[개발자 기술 면접 대비] 🧩 Hash 충돌 시 내부 데이터 탐색은 어떻게 이루어질까?

1️⃣ 해시 함수란?

• 임의의 크기를 가진 키(key)를 고정된 크기의 해시값(정수 인덱스)로 변환해주는 함수
• key → hash(key) → index 형태로 해시 테이블의 위치를 결정

---

2️⃣ 해시 충돌이란?

서로 다른 키가 같은 해시값(인덱스)을 가질 때 발생하는 현상

예시:

hash("apple") % 10 == 3  
hash("banana") % 10 == 3  # → 충돌 발생

두 키 모두 인덱스 3번에 저장되려고 할 때 → 충돌 해결 필요

---

3️⃣ 충돌 해결 방법 & 내부 탐색 방식

✅ [1] Chaining 방식 (Separate Chaining)

• 충돌된 데이터를 같은 인덱스의 연결 리스트(또는 트리)에 차곡차곡 저장
• 탐색 시 해당 인덱스에 있는 리스트를 순차적으로 순회하면서 key를 비교

table[3] = [("apple", 1), ("banana", 2)]

• "banana" 검색 시:
  • table[3]에서 각 요소의 key를 비교 → banana 발견 시 value 반환

🔍 Java의 HashMap은 충돌이 심해지면 연결 리스트를 Red-Black Tree로 전환하여 탐색 성능을 O(n) → O(log n)으로 향상시킴

---

✅ [2] Open Addressing 방식

• 빈 공간이 있는 다른 슬롯에 저장하며, 한 테이블 안에서 충돌을 해결
• 탐색 시에도 충돌된 인덱스에서부터 순차적으로 검사하면서 key를 비교

예시 (Linear Probing):

table[3] = ("apple", 1)
table[4] = ("banana", 2)

• "banana" 검색 시:
  • table[3] → key 다름
  • table[4] → key 일치 → value 반환

---

🧠 왜 key 비교가 중요한가?

• 해시값이 같더라도 진짜 원하는 key인지 확인해야 함
• 탐색 시에는 항상 key를 직접 비교해서 일치 여부를 판단

---

🎯 면접 답변 예시

“해시 충돌이 발생하면 같은 인덱스에 여러 데이터를 저장하게 되는데, 대표적인 해결 방식은 Chaining과 Open Addressing입니다.
Chaining은 연결 리스트나 트리 구조로 데이터를 보관하고, 탐색 시 리스트를 순회하며 key를 비교합니다.
Open Addressing은 테이블 내 빈 슬롯에 데이터를 저장하고, 탐색 시에도 key를 하나씩 비교하며 원하는 데이터를 찾습니다.”