2021 국가직9급 컴퓨터일반 13번 해설 — 해시

① 연결리스트는체이닝(Chaining) 구현에적합하다

이 선지 진술은 옳음(O)

체이닝은 같은 버킷에 들어온 항목들을 연결 구조로 관리하는 충돌 해결 방법이다. 연결 리스트는 그 구현에 적합하다.

② 충돌이전혀없다면해쉬탐색의시간복잡도는O(1)이다

이 선지 진술은 옳음(O)

좋은 해시 함수와 충돌이 없는 조건에서는 키가 바로 버킷으로 매핑된다. 따라서 탐색 시간은 상수 시간으로 본다.

③ 최악의경우에도이진탐색보다빠른성능을보인다

이 선지 진술은 틀림(X)

해시는 충돌이 심하면 최악의 경우 O(n)까지 나빠질 수 있다. 이진 탐색은 정렬 배열에서 O(log n)이다.

④ 해쉬함수는임의의길이의데이터를입력받을수있다

이 선지 진술은 옳음(O)

일반적인 해시 함수는 다양한 길이의 입력을 받아 고정 길이의 해시값이나 테이블 인덱스로 변환한다. 입력 길이가 반드시 고정될 필요는 없다.