해시
키를 숫자로 바꿔 곧장 자리를 찾는 방법과, 자리가 겹칠 때의 처리, 확률로 답하는 블룸 필터다.
해시 함수: 키를 칸 번호로
배열은 번호를 알면 O(1)에 칸을 찾는다. 그런데 키가 "user:42"나 이메일 주소처럼 번호가 아니라면? 해시 함수(hash function)는 키를 정수로 바꾸고, 그 정수를 칸 수로 나눈 나머지를 칸 번호로 쓴다. 이렇게 키로 곧장 칸을 찾는 자료구조가 해시 표(hash table)다. 파이썬 dict, Java HashMap, JavaScript Map, Go map이 모두 해시 표다.
좋은 해시 함수의 조건은 셋이다. 같은 키에는 언제나 같은 값을 내야 하고(결정적), 계산이 빨라야 하고, 비슷한 키라도 결과가 고르게 흩어져야 한다. 마지막이 가장 중요하다. 키의 일부만 보는 함수는 실제 데이터에서 쉽게 무너진다. 실제 키는 같은 접두사로 시작하거나, 같은 간격으로 늘어나는 경우가 많기 때문이다.
hash = 0
for c in key:
hash = hash × 31 + c // 32비트나 64비트에서 넘치면 버린다
index = hash mod 칸 수실무 해시 표는 이보다 잘 섞는 함수를 쓴다. 바이트마다 XOR과 곱셈을 하는 FNV, 더 빠른 MurmurHash·xxHash 같은 것들이다. 외부 입력을 키로 받는 서버라면 공격자가 같은 칸에 떨어지는 키만 골라 보내 표를 O(n)으로 무너뜨릴 수 있다(해시 폭탄, hash flooding). 그래서 파이썬과 Rust는 프로세스마다 무작위 비밀 값을 섞는 SipHash 계열을 기본으로 쓴다.
이 해시는 SHA-256 같은 암호 해시와 목적이 다르다. 해시 표용 해시는 빠르고 고르게 흩어지기만 하면 되고, 암호 해시는 결과에서 입력을 되찾거나 같은 결과를 내는 두 입력을 찾는 일이 사실상 불가능해야 한다. 암호 해시와 체크섬은 데이터 노트에서 다룬다.
해시 표를 쓰는 쪽이 지켜야 할 약속도 있다. 같다고 비교되는 두 키는 해시도 같아야 하고, 키의 해시는 표에 들어 있는 동안 바뀌면 안 된다. 그래서 파이썬은 리스트·딕셔너리처럼 바뀌는 컨테이너를 키로 받지 않고(hashable의 정의), Java는 equals 결과가 바뀌도록 키 객체를 고친 뒤의 Map 동작을 정하지 않는다(Map 문서). 키를 넣은 뒤 그 필드를 고치면 홈 칸이 달라져, 분명히 들어 있는 키를 못 찾는다.
순회 순서도 약속이 아니다. Java HashMap은 순서를 보장하지 않고, 같은 순서가 계속 유지된다는 보장도 없다고 문서에 적혀 있다(HashMap 문서). 파이썬 dict는 3.7부터 넣은 순서를 지키도록 언어가 보장하지만(dict 문서), 이것은 해시 표의 일반 성질이 아니라 그 구현이 따로 한 약속이다. 순서가 필요하면 순서를 명시적으로 약속한 자료구조를 쓰거나 정렬한다.
체이닝: 칸마다 목록을 매단다
칸 수보다 키가 훨씬 많을 수 있으니, 서로 다른 키가 같은 칸에 떨어지는 충돌(collision)은 피할 수 없다. 키 23개만 있어도 칸 365개 중 둘이 겹칠 확률이 절반을 넘는다(생일 문제). 그래서 해시 표 설계의 절반은 충돌을 어떻게 다루느냐다.
체이닝(separate chaining)은 칸마다 목록(보통 연결 리스트)을 매달아, 같은 칸에 떨어진 키를 그 목록에 함께 둔다. 찾을 때는 칸을 계산한 뒤 그 목록만 훑는다.
칸 5개짜리 빈 표. 키를 5로 나눈 나머지가 칸 번호다.
키 n개를 칸 m개에 넣으면 목록 길이의 평균은 부하율 α = n/m이다. 해시가 고르다면 찾기·넣기·지우기가 평균 O(1 + α)이고, α를 상수로 묶어 두면 O(1)이다. 최악은 모든 키가 한 칸에 몰린 O(n)이다. Java HashMap은 표가 충분히 크고 한 칸의 목록이 8개에 이르면 그 칸을 균형 트리로 바꿔 최악을 O(log n)으로 막는다.
체이닝은 구현이 단순하고, 지우기가 그냥 목록에서 빼는 것이라 쉽고, 부하율이 1을 넘어도 천천히 나빠진다. 대신 노드마다 따로 할당해 메모리가 더 들고, 목록을 따라가는 동안 캐시 미스가 난다.
오픈 어드레싱과 선형 탐사
오픈 어드레싱(open addressing)은 목록을 매달지 않고 모든 키를 배열 칸 안에 직접 둔다. 홈 칸이 차 있으면 정해진 순서로 다른 칸을 들여다본다(탐사, probing). 가장 단순한 것이 선형 탐사(linear probing)로, 한 칸씩 옆으로 간다. 찾기도 같은 순서로 가다가 키를 만나면 찾은 것이고, 빈 칸을 만나면 없는 것이다.
칸 7개짜리 빈 표. 키 mod 7 값이 그 키의 홈 칸이다.
지우기에 함정이 있다. 그림에서 24를 그냥 비우면, 24 때문에 5번 칸까지 밀려 앉은 31을 찾을 때 4번 칸이 비어 있어 "없다"고 멈춰 버린다. 그래서 지운 칸에는 묘비(tombstone)를 남긴다. 찾기는 묘비를 지나가고, 넣기는 키가 없음을 확인한 뒤 첫 묘비 자리를 다시 쓴다. 묘비가 쌓이면 탐사가 길어지므로, 재해시할 때 묘비를 함께 걷어 낸다.
선형 탐사의 약점은 뭉침(primary clustering)이다. 찬 칸이 이어진 덩어리는 그 범위에 떨어지는 키를 모두 끝으로 보내 덩어리를 더 키운다. 이를 줄이려고 1, 4, 9칸씩 건너뛰는 제곱 탐사(quadratic probing), 키마다 다른 보폭을 쓰는 이중 해싱(double hashing), 멀리 밀려난 키에게 자리를 양보하게 하는 로빈 후드 해싱(Robin Hood hashing)이 있다.
그래도 선형 탐사는 실무에서 자주 이긴다. 옆 칸을 보는 것은 같은 캐시 라인 안이라 거의 공짜이고, 포인터도 할당도 없다. 구글의 SwissTable(Abseil, 그리고 이를 따른 Rust의 HashMap)도 오픈 어드레싱이고, 16칸씩 묶어 SIMD 명령 하나로 한꺼번에 비교한다. 정리된 설명은 Princeton Algorithms 3.4와 VisuAlgo의 해시 표 시각화에 있다.
부하율과 재해시
해시 표가 O(1)인 것은 부하율 α가 작을 때뿐이다. 선형 탐사는 균일한 해시를 가정할 때 있는 키를 찾는 데 평균 약 ½(1 + 1/(1 − α))칸, 없는 키에는 약 ½(1 + 1/(1 − α)²)칸을 본다(Knuth의 분석). α가 0.5면 1.5칸과 2.5칸이지만, 0.9면 5.5칸과 50.5칸이다. 표가 거의 차면 곡선이 수직으로 선다.
그래서 부하율이 기준을 넘으면 재해시(rehashing)한다. 보통 두 배 크기의 표를 새로 잡고, 모든 키의 홈 칸을 새 크기로 다시 계산해 넣는다. 칸 번호가 키 mod 칸 수이므로 옛 칸을 그대로 옮길 수는 없다. 한 번에 O(n)이지만 두 배씩 키우므로 동적 배열과 같은 논리로 넣기 한 번의 분할 상환 비용은 O(1)이다(복잡도와 기초 노트).
기준은 구현마다 다르다. Java HashMap(체이닝)은 0.75, 파이썬 dict(오픈 어드레싱)는 약 2/3에서 키운다. 키를 모두 옮기는 그 한 번이 지연에 민감한 곳에서는 문제가 되므로, 옛 표와 새 표를 함께 두고 연산마다 조금씩 옮기는 점진적 재해시(incremental rehashing)를 쓰기도 한다. Redis가 그렇다. 넣을 개수를 미리 알면 처음부터 크게 잡아 재해시를 아예 피한다.
블룸 필터: 확실히 없음과 아마 있음
때로는 값 자체가 아니라 "이 키를 본 적이 있나"만 알면 된다. 키가 수십억 개라 모두 저장하기 어렵다면? 블룸 필터(Bloom filter)는 비트 m개와 해시 함수 k개로 이 질문에 답한다. 넣을 때는 키의 해시 k개가 가리키는 비트를 모두 켠다. 물을 때는 그 k개 비트가 모두 켜졌는지 본다.
비트 16개가 모두 0인 빈 필터. 키마다 해시 3개로 비트 자리를 고른다.
비트가 하나라도 꺼져 있으면 그 키는 확실히 넣은 적이 없다. 넣었다면 반드시 켰을 테니까. 모두 켜져 있으면 "아마 있음"이다. 다른 키들이 켜 둔 비트가 우연히 겹쳤을 수 있다. 즉 블룸 필터에는 거짓 음성(false negative)이 없고 거짓 양성(false positive)만 있다. 비트를 끄면 다른 키의 비트도 꺼지므로 일반 블룸 필터에서는 지울 수 없다.
키 n개를 넣은 뒤의 거짓 양성 확률은 약 (1 − e−kn/m)k이고, k = (m/n) ln 2일 때 가장 작다. 키 하나에 약 10비트(1.25바이트)를 주면 1%, 약 14.4비트면 0.1%다. 키 길이와 상관없이 이만큼만 든다는 것이 핵심이다. 넣기와 묻기는 해시 k번이라 O(k)다.
쓰임새는 "없음"을 싸게 거르는 곳이다. LevelDB·RocksDB·Cassandra 같은 LSM 트리 저장소는 디스크 파일마다 블룸 필터를 두어, 키가 없는 파일은 디스크를 읽지 않고 건너뛴다. 웹 크롤러가 이미 방문한 주소를 거르거나, 캐시가 한 번만 요청된 항목을 저장하지 않는 데도 쓴다. 지우기가 필요하면 비트 대신 카운터를 두는 카운팅 블룸 필터나 쿠쿠 필터(cuckoo filter)를 쓴다. 비슷한 확률적 자료구조인 HyperLogLog는 더 나아가기 노트에 있다.