해시 테이블은 자리를 계산해서 정한다

앞에서 Dictionary 가 몇 개가 들어 있든 찾는 시간이 거의 같다고 했습니다. 이름을 숫자로 바꿔서 자리를 계산한다고요. 그리고 “거의” 라고 쓴 이유를 한 문단으로 넘겼습니다.

그 안을 열어 봅니다. Dictionary 도 HashSet 도 속에 들어 있는 것은 같은 물건입니다. 해시 테이블(hash table) 이라고 합니다.

해시 테이블은 값을 보고 자리를 계산합니다. 어디 있는지 찾아다니지 않습니다.

순서대로 봅니다. 값을 숫자로 줄이고, 그 숫자로 자리를 정하고, 자리가 겹치면 어떻게 하고, 자리가 모자라면 어떻게 하고, 마지막으로 어떻게 찾는지입니다.

해시 함수는 값을 해시 코드 하나로 줄인다

해시 함수(hash function) 는 아무 값이나 받아서 정해진 크기의 숫자 하나를 돌려줍니다. 그 숫자를 해시 코드(hash code) 라고 합니다.

Console.WriteLine("포션".GetHashCode());
Console.WriteLine(42.GetHashCode());

모든 타입에 GetHashCode 가 있습니다. 돌아오는 것은 int 하나입니다.

문자열이 숫자가 되는 것이 이상해 보이지 않아야 합니다. 앞에서 글자마다 번호가 붙어 있다고 했고, 문자열은 그 번호들이 줄지어 선 것이라고 했습니다. 문자열은 처음부터 숫자 덩어리였습니다. 그 숫자들을 섞어서 하나로 줄이는 것뿐입니다.

해시 함수에 필요한 성질은 두 가지입니다.

• 같은 값이면 항상 같은 해시 코드가 나온다. 이게 깨지면 넣어 둔 것을 못 찾습니다.
• 다른 값이면 되도록 다른 해시 코드가 나온다. 골고루 흩어져야 합니다.

원래 값으로 되돌릴 수 있어야 한다는 조건은 없습니다. int 하나로 줄이는 순간 정보가 버려지니 되돌릴 수도 없습니다. 되돌릴 일도 없습니다. 우리는 자리만 알면 되지 그 자리에서 값을 다시 꺼낼 것이기 때문입니다.

해시 코드를 버킷 개수로 나눈다

GetHashCode 가 주는 것은 int 범위 전체입니다. 약 43억 가지입니다. 칸을 43억 개 만들 수는 없습니다.

그래서 한 번 더 줄입니다. 값이 들어가는 칸 하나를 버킷(bucket) 이라고 하고, 그 버킷이 몇 개인지를 버킷 개수라고 합니다. 해시 코드를 버킷 개수로 나눈 나머지가 자리이고, 그 번호를 버킷 인덱스(bucket index) 라고 합니다.

공식은 이것 하나가 전부입니다.

버킷 인덱스 = 해시 코드 % 버킷 개수

나누기는 이 한 번뿐입니다. 뒤에 다른 계산이 더 붙지 않습니다.

그리고 이 버킷 개수는 언제나 소수입니다. 3, 7, 17, 37, 89 같은 값만 씁니다. 8이나 6은 안 됩니다. 왜 그런지는 바로 아래에서 봅니다.

실제 값을 넣어 보면 이렇습니다.

"포션".GetHashCode()  =  1284739201      ← 키가 만든 숫자
버킷 개수             =  1931            ← 소수

1284739201 % 1931  =  488                →  488번 버킷

Dictionary 가 하는 계산은 이 나머지 하나입니다. 받은 해시 코드를 섞거나 고치지 않습니다. 나누기만 합니다.

어디 있는지 찾아다니는 단계가 없습니다. 계산 한 번이면 자리가 나옵니다.

버킷 개수가 소수여야 하는 이유

해시 코드가 규칙적으로 나오는 경우가 흔합니다. id 가 1씩 늘거나, 좌표가 격자거나, 어설픈 해시 함수가 값 × 16 같은 걸 뱉거나요. 그럴 때 버킷 개수를 잘못 고르면 버킷이 뭉텅이로 놉니다.

