🔑 해시 테이블(Hash Table) 개념과 충돌 처리 방식 정리
해시 테이블이란?
해시 테이블(Hash Table)은 키를 해시 함수를 통해 정수 인덱스로 변환한 뒤 해당 인덱스를 기반으로 값을 저장하는 자료구조이다. 이 과정을 통해 일반적인 배열처럼 빠른 접근 속도를 얻을 수 있다.
Map: 키-값 쌍(key → value) 저장
Set: 값의 존재 ㅇ여부만 저장 (중복 허용 X)
두 자료구조 모두 내부적으로 해시 테이블을 기반으로 구현되는 경우가 많으며 탐색/삽입/삭제 모두 평균적으로 O(1)의 성능을 기대할 수 있다.
해시 테이블의 핵심은 아래 세 가지 요소이다.
1) 해시 함수 (Hash Function)
입력값(key)을 받아 고정된 정수로 변환하는 함수로 동일한 키는 항상 동일한 해시값을 반환해야 한다. 또한 서로 다른 키도 같은 해시값이 나올 수 있으므로 균등 분포가 중요하다.
2) 버킷 인덱싱 (Bucket Indexing)
해시 함수는 키를 정수로 바꾸는 일만 한다. 따라서 실제로 값을 저장하기 위해 해시값을 배열 인덱스로 변환하는 것이 버킷 인덱싱이다.
index = hash(key) % capacity
해시 함수로 나온 정수값을 전체 버킷 수로 나머지를 구해 인덱스를 결정한다. 나머지 연산을 사용하는 이유는 배열의 경우 고정된 크기를 가지기 때문에 해시값이 아무리 커도 배열 범위를 벗어나지 않도록 하기 위함이다.
3) 충돌 처리 (Collision Handling)
해시 함수는 다양한 키를 한정된 인덱스 공간의 배열에 매핑해야 한다. 그러다 보니 다른 키임에도 불구하고 같은 인덱스를 가리키는 경우가 생기는데 이를 충돌(Collision)이라고 한다.
"dog" -> hash = 42 -> index = 42 % 16 = 10
"god" -> hash = 58 -> index = 58 % 16 = 10 (충돌)
충돌이 해결되지 않으면 기존 값을 덮어쓰게 되어 데이터 손실이 일어나고 삽입/탐색/삭제가 실패하거나 오류가 발생할 수 있다. 따라서 충돌을 어떻게 다루느냐에 따라 해시 테이블의 성능이 결정된다.
[대표적인 충돌 처리 방법]
1) 체이닝 (Chaining, 분리 연결법)
같은 인덱스에 들어온 키들을 연결 리스트(혹은 트리)로 저장하는 방법으로 배열의 각 칸이 노드의 체인을 가진다.
bucket[10] -> [("dog", var1)] -> [("god", var2)] -> ...
장점: 구현이 간단하며 삭제가 쉽고 *로드 팩터가 1을 넘어도 동작이 가능하다.
로드 팩터(Load Factor)란?
해시 테이블이 얼마나 차있는지를 나타내는 비율
공식) 로드 팩터 α = 저장된 원소 수 / 전체 버킷 수
단점: 각 버킷이 포인터를 갖게 되어 추가적인 메모리 오버헤드가 발생하며 메모리에 저장된 위치가 연속적이지 않아 캐시에 친화적이지 않다.
Java의 HashMap은 이 체이닝 방식을 기반으로 하며 체인 길이가 너무 길어지면 Red-Black Tree로 자동 전환하여 성능 저하를 막는다.
2) 오픈 어드레싱 (Open Addressing, 개방 주소법)
충돌이 발생하면 테이블 내에서 다음 빈 자리를 찾아서 저장하는 방식으로 배열 자체 안에서 모든 값을 저장하게 된다.
bucket[10] -> 이미 사용중 ->
bucket[11] 확인 -> 비어있음 -> 저장
장점: 배열만으로 동작하므로 포인터나 연결 리스트 같은 별도 구조체가 필요하지 않으며 캐시 친화적이다.
단점: 삭제 시 값을 단순히 제거하면 탐색 경로가 끊겨 오류가 발생할 수 있고 공간이 점점 채워질수록 빈 자리를 찾는 데 시간이 오래 걸리므로 로드 팩터가 낮아야 성능이 유지된다.
*리사이즈
로드 팩터가 설정한 임계치를 초과하면 해시 테이블은 자체적으로 크기를 2배로 늘리고 모든 값을 다시 해싱(rehash)하게 된다. 이 과정을 리사이즈(resize) 또는 리해시(rehash) 라고 한다. 따라서 대량의 데이터를 넣을 것이 예상되는 경우 초기 용량을 미리 충분히 설정하는 것이 좋다.
