[Interview] 해시 테이블과 이진 검색트리에 대해 설명해주세요

해시 테이블 (Hash Table)

● 해시 함수를 통해 key를 index로 변환하여 데이터를 빠르게 접근할 수 있습니다.

   - 단, 데이터의 순서가 보장되지 않고 충돌 문제에 영향이 있습니다.

   - BigO 시간 복잡도로 표현하면 O(1)입니다. 속도에 특화되어 있습니다.

key : 출석번호, value : 이름

(1, 김하나)
(2, 이두리)
(3, 신 석)
(4, 박 사)
(5, 오이오)

  - key에 대해 해시함수를 적용하여 배열 상의 index를 결정한 후 데이터를 저장하는 방식입니다.

  - 또 다른 단점으로는 키-값 들이 별도의 순서를 유지하지 않습니다. 알파벳 순서로 정렬은 어렵습니다.

 

이진 검색트리 (Binary Search Tree / Tree Map)

● 노드들이 key의 크기순으로 정렬되어 저장됩니다.

  - 정렬된 결과를 바로 얻을 수 있으며, 범위 검색(range query)과 같은 연산을 하기에 적절합니다.

  - 각 노드의 왼쪽에 작은 값, 오른쪽에 큰 값이 위치하도록 유지되어 데이터가 항상 정렬된 상태입니다.

                 5000 (김팀장)
                /             \
   3500 (이대리)               7000 (박과장)
      /       \              /          \
3000 (최사원) 4000 (정사원) 6000 (홍주임) 8000 (강부장)

  - 위의 예시를 사용한다면 급여를 낮은 순서, 높은 순서로 조회하기에 적절합니다.

 

Q. 해시 테이블과 이진 검색트리 비교하여 설명해보세요

A :
  해시테이블은 빠른 단일 원소 검색과 삽입, 삭제에 강점을 가집니다. 입력 크기를 미리 알고 있고 순서 정보가 필요 없는 경우 유리합니다. 반면, 이진 검색트리는 데이터가 항상 정렬된 상태를 유지합니다. 때문에 넓은 범위를 검색해야 할 때에나 정렬된 데이터 조회가 필요할 때 적합합니다. 동적 데이터에 사용하기에 유리합니다.

  한 문장으로 한 번 더 정리하자면, 해시테이블은 빠른 접근 속도가 요구되는 경우 사용하고, 이진 검색트리는 정렬 및 범위 질의가 중요한 경우에 적합합니다.