4의 배수 여덟 개를 넣어 봅니다.

해시 코드      0    4    8   12   16   20   24   28

버킷 8개       0    4    0    4    0    4    0    4     → 0번과 4번, 두 개만 씀
버킷 7개       0    4    1    5    2    6    3    0     → 일곱 개를 다 씀

버킷이 8개면 그중 두 개만 쓰고 나머지 여섯은 영원히 빕니다. 해시 코드가 4 간격인데 버킷 개수 8이 4를 공약수로 갖고 있어서, 나올 수 있는 나머지가 8 ÷ 4 = 2 가지로 줄어든 것입니다.

7은 소수라 4와 나눠지는 것이 1밖에 없습니다. 그래서 나머지가 안 줄고 일곱 가지가 다 나옵니다.

해시 코드가 일정 간격으로 놓여 있으면, 그 간격과 버킷 개수의 공약수만큼 버킷이 줄어듭니다. 소수는 공약수를 가질 수가 없어서 이 일이 안 생깁니다.

int 의 GetHashCode 가 값을 그대로 돌려주는데도 안전한 이유가 이것입니다. 섞는 일을 해시 함수가 아니라 버킷 개수가 소수라는 사실이 대신 해 줍니다.

쓰는 소수는 미리 정해져 있다

아무 소수나 그때그때 찾는 것이 아닙니다. 표가 코드에 박혀 있고 거기서 고릅니다.

3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, ...
1931, 2333, 2801, ... 17519, ... 156437, ... 1162687, 1395263, ...

담을 개수가 정해지면 그 이상인 첫 소수를 버킷 개수로 씁니다. 100만 개를 담아야 하면 표를 훑다가 1162687 에서 멈춥니다. 뒤에 더 큰 소수도 있지만 안 씁니다. 필요 이상으로 잡으면 메모리만 버리니까요.

표에는 소수가 일흔둘 있고 7199369 에서 끝납니다. 그보다 커지면 표를 벗어나 그 자리에서 소수를 직접 찾습니다. 거기까지 갈 일은 거의 없습니다.

버킷 인덱스가 나오면 그다음은 배열입니다. 버킷들이 줄지어 선 배열을 버킷 배열(bucket array) 이라고 합니다. 앞에서 배열은 몇 번째 칸이든 찾는 시간이 같다고 했는데, 그 성질을 그대로 씁니다.

해시 테이블은 배열 위에 자리 계산을 얹은 것입니다.

서로 다른 값이 같은 버킷에 온다

43억 가지를 버킷 일곱 개에 밀어 넣습니다. 겹칠 수밖에 없습니다. 서로 다른 값이 같은 버킷 인덱스로 계산되는 것을 해시 충돌(hash collision) 이라고 합니다.

피할 수 있는 문제가 아닙니다. 버킷보다 들어올 수 있는 값이 많으면 반드시 생깁니다. 그래서 해시 테이블은 충돌을 없애는 대신 처리하는 방법을 갖고 있습니다.

C# 이 쓰는 방법은 체이닝(chaining) 입니다. 같은 버킷에 온 것들을 그 버킷에 줄줄이 매답니다. 버킷 하나가 값 하나가 아니라 값의 목록을 들고 있는 셈입니다. 버킷마다 따로 목록을 두기 때문에 분리 연쇄법(separate chaining) 이라고도 합니다.

3번 버킷 아래로 줄이 자랍니다. 버킷 개수는 그대로입니다. 늘어난 것은 그 버킷의 줄 길이지 버킷 개수가 아닙니다.

이래서 “거의” 같다고 했던 것입니다. 버킷을 찾아가는 것은 계산 한 번이고, 그 버킷 안에서 한두 번 더 비교합니다. 전체를 훑는 것과는 다릅니다.

적재율이 넘으면 재해싱한다

줄이 길어지면 그만큼 비교가 늘어납니다. 그래서 해시 테이블은 얼마나 찼는지를 봅니다. 이 값을 적재율(load factor) 이라고 합니다.

적재율 = 들어 있는 개수 / 버킷 개수

