서로 다른 두 값이 같은 인덱스로 계산되는 상황. 피할 수 없다. 키의 가짓수가 테이블 크기보다 많으면 비둘기집 원리로 반드시 겹치기 때문이다. 해시 테이블이 O(1)이라고 말할 수 있느냐는 이 충돌을 얼마나 잘 처리하느냐에 달려 있다.
충돌을 피할 수 없는 이유
완벽한 해시 함수를 만들 수 없어서다.
boolean처럼 값의 종류가 적거나 Integer, Long 같은 숫자 타입은 값 자체를 해시로 쓸 수 있어서 충돌이 없다. 하지만 String이나 직접 만든 객체는 가능한 값이 사실상 무한해서, 서로 다른 값에 서로 다른 수를 배정하는 함수를 만들 수 없다.
설령 만들었다 해도 테이블 크기로 나누는 순간 다시 겹친다. hash(a) != hash(b)인데 hash(a) % M == hash(b) % M이 되는 것이다.
분리 연결법 (Separate Chaining)
같은 자리에 연결 리스트를 매달고 뒤에 이어 붙인다. 값의 주소가 바뀌지 않고, 테이블이 차올라도 성능이 선형적으로만 나빠진다. 해시 함수가 값을 뭉치게 만들어도 별로 영향받지 않아 충돌 횟수만 신경 쓰면 된다.
대신 리스트 노드만큼 추가 메모리를 쓰고, 한 자리에 많이 쌓이면 그 자리 탐색이 O(N)이 된다. 한 자리에 몰려서 O(N)이 되면 해시를 쓸 이유가 없어지니, 충돌이 덜 나는 해시 함수를 고르는 것이 근본이다.
개방 주소법 (Open Addressing)
추가 메모리 없이 테이블의 빈칸을 찾아 들어간다. 충돌하면 원래 자리가 아닌 다른 곳에 저장되므로 값의 주소가 바뀐다. 데이터가 한 배열에 모여 있어 참조 지역성이 좋고, 캐시에 잘 올라가 조회가 빠르다. 데이터가 작고 테이블에 다 들어갈수록 유리하다.
삭제가 까다롭다는 것이 약점이다. 그냥 비우면 그 자리를 건너뛰고 뒤에 저장된 값을 못 찾는다. 그래서 여기 있었다가 지워졌다는 더미 노드를 남기는데, 삭제가 잦으면 더미가 쌓여 검색할 때 여러 버킷을 연속으로 훑게 된다. 일정 수를 넘으면 새 배열을 만들어 재해시해야 성능이 유지된다.
빈칸을 어떻게 찾느냐로 다시 갈린다.
| 방법 | 어떻게 | 특징 |
|---|---|---|
| 선형 탐사 | 한 칸씩 뒤로 | 구조가 단순하고 캐시 효율이 가장 좋다. 대신 값이 한 덩어리로 뭉치는 클러스터링이 심하다 |
| 제곱 탐사 | 1, 4, 9, 16칸씩 | 뭉침을 흩뜨린다. 다만 애초에 같은 해시값을 가진 키끼리는 여전히 같이 움직인다 |
| 이중 해싱 | 두 번째 해시 함수로 보폭을 정함 | 클러스터링에 거의 영향받지 않는다. 대신 캐시 효율이 나쁘고 계산이 가장 많다 |
자바 HashMap이 둘을 섞는 방식
자바 HashMap은 둘을 섞는다. 기본은 분리 연결법인데, 한 버킷에 값이 8개를 넘게 쌓이면 그 버킷의 연결 리스트를 레드-블랙 트리로 바꾼다. 연결 리스트의 최악은 O(N)이지만 트리는 O(log N)이라 최악이 크게 개선된다. JDK 7까지는 연결 리스트만 썼고 JDK 8부터 이렇게 바뀌었다. 균형 트리가 여기 쓰인다.
참고
임계값은 8이고 조건은 초과다. 그리고 조건이 하나 더 있다. 테이블 용량이 64 미만이면 트리로 바꾸는 대신 테이블을 넓힌다(MIN_TREEIFY_CAPACITY). 원본과 이 저장소의 다른 문서들은 이 조건을 적지 않았다. HashMap 소스