해시 테이블(Hash Table)의 원리와 충돌 해결

배열(Array)은 값을 찾으려면 처음부터 끝까지 뒤져야 해서 O(n)이 걸립니다. 그런데 해시 테이블은 마법처럼 **O(1)**만에 값을 찾습니다. JS의 Object나 Map이 내부적으로 이렇게 동작합니다. 어떻게 가능할까요?

1. 해시 함수 (Hash Function)

임의의 데이터를 넣으면 고정된 길이의 숫자(인덱스)를 뱉어주는 함수입니다. "korea" -> 5, "japan" -> 2 이 숫자를 인덱스로 배열에 저장하면 바로 찾아갈 수 있습니다.

2. 해시 충돌 (Hash Collision)

만약 "china"를 넣었는데 똑같이 5가 나오면 어떡하죠? 이미 5번 칸에 Korea가 살고 있는데요. 이걸 충돌이라고 합니다. 비둘기집 원리에 의해 충돌은 피할 수 없습니다.

2.1 해결법: 체이닝 (Chaining) - Open Hashing

5번 칸에 연결 리스트(Linked List)를 답니다. 5: [Korea] -> [China] 처럼 줄줄이 엮습니다. 충돌이 나면 뒤에 갖다 붙입니다. 구현이 쉽지만 메모리가 추가로 필요합니다. Java의 HashMap이 이 방식을 씁니다. (데이터가 많아지면 Red-Black Tree로 변신해서 성능을 최적화합니다.)

2.2 해결법: 개방 주소법 (Open Addressing) - Closed Hashing

5번이 찼으면 옆 칸(6)을 봅니다. 비었으면 거기 들어갑니다. (선형 탐사). 추가 메모리가 필요 없지만, 데이터가 삭제되면 구멍이 뚫려서 탐색이 끊길 수 있습니다.

3. 언제 쓸까?

• 빠른 탐색이 필요할 때
• 중복을 제거해야 할 때 (Set)
• 캐싱 (Key-Value)

해시 테이블은 컴퓨터 공학이 낳은 가장 위대한 자료구조 중 하나입니다.