적재율이 기준을 넘으면 버킷 개수를 늘립니다. List 가 두 배로 늘리던 것과 비슷한데, 결정적으로 다른 것이 하나 있습니다.

버킷 개수가 바뀌면 나머지가 달라집니다.

해시 코드 12       버킷 3개 →  12 % 3 = 0
같은 해시 코드     버킷 7개 →  12 % 7 = 5

왼쪽은 그대로고 오른쪽만 바뀌었습니다. GetHashCode 는 한 번도 안 불렸는데 자리가 달라집니다. 그래서 늘릴 때 들어 있는 것을 전부 다시 계산해서 재배치해야 합니다. 이 작업을 재해싱(rehashing) 이라고 합니다.

늘릴 때도 소수를 지킵니다. 지금 버킷 개수를 두 배로 잡은 뒤, 그 이상인 첫 소수로 올립니다. 앞에서 본 소수 표를 한 칸씩 올라가는 셈입니다.

3 → 7 → 17 → 37 → 89 → 197 → 431 → 919 → 1931 → 4049 → ...
... → 156437 → 324449 → 672827 → 1395263

값 백만 개를 넣으면 이 사다리를 열일곱 칸 올라갑니다. 그동안 키의 해시 코드는 한 번도 안 바뀌고, 버킷 개수만 계속 커집니다.

1284739201 % 3        =  1
1284739201 % 1931     =  488
1284739201 % 1395263  =  1097241

같은 키가 1번 버킷에 있다가 488번으로, 다시 1097241번으로 옮겨 다닙니다. 재해싱이 비싼 이유가 이것입니다. 값을 옮기는 게 아니라 전부의 나머지를 다시 구해야 합니다.

0번 버킷에 매달려 있던 포션과 활이 갈라집니다. 늘리는 목적이 이것입니다.

List 는 값을 그대로 옮기기만 하면 됐는데 여기는 자리를 다시 정합니다. 담긴 개수만큼 계산이 다시 듭니다. 그래서 담을 개수를 짐작할 수 있으면 처음부터 알려주는 편이 낫습니다.

Dictionary<string, int> prices = new Dictionary<string, int>(1000);

이득이 둘입니다. 백만 개를 담는 경우로 재 보면 이렇습니다.

재해싱이 사라지고, 버킷도 덜 잡습니다. 사다리를 두 배씩 밟고 올라가면 마지막 한 칸에서 넘겨 잡게 되는데, 처음부터 알려주면 필요한 만큼만 잡습니다. 23만 개가 덜 듭니다.

그러면 줄은 계속 길어지는가

체이닝은 한 버킷에 목록을 매답니다. 값을 계속 넣으면 그 줄이 끝없이 길어질까요.

보통은 아닙니다. 방금 본 재해싱이 막습니다. 값이 늘면 적재율이 올라가고, 기준을 넘으면 버킷 개수가 늘어납니다. 버킷이 늘면 줄이 다시 흩어집니다. 값과 버킷이 같이 늘어나니 평균 줄 길이는 거의 그대로입니다.

다만 조건이 있습니다. 해시 코드가 고르게 나와야 합니다. 값 다섯 개를 같은 순서로 넣으면서 해시 코드만 바꿔 봅니다.

왼쪽은 버킷이 7개로 늘면서 다섯 값이 다섯 자리로 흩어집니다. 가장 긴 줄이 1입니다. 오른쪽은 늘려도 그대로입니다. 버킷을 늘린 보람이 없습니다. 가장 긴 줄이 5입니다.

적재율은 둘 다 0.71 로 같습니다. 여기가 핵심입니다.

재해싱은 줄이 길어서 도는 게 아니라 적재율이 높아서 돕니다.

오른쪽도 재해싱은 돌았습니다. 적재율이 기준을 넘었으니까요. 버킷도 3개에서 7개로 늘었습니다. 그런데 줄은 그대로입니다. 0, 21, 42, 63, 84 는 3으로 나눠도 7로 나눠도 나머지가 0이라 갈 곳이 같습니다.

재해싱이 안 도는 것이 아니라 돌아도 소용이 없는 것입니다. 버킷 배열만 커지고, 전부 다시 계산하는 비용은 다 내고, 줄은 하나도 안 짧아집니다.

