해시 충돌과 해결 방법 (Hash Collision Resolution)
쉽게 풀면
아파트 우편함을 생각해 봅시다. 이름을 기준으로 우편함 번호를 정했는데, 서로 다른 두 사람에게 같은 번호가 배정되는 경우가 생길 수 있습니다. 이때 한 우편함 안에 여러 사람의 편지를 겹쳐서 넣어두는 방법(체이닝)이 있고, 아니면 이미 자리가 찼으니 바로 옆의 빈 우편함을 찾아 넣는 방법(개방주소법)이 있습니다. 해시테이블도 마찬가지로 서로 다른 데이터가 같은 저장 위치로 계산되는 "충돌"이 발생할 수 있는데, 이를 해결하지 않으면 데이터가 유실되므로 이런 해결 전략이 반드시 필요합니다.
왜 중요한가
해시 충돌 해결 방법은 해시테이블의 실제 성능을 좌우하는 핵심 요소이기 때문에, 데이터베이스, 캐시 시스템, 분산 시스템 논문에서 자료구조 설계의 근거로 자주 다뤄집니다. 대규모 데이터를 다루는 시스템에서는 충돌 처리 방식에 따라 검색·삽입 성능과 메모리 사용량이 크게 달라지므로, 새로운 자료구조나 캐싱 알고리즘을 제안하는 연구에서는 어떤 충돌 해결 전략을 썼는지가 성능 비교의 중요한 조건으로 명시됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 "같은 주소로 계산되는 데이터끼리는 하나의 목록으로 연결해 저장하는 방식을 써서, 충돌이 생겨도 데이터를 넣고 찾는 속도가 크게 느려지지 않도록 했다"는 뜻입니다.
연속된 빈 자리를 찾는 대신 두 번째 해시 함수를 이용해 충돌 시 다음 위치를 계산함으로써, 데이터가 한쪽으로 몰리는 문제를 줄였다는 뜻이다.
여러 서버에 데이터를 분산 저장하는 시스템에서도 충돌과 유사한 부하 쏠림 문제가 발생할 수 있으며, 이를 완화하는 해싱 기법이 분산 시스템 설계에 쓰인다는 것을 보여준다.
조금 더 깊게 보면
충돌 해결 방식은 크게 체이닝(연결 리스트로 같은 주소의 데이터를 묶는 방식)과 개방주소법(선형 탐사, 이차 탐사, 이중 해싱 등으로 빈 자리를 찾는 방식)으로 나뉘며, 각각 메모리 사용 패턴과 캐시 효율성이 다릅니다. 개방주소법은 별도의 포인터 없이 배열 안에서 처리되어 캐시 지역성이 좋은 반면, 테이블이 꽉 찰수록 성능이 급격히 나빠지는 특징이 있습니다. 그래서 논문에서는 적재율(load factor, 저장된 데이터 수 대비 테이블 크기)을 함께 언급하며 충돌 빈도와 성능의 관계를 설명하는 경우가 많습니다.
주의할 점
충돌 해결 기법을 쓴다고 해도 해시 함수 자체가 특정 값에 몰리게 데이터를 배치한다면(즉 해시 함수의 분포가 나쁘면) 충돌이 잦아져 해시테이블의 장점인 빠른 검색 속도를 잃게 됩니다. 따라서 충돌 해결 전략만큼이나 해시 함수 자체의 설계도 중요합니다.