알고리즘 심화: 해시 테이블과 충돌 해결 전략

평균 O(1)의 경이로운 검색 속도를 자랑하는 해시 테이블의 원리와, 필연적으로 발생하는 해시 충돌을 해결하는 다양한 기법들을 정리합니다.

1. 해싱(Hashing)의 기본 원리

해시 테이블은 키(Key)를 해시 함수에 넣어 얻은 결과값(Index)을 배열의 주소로 사용합니다. 덕분에 데이터의 위치를 계산만으로 바로 알 수 있어 **평균 O(1)**이라는 압도적인 검색 속도를 가집니다.

2. 해시 충돌(Hash Collision)

서로 다른 키가 해시 함수를 거쳐 같은 인덱스를 가리키게 되는 상황을 '충돌'이라고 합니다. 이를 해결하는 방법은 크게 두 가지입니다.

• 체이닝 (Chaining): 같은 주소로 배정된 데이터들을 연결 리스트로 묶어서 관리합니다. 구현이 비교적 간단하고 데이터 삭제가 쉽습니다.
• 개방 주소법 (Open Addressing): 충돌이 나면 배열의 다른 빈 공간을 찾아 떠납니다.
  • 선형 탐사: 바로 다음 칸을 확인
  • 이차 탐사: 제곱수만큼 떨어진 칸을 확인
  • 이중 해싱: 또 다른 해시 함수를 이용해 이동 간격을 결정

3. 해시 테이블 성능의 핵심

해시 테이블의 성능은 해시 함수의 품질과 **부하율(Load Factor)**에 달려 있습니다. 데이터가 배열 크기의 일정 수준(보통 70~80%)을 넘어서면 충돌이 급격히 늘어나므로, 배열 크기를 키우고 재배치하는 '리해싱(Rehashing)' 과정이 필요합니다.