해시 코드가 나쁘면 줄은 실제로 계속 길어집니다. 해시 테이블이 무너지는 길은 이것 하나입니다.

재해싱은 고르게 만드는 게 아니라 짧게 만든다

여기서 말을 정확히 해야 합니다. 두 가지가 섞이기 쉽습니다.

같은 값 백만 개를 넣으면서 버킷 개수만 바꿔 보면 이렇습니다.

1,931개일 때도 이미 고릅니다. 모든 버킷을 쓰고 있고 평균 518에 최대 595니 쏠림이 없습니다. 고른데 줄이 518인 것뿐입니다.

버킷을 늘려도 고름의 정도는 그대로입니다. 줄어드는 것은 길이입니다.

재해싱은 이미 고른 것을 넓게 펴서 얇게 만듭니다. 쏠린 것을 펴는 기능은 없습니다. 그래서 오른쪽 탭이 안 풀렸던 것입니다.

C# 은 문자열에만 장치를 하나 더 둔다

문자열 키는 밖에서 들어온 값일 때가 많습니다. 사용자가 보낸 이름, 주소, 요청 값 같은 것들입니다. 누군가 같은 버킷으로 가는 문자열만 골라서 보내면 줄이 길어지고 서버가 느려집니다.

그래서 Dictionary 는 한 줄에서 100번 넘게 비교하게 되면 해시 함수를 바꿉니다. 버킷 개수는 그대로 두고 무작위 해시로 다시 계산합니다.

// dotnet/runtime 의 Dictionary.cs, TryInsert 안
if (!typeof(TKey).IsValueType &&
    collisionCount > HashHelpers.HashCollisionThreshold &&
    comparer is NonRandomizedStringEqualityComparer)
{
    Resize(entries.Length, true);   // 버킷 개수는 그대로, 해시만 새로
}

HashCollisionThreshold 가 100 입니다. Resize 의 첫 인자가 지금 버킷 개수 그대로이고, 둘째 인자가 해시를 새로 계산하라는 뜻입니다. 늘리는 재해싱이 아니라 흩는 재해싱입니다. 같은 문자열이라도 실행할 때마다 다른 해시가 나오니 미리 골라 오는 것이 안 통하게 됩니다.

조건을 보면 안 도는 경우도 보입니다. 값 타입 키에는 안 돕니다. 직접 만든 참조 타입도 안 돕니다. 문자열에만 걸어 둔 장치입니다.

찾을 때도 같은 계산을 한다

여기까지가 넣는 쪽입니다. 찾는 쪽은 같은 계산을 한 번 더 하는 것이 전부입니다. 해시 코드를 구하고, 버킷 개수로 나누고, 그 버킷 안에서만 비교합니다.

두 가지가 보입니다.

• 해시 코드는 버킷을 좁히는 데까지만 씁니다. 같은 버킷에 왔다고 같은 값이 아닙니다. 최종 판단은 비교가 합니다. 그래서 버킷 안에서 하나씩 맞춰 봅니다.
• 없는 값을 찾을 때도 그 버킷만 봅니다. 3번 버킷에 없으면 없는 것입니다. 있었다면 3번에 있어야 하니까요. 다른 버킷을 훑을 이유가 없습니다.

얼마나 빠른가

담긴 개수를 올려도 해시 테이블 쪽은 안 움직입니다. 적재율만 봅니다. 적재율은 재해싱으로 관리하니 결국 개수와 상관없이 일정하게 유지됩니다.

평균 O(1), 최악 O(N)

지금까지 본 것에는 이름이 있습니다.

O 는 담긴 개수가 늘 때 비용이 어떻게 늘어나는지를 적는 표기입니다. O(1) 은 안 늘어난다, O(N) 은 개수에 비례해서 늘어난다는 뜻입니다.

해시 테이블은 평균 O(1) 입니다. 계산 한 번으로 버킷을 찾고 그 안에서 한두 번 비교합니다.

최악은 O(N) 입니다. 앞에서 본, 모든 값이 한 버킷으로 몰린 경우입니다. 그 줄을 처음부터 훑게 되니 List 와 똑같아집니다.

