📚 지식 노트

첫 글자 해시는 1번 칸에 8개가 모두 몰리고, 다항식 해시는 칸마다 2개씩 고르게 나뉜다. i의 코드 105를 4로 나눈 나머지가 1이라 모든 키가 1번 칸으로 간다.

첫 글자 해시는 키의 일부만 보므로, 키가 다른 곳(끝 숫자)에서만 달라지면 구별하지 못한다. 실제 키는 같은 접두사를 공유하는 일이 흔하다. 그러면 칸 하나에 모두 몰려 찾기가 O(n)이 된다. 좋은 해시는 키의 모든 글자를 결과에 섞는다.

h는 97, 3105, 96354로 바뀌고, 96354 mod 8 = 2번 칸이다. 0 × 31 + 97 = 97, 97 × 31 + 98 = 3105, 3105 × 31 + 99 = 96354다.

"cab"의 다항식 해시는 98244로 8로 나누면 4번 칸이라 "abc"와 갈린다. 글자 코드를 그냥 더하면 둘 다 97 + 98 + 99 = 294로 같아 같은 칸(6번)에 충돌한다. 더하기는 순서를 보지 못하므로, 같은 글자로 된 다른 키(애너그램)가 모두 부딪힌다. 31을 곱하는 것은 글자의 위치를 결과에 새기기 위해서다.

칸 8개면 모두 0번 칸에 몰리고, 칸 7개면 0~6번에 고르게 흩어진다(0번만 2개).

키의 간격(8)과 칸 수가 공약수를 가지면 일부 칸만 쓰인다. 8과 7처럼 서로소면 키가 칸을 골고루 돈다. 그래서 단순한 mod 해시는 칸 수를 소수로 잡곤 한다. 칸 수를 2의 거듭제곱으로 두는 구현(빠른 비트 AND를 쓰려고)은 대신 해시 값을 잘 섞어 아래 비트에도 키의 모든 정보가 퍼지게 한다.

20은 3번, 25는 3번, 4는 0번이고, 부하율은 6 / 5 = 1.2다. 20은 0번 칸 목록의 세 번째라 10, 15, 20과 비교한다. 25도 0번 칸이라 목록 셋을 모두 보고 나서야 없다고 안다. 4는 4번 칸이 비어 있어 비교 없이 바로 없다고 답한다.

평균 목록 길이는 1.2지만, 키가 0번과 3번 칸에만 몰려 실제 목록은 3이다. 부하율은 해시가 고르다는 가정에서만 비용을 알려 준다. 이 키들은 모두 5로 나눈 나머지가 0이나 3이라 mod 5와 궁합이 나쁘다.

0번 칸에 5, 1번 칸에 21 → 16 → 11, 3번 칸에 8 → 13이 매달린다. 충돌은 3번(13, 16, 11), 가장 긴 목록은 1번 칸의 3개다.

11은 1번 칸에 이미 둘이 있어 충돌 두 개째다. 넣기 자체는 목록 끝(또는 앞)에 붙이면 되지만, 같은 키가 이미 있는지 확인하려면 그 목록을 훑어야 한다. 그래서 넣기도 목록 길이에 비례한다.

0 + 1 + … + (n − 1) = n(n − 1)/2번이고, n = 1,000이면 499,500번이다. k번째 키를 넣을 때 목록에 이미 k − 1개가 있어 모두와 비교한다. 해시 표가 연결 리스트로 무너져 넣기 한 번이 O(n), 전체가 O(n²)이 된다. 고르게 흩어졌다면 약 1,000번이면 됐다.

이것이 해시 폭탄(hash flooding)이다. 막는 방법은 공격자가 칸을 예측하지 못하게 하는 것이다. 파이썬과 Rust는 프로세스마다 무작위 비밀 값을 섞는 SipHash 계열을 쓴다. Java HashMap은 긴 목록을 균형 트리로 바꿔 최악을 O(log n)으로 묶는다. 요청 하나에 받는 키의 수를 제한하는 것도 함께 쓴다.

17이 표에 있는데도 "없다"고 답한다. 17의 홈 칸 3에는 3이 있어 4번 칸으로 가는데, 그 칸이 비어 있으니 탐사가 멈춘다. 빈 칸은 "이 키는 여기까지 오지 않았다"는 뜻이기 때문이다.

그래서 지운 칸에는 묘비(tombstone)를 세운다. 찾기는 묘비를 지나가고, 넣기는 키가 없음을 확인한 뒤 묘비 자리를 다시 쓴다. 체이닝에서는 목록에서 빼기만 하면 되므로 이런 문제가 없다.

마지막 표는 0번 19, 1번 6, 5번 5, 6번 26이다. 찾기 19는 3칸, 넣기 26은 5칸을 본다.

19는 5(키 5) → 6(묘비, 지나감) → 0에서 찾는다. 26은 5 → 6(묘비) → 0(19) → 1(6) → 2(빈 칸)까지 가서 26이 없음을 확인한 뒤, 지나온 첫 묘비인 6번 칸에 넣는다. 묘비에서 바로 넣지 않는 것은 26이 더 뒤에 이미 있을 수 있기 때문이다. 6은 홈 칸 6이 12에게 차지되어 있어 두 칸을 밀려났다. 서로 다른 홈 칸의 키도 한 덩어리로 엉킨다.

