해시 테이블에 대한 설명으로 옳지 않은 것은? | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 24년 1회차
해시 테이블에 대한 설명으로 옳지 않은 것은?
1
충돌이 발생하지 않는다면 상수 시간 에 검색과 저장이 가능하다.2
키 값을 입력으로 받아 해시 테이블상의 주소를 리턴하는 해시 함수는 나누기 방법뿐만 아니라 곱하기 방법으로도 만들 수 있다.
3
저장 원소의 총수를 해시 테이블의 크기로 나눈 적재율(load factor)은 해시 테이블의 성능에 중요한 영향을 미친다.
4
충돌을 해결하기 위한 별도 체이닝과 오픈 주소 방법은 모두 추가적인 저장 공간을 필요로 하지 않는다.
해설
옳지 않은 것은 별도 체이닝과 오픈 주소 방법 모두 추가 저장 공간이 필요 없다는 설명이다.
별도 체이닝은 충돌한 원소를 테이블 밖의 연결 리스트에 매달므로 노드와 포인터를 위한 추가 공간이 필요하다. 추가 공간 없이 테이블 내부의 빈 칸을 찾아 저장하는 것은 오픈 주소 방법이다.
- 충돌이 없으면 해시 함수 계산 한 번으로 주소가 정해지므로 검색·저장이 이라는 설명은 옳다.
- 해시 함수를 나누기(제산) 방법뿐 아니라 곱하기(승산) 방법으로도 만들 수 있다는 설명은 옳다.
- 적재율이 높을수록 충돌이 잦아져 성능이 떨어지므로 적재율이 성능에 중요한 영향을 준다는 설명은 옳다.
오류나 개정된 내용이 보이면 알려주세요