실제로 재 보면 이렇습니다. GetHashCode 가 항상 0을 돌려주는 키를 넣은 것입니다.

가장 긴 줄이 담긴 개수와 같습니다. 그리고 개수를 두 배로 하면 시간도 두 배가 됩니다. 이게 O(N) 입니다.

평균이 O(1) 이 되는 조건이 둘이라는 것도 이제 보입니다.

• 해시 코드가 고르게 나와야 합니다.
• 적재율이 기준 아래로 관리돼야 합니다.

둘 중 하나가 깨지면 평균이 최악 쪽으로 끌려갑니다. 적재율은 재해싱이 알아서 관리합니다. 남는 건 해시 코드입니다. int 나 string 처럼 자주 쓰는 타입은 잘 만들어져 있으니 걱정할 것이 없습니다. 직접 만든 타입을 키로 쓸 때가 문제입니다.

직접 만든 타입을 키로 쓸 때

앞에서 HashSet 에 직접 만든 타입을 담으면 내용이 같아도 다른 것으로 본다고 했습니다. 이유가 이제 보입니다.

찾는 과정에서 봤듯이, 해시 테이블이 두 값을 같다고 판단하려면 두 가지가 맞아야 합니다.

• 해시 코드가 같아야 같은 버킷으로 갑니다.
• 그 버킷 안에서 비교했을 때 같다고 나와야 합니다.

그래서 규칙이 하나 나옵니다. GetHashCode 와 Equals 의 계약 이라고 부릅니다.

같다고 볼 두 값은 반드시 같은 해시 코드를 내놓아야 합니다.

반대는 성립하지 않습니다. 해시 코드가 같아도 다른 값일 수 있습니다. 그게 해시 충돌입니다. 그러니 해시 코드는 버킷을 좁히는 데까지만 쓰고, 최종 판단은 Equals 가 합니다.

아무것도 안 하면 직접 만든 타입은 내용이 아니라 만들어진 개체 단위로 판단합니다. 내용이 같아도 따로 만든 것이면 다른 값입니다.

한 가지 더 있습니다. 키로 쓴 값을 나중에 바꾸면 안 됩니다. 넣을 때 계산한 버킷에 놓여 있는데, 값이 바뀌면 해시 코드도 바뀝니다. 그러면 새 해시 코드로 계산한 버킷에는 그게 없습니다. 넣어 두고도 못 찾습니다.

키는 안 바뀌는 값으로 씁니다. 숫자, 문자열, enum 이 키로 자주 쓰이는 이유입니다.

그래서 어떻게 만드나

직접 쓰지 않는 것이 답입니다. record 로 선언하면 컴파일러가 만들어 줍니다.

public readonly record struct Cell(int X, int Y);

Equals 와 GetHashCode 가 값 기준으로 같이 생깁니다. 계약도 저절로 지켜집니다.

record 를 못 쓰는 자리면 HashCode.Combine 을 씁니다.

public override int GetHashCode() => HashCode.Combine(X, Y);

직접 쓸 때 지킬 것은 셋입니다.

• Equals 에서 쓰는 필드를 전부, 그리고 그것만 섞습니다
• ^ 나 + 만 쓰지 않습니다. 둘 다 순서를 구분 못 해서 (1, 2) 와 (2, 1) 이 같아집니다
• 안 바뀌는 필드만 씁니다

64×64 격자 좌표 4096개를 키로 넣고 조합 방식만 바꿔 재 보면 차이가 이렇게 납니다. 버킷 개수는 4099로 같습니다.

^ 만 쓰면 4096개가 버킷 64개에만 들어갑니다. 나머지는 영원히 빕니다. 소수인 버킷 개수도 재해싱도 이건 못 구합니다. 애초에 서로 다른 해시 코드가 안 나왔으니까요.

누가 무엇을 책임지나

마지막 줄만 조심하면 나머지는 신경 쓸 일이 없습니다.

다른 방법도 있다: 개방 주소법

여기까지가 C# 의 해시 테이블입니다. 충돌을 처리하는 방법이 하나 더 있습니다.

