Hash table의 collision 해결 방식은 크게 chaining과 open addressing으로 나눌 수 있습니다. Chaining은 한 bucket에 여러 원소를 묶어 두는 방식이고, open addressing은 한 slot에 하나의 원소만 두되 충돌이 나면 table 안에서 다른 빈 slot을 찾는 방식입니다.
Open addressing 안에서 다음 slot을 찾는 방법에 따라 linear probing, quadratic probing, double hashing으로 나뉩니다. Linear probing은 한 칸씩, quadratic probing은 제곱 간격으로, double hashing은 두 번째 hash 함수로 정한 간격만큼 이동합니다.
꼬리질문
조금 더 깊게 물어본다면
답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.
Open addressing과 chaining의 차이는 무엇인가요?
Chaining은 같은 bucket 안에 list나 다른 collection으로 여러 원소를 저장합니다. Open addressing은 각 slot에 하나의 원소만 저장하고, collision이 나면 table 내부의 다른 slot을 탐사합니다.
그래서 open addressing은 load factor가 1에 가까워질수록 빈 slot을 찾기 어려워지고, 보통 일정 수준에서 resizing이 필요합니다.
Linear probing의 장단점은 무엇인가요?
Linear probing은 충돌 시 바로 다음 칸부터 순서대로 확인합니다. 구현이 쉽고 연속 메모리 접근이라 cache locality가 좋을 수 있습니다.
단점은 primary clustering입니다. 한 번 연속 구간이 생기면 그 근처로 새 값이 계속 붙어서 탐사 길이가 길어질 수 있습니다.
Quadratic probing은 linear probing의 어떤 문제를 줄이나요?
한 칸씩 이동하지 않고 제곱 간격으로 이동하므로 연속된 큰 덩어리가 생기는 primary clustering을 줄입니다.
다만 같은 초기 hash 값을 가진 key는 같은 탐사 순서를 따르기 때문에 secondary clustering은 완전히 없애지 못합니다.
Double hashing이 clustering을 줄이는 이유는 무엇인가요?
두 번째 hash 함수로 key마다 다른 이동 간격을 만들기 때문입니다. 시작 위치가 같더라도 이동 간격이 달라지면 같은 탐사 경로를 따라갈 가능성이 줄어듭니다.
다만 모든 slot을 잘 방문하려면 table 크기와 두 번째 hash 값이 서로 맞물리지 않도록 설계해야 합니다.
Open addressing에서 삭제가 까다로운 이유는 무엇인가요?
탐사 경로 중간의 값을 그냥 비워 버리면, 그 뒤에 있던 원소를 검색할 때 “여기서 없구나”라고 잘못 판단할 수 있습니다.
그래서 삭제 표시용 tombstone을 두거나, 삭제 후 뒤쪽 원소를 재배치하는 방식이 필요합니다.
부가 설명
Open addressing의 핵심은 “충돌 난 값을 table 밖으로 빼지 않는다”는 점입니다. 같은 배열 안에서 빈 자리를 찾아 들어가기 때문에 pointer 구조가 단순하고 cache locality가 좋을 수 있습니다. 대신 table이 많이 차면 빈 slot을 찾는 탐사 길이가 길어지고 성능이 급격히 나빠질 수 있습니다.
탐사 순서는 보통 다음처럼 표현합니다.
h(k, i) = (h1(k) + f(i)) mod m
여기서 i는 몇 번째 시도인지, m은 table 크기입니다.
linear probing: f(i) = iquadratic probing: f(i) = i^2 또는 c1*i + c2*i^2double hashing: f(i) = i * h2(k)
Linear probing은 단순하지만 값들이 연속 구간에 몰리는 primary clustering이 생기기 쉽습니다. Quadratic probing은 primary clustering을 줄이지만 같은 초기 hash를 가진 key들이 같은 경로를 따라가는 secondary clustering은 남습니다. Double hashing은 key마다 이동 간격을 다르게 만들어 clustering을 더 줄이는 편입니다.
한 줄 정리
Open addressing은 hash collision을 table 내부의 다른 slot 탐사로 해결하고, linear probing·quadratic probing·double hashing은 그 탐사 순서를 정하는 방법입니다.