7번 칸은 60%, 0번 칸은 10%다. 홈 칸이 2~6이면 덩어리 끝까지 밀려 7번에 앉고, 7이면 바로 앉는다. 10개 중 6개가 7번으로 간다. 0번에는 홈 칸이 0일 때만 앉는다.

덩어리 바로 뒤 칸은 그만큼 빨리 차고, 차면 덩어리가 더 커져 다음 키를 더 많이 끌어들인다. 이것이 뭉침(primary clustering)이다. 덩어리가 클수록 찾기가 그 길이만큼 길어진다. 제곱 탐사나 이중 해싱은 충돌한 키를 서로 다른 보폭으로 흩어 이 되먹임을 끊는다.

부하율 0.75에서 없는 키 8.5칸, 있는 키 2.5칸이다. 32칸으로 키우면 부하율 0.375에서 약 1.78칸과 1.3칸으로 준다. 없는 키는 ½(1 + 1/(1 − α)²) = ½(1 + 16) = 8.5, 있는 키는 ½(1 + 1/(1 − α)) = ½(1 + 4) = 2.5다.

칸 수를 두 배로 하면 메모리는 두 배지만 없는 키 찾기는 다섯 배 가까이 빨라진다. 없는 키 찾기는 넣기마다 한 번씩 하는 일(중복 확인)이라 이 값이 넣기 비용을 정한다. 그래서 선형 탐사 표는 부하율이 0.7 언저리를 넘기 전에 키운다.

19는 5번, 26은 12번, 5는 6번, 12는 13번 칸이다. 밀려난 키는 3개(19, 26, 12)에서 2개(5, 12)로 준다.

읽는 순서대로 19(19 mod 14 = 5), 26(12), 5(5, 이미 19가 있어 6), 12(12, 이미 26이 있어 13)를 넣는다. 칸 번호가 키 mod 칸 수라서 옛 칸을 그대로 옮길 수 없고 모든 키의 홈 칸을 새로 계산해야 한다. 옛 표에서 같은 칸을 노리던 키들이 새 표에서는 5번과 12번 두 무리로 갈라진다. 넣는 순서에 따라 누가 밀려날지는 달라진다.

재해시는 5번, 옮기는 키는 모두 186개, 넣기 한 번당 1.86개다.

6 + 12 + 24 + 48 + 96 = 186이다. 옮기는 양이 두 배씩 느는 등비수열이라 합이 마지막 항(96)의 두 배를 넘지 않고, 그 마지막 항도 넣은 키 수보다 작다. 그래서 동적 배열처럼 넣기 한 번의 분할 상환 비용이 O(1)이다. 다만 97번째 넣기 한 번은 96개를 옮기느라 느리다. 지연에 민감한 곳에서는 Redis처럼 연산마다 조금씩 옮기는 점진적 재해시를 쓴다.

z는 "아마 있음"(거짓 양성), w는 "확실히 없음"이다. z의 1, 2, 7번은 x와 y가 켜 둔 비트라 모두 켜져 있다. w의 3번은 꺼져 있어, 넣었다면 반드시 켰을 비트가 꺼진 것이니 확실히 없다.

x를 지우려고 비트를 끄면 y가 "없음"으로 바뀐다. 4번 비트는 x와 y가 함께 쓰기 때문이다. 블룸 필터가 약속하는 "거짓 음성 없음"이 깨지므로 일반 블룸 필터는 지우지 않는다. 지우기가 필요하면 비트 대신 개수를 세는 카운팅 블룸 필터를 쓴다.

bee는 아마 있음(맞음), cow는 확실히 없음, gnu는 거짓 양성이다. gnu의 7번은 elk가, 6번은 ant가, 5번은 bee가 켜 두었다.

cow는 0번과 11번이 꺼져 있다. 하나만 꺼져 있어도 충분하다. 키 셋이 비트 16개 중 7개(2, 4, 5, 6, 7, 13, 15)를 켜 두어 거의 절반이 켜졌으니, 아무 키나 세 자리가 모두 켜졌을 확률이 꽤 크다. 비트 수에 비해 키가 많아질수록 거짓 양성이 빠르게 는다.

비트 약 958만 개(키당 약 9.6비트, 약 1.2MB)와 해시 7개다. 최적 비트 수는 m = −n ln p / (ln 2)² ≈ 9,585,059개, 최적 해시 수는 k = (m/n) ln 2 ≈ 6.6이라 7개로 올린다.

표처럼 키당 10비트면 k = 7에서 0.82%로 가장 낮다. 해시가 너무 적으면 비트 몇 개만 겹쳐도 걸리고, 너무 많으면 비트가 빨리 차서 오히려 나빠진다. 키가 32바이트 문자열이라면 그대로 저장하는 데 32MB가 드는데, 블룸 필터는 키 길이와 상관없이 1.2MB면 된다. 대신 "있음"은 늘 "아마"다.