[개발자 기술 면접 대비] 🌳 검색 자료구조로서 해시 테이블과 이진 탐색 트리 비교

검색(탐색)을 위한 대표적인 자료구조는 Hash Table과 Binary Search Tree (BST)입니다.
이 두 구조는 각기 다른 방식으로 데이터를 저장하고 찾습니다.

---

1️⃣ 핵심 비교표

항목 해시 테이블 (Hash Table) 이진 탐색 트리 (Binary Search Tree, BST)

구조	배열 기반 + 해시 함수 사용	노드 기반 트리 구조
키 기준	해시 함수로 인덱스 계산	노드의 값 대소 비교
탐색 방식	key → hash → 인덱스 → 버킷 탐색	루트부터 대소 비교하며 좌/우로 이동
시간복잡도 (탐색)	평균 O(1), 최악 O(n)	평균 O(log n), 최악 O(n)
정렬 여부	❌ 정렬되지 않음	✅ 항상 정렬된 상태 유지
범위 검색	어려움	효율적 (예: x > 10 검색)
공간 효율	배열 공간 낭비 가능	노드 기반, 동적 구조
활용 예	Python dict, Java HashMap	TreeSet, TreeMap, DB 인덱싱

---

2️⃣ 해시 테이블 (Hash Table)

• key → value 형식으로 저장하는 자료구조
• 해시 함수를 이용해 배열 인덱스를 계산한 뒤, 해당 위치에 데이터를 저장
• 탐색, 삽입, 삭제가 평균 O(1)로 매우 빠름

✔️ 장점

• 빠른 검색
• 구현 단순

❗ 단점

• 해시 충돌 발생 가능 → 별도 충돌 해결 필요 (Chaining, Open Addressing 등)
• 정렬 불가능
• 범위 기반 탐색 어려움
• 배열 크기를 넉넉히 설정해야 하므로 공간 낭비 가능

---

3️⃣ 이진 탐색 트리 (BST)

• 각 노드에 데이터를 저장하고,
• 왼쪽 자식 < 부모 < 오른쪽 자식의 대소 관계를 유지
• 중위 순회(in-order traversal) 시 항상 정렬된 결과 출력

✔️ 장점

• 정렬된 상태 유지
• 범위 기반 검색 용이
• 삽입, 삭제, 탐색 모두 평균 O(log n)

❗ 단점

• 트리가 한쪽으로 편향되면 성능 O(n)까지 저하
• 이를 해결하기 위해 균형 BST (AVL Tree, Red-Black Tree) 사용

---

🎯 면접 한 줄 요약 예시

“해시 테이블은 빠른 O(1) 검색이 가능한 반면, 정렬이나 범위 검색은 불가능합니다. 반면 이진 탐색 트리는 O(log n) 탐색이 가능하고 항상 정렬된 상태를 유지하여 다양한 탐색 연산에 유리합니다.”

---

🧠 어떤 상황에 어떤 걸 사용할까?

상황 추천 자료구조

매우 빠른 검색이 필요	해시 테이블
정렬된 데이터가 필요	BST
범위 검색 (예: 10 < x < 50)	BST
중복 없는 키 저장	BST, Set
키 순서에 관계 없는 키-값 저장	해시 테이블