앞선 글에서 해시 테이블(Hash Table)은 O(1)이라는 꿈의 검색 속도를 제공한다고 배웠습니다. 하지만 이론적으로 완벽해 보이는 이 자료구조에도 치명적인 약점이 하나 숨어 있습니다. 바로 '해시 충돌(Hash Collision)'입니다. "서로 다른 키(Key)를 넣었는데, 해시 함수가 우연히 똑같은 방 번호(Index)를 주면 어떻게 하지?"라는 문제입니다. 마치 비둘기집 원리처럼, 저장 공간은 유한한데 들어오는 데이터가 많아지면 필연적으로 겹치는 자리가 생길 수밖에 없습니다. 오늘은 개발자 면접의 단골 질문인 해시 충돌의 개념과 이를 해결하는 기술적 방법들을 상세히 알아보겠습니다.
1. 해시 충돌(Collision)이란?
해시 함수는 무한에 가까운 입력값을 받아 유한한 배열의 인덱스로 변환합니다. 아무리 정교하게 설계된 해시 함수라도, 서로 다른 입력값에 대해 동일한 출력값을 내놓을 확률이 존재합니다.
예를 들어 10개의 방이 있는 해시 테이블이 있다고 가정해 봅시다. 1. `hash("apple")` -> 3번 방 배정 (데이터 저장 완료) 2. `hash("banana")` -> 7번 방 배정 (데이터 저장 완료) 3. `hash("cherry")` -> 3번 방 배정!
이때 "cherry"를 저장하려고 3번 방에 갔더니 이미 "apple"이 자리를 차지하고 있습니다. 이것이 바로 해시 충돌입니다. 이 문제를 해결하지 못하면 기존 데이터가 덮어씌워져 사라지거나, 새로운 데이터를 저장할 수 없게 됩니다.
2. 해결책 1: 체이닝 (Chaining) - "같이 쓰자!"
가장 대중적이고 직관적인 해결 방법은 체이닝(Chaining)입니다. 이름 그대로 데이터를 사슬(Chain)처럼 엮어서 연결 리스트(Linked List)로 매달아 두는 방식입니다.
2-1. 동작 원리
충돌이 발생하면 해당 방(Bucket)에 연결 리스트를 생성합니다. 그리고 기존 데이터 뒤에 새로운 데이터를 줄줄이 연결합니다. 즉, 3번 방에는 "apple"만 있는 것이 아니라, ["apple"] -> ["cherry"] -> ["melon"] 순서로 데이터가 기차처럼 연결되어 저장됩니다.
2-2. 장단점 분석
- 장점: 해시 테이블의 크기를 늘리지 않고도 데이터를 무한정 받을 수 있습니다. 구현이 비교적 단순합니다.
- 단점: 한 방에 데이터가 너무 많이 몰리면(쏠림 현상), 그 방에서 데이터를 찾을 때 연결 리스트를 순차 탐색해야 하므로 속도가 O(n)으로 느려집니다. 이를 방지하기 위해 해시 함수가 데이터를 골고루 분산시키는 것이 중요합니다.
3. 해결책 2: 개방 주소법 (Open Addressing) - "빈방 찾기"
체이닝과 달리 추가적인 메모리(포인터)를 쓰지 않고, 해시 테이블의 빈 공간을 찾아 떠나는 방식을 개방 주소법이라고 합니다. "원래 내 자리는 아니지만, 비어있으니 내가 쓸게"라는 식입니다.
3-1. 선형 탐사 (Linear Probing)
충돌이 발생하면 바로 옆 칸(인덱스 + 1)을 확인합니다. 비어있으면 저장하고, 차 있으면 또 다음 칸을 확인합니다. - 장점: CPU 캐시 효율이 좋습니다(데이터가 붙어 있으므로). - 단점: 데이터들이 한곳에 뭉치는 클러스터링(Clustering) 현상이 발생하여, 빈방을 찾는 시간이 점점 오래 걸릴 수 있습니다.
3-2. 이차 탐사 (Quadratic Probing) 및 이중 해싱 (Double Hashing)
선형 탐사의 뭉침 현상을 막기 위해, 옆 칸이 아니라 1칸, 4칸, 9칸($n^2$)씩 건너뛰며 빈방을 찾거나(이차 탐사), 해시 함수를 하나 더 써서 점프할 간격을 계산하는 방식(이중 해싱)을 사용하기도 합니다.
4. 로드 팩터(Load Factor)와 리사이징
해시 충돌을 줄이는 근본적인 방법은 테이블 자체를 키우는 것입니다. 해시 테이블에는 '로드 팩터(Load Factor)'라는 지표가 있습니다. 전체 방 개수 대비 데이터가 얼마나 차 있는지를 나타내는 비율입니다. 보통 로드 팩터가 0.75(75%)를 넘어가면, 충돌 확률이 급격히 높아진다고 판단하여 테이블의 크기를 2배로 늘리고 기존 데이터를 새로운 테이블로 옮기는 리사이징(Resizing) 작업을 수행합니다. 자바(Java)의 HashMap이나 파이썬의 Dictionary도 내부적으로 이 방식을 사용하여 성능을 유지합니다.
1. 해시 충돌은 서로 다른 키가 같은 해시값(인덱스)을 가질 때 발생하는 필연적인 현상입니다.
2. 체이닝은 연결 리스트를 이용해 한 방에 여러 데이터를 줄세우는 방식입니다.
3. 개방 주소법은 인근의 빈방을 찾아 데이터를 저장하는 방식으로, 메모리를 효율적으로 사용합니다.