개방 주소법(open addressing) 은 아예 안 매답니다. 버킷이 차 있으면 다른 빈 버킷을 찾아 거기 넣습니다. 값이 자기 버킷이 아닌 곳에 앉을 수 있으니 “주소가 열려 있다” 는 이름이 붙었습니다. 빈 버킷을 한 칸씩 옆으로 찾아가는 방식을 선형 탐사(linear probing) 라고 합니다.

같은 값을 같은 순서로 넣으면서 방식만 바꿔 봅니다.

물약이 4번으로, 반지가 0번까지 밀립니다. 반지는 빈 자리를 찾느라 네 번 옆을 봤습니다. 자기 자리 근처가 이미 차 있으면 그 덩어리를 통째로 지나가야 하는데, 이렇게 값이 한쪽에 뭉치는 것을 군집화(clustering) 라고 합니다. 선형 탐사의 고질적인 약점입니다.

지우는 것도 다릅니다. 값을 지우고 그 버킷을 그냥 비우면, 뒤로 밀려 있던 값들이 통째로 안 보이게 됩니다. 찾을 때 빈 버킷을 만나면 없다고 판단하고 멈추기 때문입니다. 그래서 지운 자리에는 비었다는 표시가 아니라 지웠다는 표시를 남깁니다. 이 표시를 톰스톤(tombstone) 이라고 합니다. 찾을 때는 지나가고, 넣을 때는 쓸 수 있는 자리입니다.

무엇을 얻고 무엇을 잃는가

한 줄로 줄이면 체이닝은 안정적이고, 개방 주소법은 조건이 맞으면 더 빠릅니다.

C# 이 체이닝을 고른 이유가 여기 있습니다. 어떤 용도로 쓰일지 모르는 표준 라이브러리라 안정적인 쪽을 골랐습니다. 개방 주소법은 조건을 직접 통제할 수 있는 자리에서 씁니다. Span 을 직접 굴리는 고성능 코드나, 그런 선택을 한 다른 언어의 표준 라이브러리에서 만납니다. 둘 중 무엇이 맞다가 아니라, 무엇을 포기했느냐가 다릅니다.

정리

• 해시 테이블은 값을 보고 자리를 계산합니다. 찾아다니지 않습니다.
• 해시 함수가 값을 해시 코드 하나로 줄입니다. 같은 값이면 항상 같은 해시 코드여야 합니다.
• 버킷 인덱스 = 해시 코드 % 버킷 개수. 나누기는 이 한 번뿐입니다.
• 버킷 개수는 언제나 소수입니다. 해시 코드가 규칙적이어도 소수로 나누면 고르게 퍼집니다.
• 버킷보다 값의 가짓수가 많으니 해시 충돌은 반드시 생깁니다. C# 은 체이닝으로 그 버킷에 매답니다.
• 적재율이 기준을 넘으면 버킷 개수를 다음 소수로 늘리고 전부 다시 계산합니다.
• 담을 개수를 짐작할 수 있으면 처음부터 알려주세요. 재해싱이 사라지고 버킷도 덜 잡습니다.
• 재해싱은 고르게 만드는 게 아니라 짧게 만듭니다. 고르게 만드는 것은 해시 코드와 소수인 버킷 개수입니다.
• 그래서 해시 코드가 나쁘면 늘려도 소용없습니다. 줄이 실제로 계속 길어집니다.
• 문자열 키는 한 줄에서 100번 넘게 충돌하면 C# 이 무작위 해시로 바꿔 다시 흩습니다.
• 찾을 때도 같은 계산을 합니다. 그 버킷만 보고, 없으면 없는 것입니다.
• 담긴 개수가 늘어도 찾는 비용이 거의 안 늘어납니다. 평균 O(1) 입니다. 한 버킷에 다 몰리면 최악 O(N) 입니다.
• GetHashCode 와 Equals 는 계약 관계입니다. 키로 쓴 값은 나중에 바꾸면 안 됩니다.
• 직접 만든 타입은 record 로 선언하면 끝입니다. 구멍은 GetHashCode 를 직접 쓸 때만 열립니다.
• 충돌 처리에는 개방 주소법도 있습니다. 캐시에 유리한 대신 적재율이 1을 못 넘고 군집화와 톰스톤을 떠안습니다.