[면접준비] 해시테이블과 이진 검색 트리 (24/04/24)

해시 테이블

해시 테이블은 키를 기반으로 요소에 매우 빠른 액세스를 제공하는 데이터 구조입니다. 해시 함수를 사용하여 원하는 값을 찾을 수 있는 버킷 또는 슬롯 배열에 대한 인덱스를 계산합니다. 이상적으로 해시 함수는 각 키를 고유한 버킷에 할당하지만 대부분의 해시 테이블 디자인은 어떤 형태의 충돌 해결을 사용합니다.

• 장점:
  • 빠른 조회: 검색, 삽입 및 삭제에 대해 O(1)의 평균 시간 복잡도를 제공합니다.
  • 시간 측면에서 효율적: 특히 해시 함수가 좋고 부하율(요소 수/버킷 수)을 관리할 수 있는 경우.
  • 직접 액세스: 계산된 해시 키를 사용하여 데이터에 직접 액세스할 수 있습니다.
• 단점:
  • 공간 비효율성: 해시 테이블에는 구조를 위한 추가 공간이 필요하며 충돌 처리를 위한 오버헤드가 발생할 수 있습니다.
  • 해시 함수에 민감함: 해시 함수가 좋지 않으면 많은 충돌이 발생할 수 있으며 최악의 경우 성능이 O(n)으로 저하됩니다.
  • 순서가 보존되지 않음: 데이터는 고유한 순서를 저장하지 않습니다. 요소를 반복한다고 해서 반드시 특정 순서로 처리되는 것은 아닙니다.

 

이진 검색 트리(BST)

이진 검색 트리는 각 노드가 노드의 왼쪽 하위 트리에 있는 모든 키보다 크고 오른쪽 하위 트리에 있는 모든 키보다 작은 키를 갖는 이진트리입니다. 이 속성은 데이터 세트가 자주 변경되는 동적 데이터 시나리오에 BST를 유용하게 만듭니다

 

• 장점:
  • 순서 유지: 요소의 정렬된 순서를 생성하기 위해 요소를 순회할 수 있습니다.
  • 동적 구조: 필요에 따라 구조를 확장하고 축소할 수 있습니다(삽입 및 삭제는 비교적 간단합니다).
  • 유연한 크기: 필요에 따라 트리를 늘리거나 줄일 수 있으며 다양한 데이터세트 크기를 처리할 수 있습니다.
• 단점:
  • 성능이 저하될 수 있음: 최악의 경우(예: 정렬된 데이터 삽입)에서 BST는 연결 목록으로 변질되어 시간 복잡도가 O(n)이 될 수 있습니다.
  • 더 많은 공간 필요: 일반적으로 추가 포인터(왼쪽 및 오른쪽) 저장으로 인해 더 많은 메모리가 필요합니다.
  • 균형 조정: 효율적인 운영을 유지하려면 BST의 균형을 맞춰야 할 수 있으며 이는 추가 논리와 운영이 필요합니다.

비교

기능적 측면

• 성능: 
  • 해시 테이블은 충돌로 인한 잠재적 오버헤드를 고려하더라도 해시 함수를 통한 직접 액세스로 인해 조회, 삽입 및 삭제에 대한 평균 O(1) 작업으로 더 빠르게 수행되는 경우가 많습니다. 
  • 이진 검색 트리는 평균 O(log N) 연산을 사용하는, 특히 균형이 유지될 때 경쟁력 있는 성능을 제공합니다.
• 순서 및 범위 쿼리:
  • BST는 본질적으로 데이터를 정렬된 순서로 유지하므로 정렬된 데이터 또는 효율적인 범위 쿼리가 필요한 애플리케이션에 유용합니다. 이는 순서를 유지하지 않고 정렬된 데이터를 활용하는 작업에 적합하지 않은 해시 테이블에 비해 중요한 이점입니다.

메모리 측면

• 메모리 할당: 
  • BST는 일반적으로 요소 수에 비례하여 동적으로 증가하거나 축소되는 메모리를 사용합니다. 
  • 해시 테이블은 충돌을 최소화하고 효율적인 작업을 유지하기 위해 즉시 필요한 것보다 더 많은 메모리를 할당하는 경우가 많아 낭비로 보일 수 있습니다.
• 캐시 효율성: 
  • 해시 테이블은 일반적으로 연속적인 메모리 블록을 사용하므로 요소에 액세스할 때 캐시 성능이 향상됩니다. 
  • BST는 노드 기반 구조로 인해 메모리 조각화로 인해 캐시 지역성이 저하될 수 있습니다.

실제 적용 및 고려 사항

• 해시 테이블은 매우 빠른 액세스가 필요하고 데이터세트 크기가 알려져 있어 최적화된 해시 함수를 통해 충돌을 최소화할 수 있는 경우에 선호됩니다.
• BST는 순서 유지 또는 효율적인 범위 쿼리가 필요한 애플리케이션에 더 적합합니다. 문자열과 같은 비교 연산의 이점을 얻는 데이터를 처리할 때 특히 유리합니다.