--- title: "해시 테이블은 자리를 계산해서 정한다" description: "Dictionary 와 HashSet 이 곧장 찾는 이유입니다. 해시 코드를 버킷 개수로 나눈 나머지가 자리이고, 그 버킷 개수는 언제나 소수입니다. 겹치면 어떻게 되고 줄은 어디까지 길어지는지까지 봅니다." author: "유니얼" pubDate: 2026-09-08 updatedDate: 2026-09-17 category: "programming/csharp/collections" tags: ["C#", "자료구조"] canonical: https://blog.unialgames.com/posts/csharp-hash-table/ --- 앞에서 `Dictionary` 가 몇 개가 들어 있든 찾는 시간이 거의 같다고 했습니다. 이름을 숫자로 바꿔서 자리를 계산한다고요. 그리고 "거의" 라고 쓴 이유를 한 문단으로 넘겼습니다. 그 안을 열어 봅니다. `Dictionary` 도 `HashSet` 도 속에 들어 있는 것은 같은 물건입니다. **해시 테이블**(hash table) 이라고 합니다. > **해시 테이블은 값을 보고 자리를 계산합니다. 어디 있는지 찾아다니지 않습니다.** 순서대로 봅니다. 값을 숫자로 줄이고, 그 숫자로 자리를 정하고, 자리가 겹치면 어떻게 하고, 자리가 모자라면 어떻게 하고, 마지막으로 어떻게 찾는지입니다. ## 해시 함수는 값을 해시 코드 하나로 줄인다 **해시 함수**(hash function) 는 아무 값이나 받아서 정해진 크기의 숫자 하나를 돌려줍니다. 그 숫자를 **해시 코드**(hash code) 라고 합니다. ```csharp Console.WriteLine("포션".GetHashCode()); Console.WriteLine(42.GetHashCode()); ``` 모든 타입에 `GetHashCode` 가 있습니다. 돌아오는 것은 `int` 하나입니다. 문자열이 숫자가 되는 것이 이상해 보이지 않아야 합니다. 앞에서 글자마다 번호가 붙어 있다고 했고, 문자열은 그 번호들이 줄지어 선 것이라고 했습니다. **문자열은 처음부터 숫자 덩어리였습니다.** 그 숫자들을 섞어서 하나로 줄이는 것뿐입니다. 해시 함수에 필요한 성질은 두 가지입니다. - **같은 값이면 항상 같은 해시 코드가 나온다.** 이게 깨지면 넣어 둔 것을 못 찾습니다. - **다른 값이면 되도록 다른 해시 코드가 나온다.** 골고루 흩어져야 합니다. 원래 값으로 되돌릴 수 있어야 한다는 조건은 없습니다. `int` 하나로 줄이는 순간 정보가 버려지니 되돌릴 수도 없습니다. 되돌릴 일도 없습니다. 우리는 **자리만 알면 되지** 그 자리에서 값을 다시 꺼낼 것이기 때문입니다. ## 해시 코드를 버킷 개수로 나눈다 `GetHashCode` 가 주는 것은 `int` 범위 전체입니다. 약 43억 가지입니다. 칸을 43억 개 만들 수는 없습니다. 그래서 한 번 더 줄입니다. 값이 들어가는 칸 하나를 **버킷**(bucket) 이라고 하고, 그 버킷이 몇 개인지를 **버킷 개수**라고 합니다. 해시 코드를 버킷 개수로 나눈 나머지가 자리이고, 그 번호를 **버킷 인덱스**(bucket index) 라고 합니다. **공식은 이것 하나가 전부입니다.** ``` 버킷 인덱스 = 해시 코드 % 버킷 개수 ``` 나누기는 이 한 번뿐입니다. 뒤에 다른 계산이 더 붙지 않습니다. | | 무엇인가 | 누가 정하나 | | --- | --- | --- | | **해시 코드** | `key.GetHashCode()` 가 돌려준 `int` | 키 타입 | | **버킷 개수** | 버킷이 몇 개인가 | `Dictionary` | **그리고 이 버킷 개수는 언제나 소수입니다.** 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` 는 값을 그대로 옮기기만 하면 됐는데 여기는 **자리를 다시 정합니다.** 담긴 개수만큼 계산이 다시 듭니다. 그래서 담을 개수를 짐작할 수 있으면 처음부터 알려주는 편이 낫습니다. ```csharp Dictionary prices = new Dictionary(1000); ``` 이득이 둘입니다. 백만 개를 담는 경우로 재 보면 이렇습니다. | | 버킷 개수 | 재해싱 | 적재율 | | --- | --- | --- | --- | | 그냥 넣기 | 1,395,263 | **17번** | 0.72 | | 개수를 알려주고 넣기 | **1,162,687** | **0번** | 0.86 | **재해싱이 사라지고, 버킷도 덜 잡습니다.** 사다리를 두 배씩 밟고 올라가면 마지막 한 칸에서 넘겨 잡게 되는데, 처음부터 알려주면 필요한 만큼만 잡습니다. 23만 개가 덜 듭니다. ## 그러면 줄은 계속 길어지는가 체이닝은 한 버킷에 목록을 매답니다. 값을 계속 넣으면 그 줄이 끝없이 길어질까요. **보통은 아닙니다. 방금 본 재해싱이 막습니다.** 값이 늘면 적재율이 올라가고, 기준을 넘으면 버킷 개수가 늘어납니다. 버킷이 늘면 줄이 다시 흩어집니다. 값과 버킷이 같이 늘어나니 **평균 줄 길이는 거의 그대로**입니다. 다만 조건이 있습니다. 해시 코드가 고르게 나와야 합니다. 값 다섯 개를 같은 순서로 넣으면서 해시 코드만 바꿔 봅니다.

왼쪽은 버킷이 7개로 늘면서 다섯 값이 다섯 자리로 흩어집니다. 가장 긴 줄이 1입니다. 오른쪽은 늘려도 그대로입니다. **버킷을 늘린 보람이 없습니다.** 가장 긴 줄이 5입니다. **적재율은 둘 다 0.71 로 같습니다.** 여기가 핵심입니다. > **재해싱은 줄이 길어서 도는 게 아니라 적재율이 높아서 돕니다.** 오른쪽도 재해싱은 돌았습니다. 적재율이 기준을 넘었으니까요. 버킷도 3개에서 7개로 늘었습니다. **그런데 줄은 그대로입니다.** 0, 21, 42, 63, 84 는 3으로 나눠도 7로 나눠도 나머지가 0이라 갈 곳이 같습니다. **재해싱이 안 도는 것이 아니라 돌아도 소용이 없는 것**입니다. 버킷 배열만 커지고, 전부 다시 계산하는 비용은 다 내고, 줄은 하나도 안 짧아집니다. **해시 코드가 나쁘면 줄은 실제로 계속 길어집니다.** 해시 테이블이 무너지는 길은 이것 하나입니다. ### 재해싱은 고르게 만드는 게 아니라 짧게 만든다 여기서 말을 정확히 해야 합니다. 두 가지가 섞이기 쉽습니다. 같은 값 백만 개를 넣으면서 **버킷 개수만** 바꿔 보면 이렇습니다. | 버킷 개수 | 평균 줄 | 가장 긴 줄 | 쓴 버킷 비율 | | --- | --- | --- | --- | | 1,931 | 517.9 | 595 | 100% | | 17,519 | 57.1 | 88 | 100% | | 156,437 | 6.4 | 21 | 100% | | 1,395,263 | 0.7 | **8** | 51% | **1,931개일 때도 이미 고릅니다.** 모든 버킷을 쓰고 있고 평균 518에 최대 595니 쏠림이 없습니다. 고른데 줄이 518인 것뿐입니다. 버킷을 늘려도 고름의 정도는 그대로입니다. 줄어드는 것은 **길이**입니다. | | 무슨 뜻인가 | 누가 하는가 | | --- | --- | --- | | **고르게** | 한쪽으로 안 쏠린다 | 키의 `GetHashCode` 와 소수인 버킷 개수 | | **짧게** | 한 줄에 몇 개 없다 | **재해싱** | 재해싱은 이미 고른 것을 **넓게 펴서 얇게** 만듭니다. 쏠린 것을 펴는 기능은 없습니다. 그래서 오른쪽 탭이 안 풀렸던 것입니다. ### C# 은 문자열에만 장치를 하나 더 둔다 문자열 키는 밖에서 들어온 값일 때가 많습니다. 사용자가 보낸 이름, 주소, 요청 값 같은 것들입니다. 누군가 같은 버킷으로 가는 문자열만 골라서 보내면 줄이 길어지고 서버가 느려집니다. 그래서 `Dictionary` 는 **한 줄에서 100번 넘게 비교하게 되면 해시 함수를 바꿉니다.** 버킷 개수는 그대로 두고 무작위 해시로 다시 계산합니다. ```csharp // dotnet/runtime 의 Dictionary.cs, TryInsert 안 if (!typeof(TKey).IsValueType && collisionCount > HashHelpers.HashCollisionThreshold && comparer is NonRandomizedStringEqualityComparer) { Resize(entries.Length, true); // 버킷 개수는 그대로, 해시만 새로 } ``` `HashCollisionThreshold` 가 100 입니다. `Resize` 의 첫 인자가 지금 버킷 개수 그대로이고, 둘째 인자가 해시를 새로 계산하라는 뜻입니다. **늘리는 재해싱이 아니라 흩는 재해싱**입니다. 같은 문자열이라도 실행할 때마다 다른 해시가 나오니 미리 골라 오는 것이 안 통하게 됩니다. 조건을 보면 안 도는 경우도 보입니다. **값 타입 키에는 안 돕니다. 직접 만든 참조 타입도 안 돕니다.** 문자열에만 걸어 둔 장치입니다. ## 찾을 때도 같은 계산을 한다 여기까지가 넣는 쪽입니다. 찾는 쪽은 **같은 계산을 한 번 더 하는 것**이 전부입니다. 해시 코드를 구하고, 버킷 개수로 나누고, 그 버킷 안에서만 비교합니다. 두 가지가 보입니다. - **해시 코드는 버킷을 좁히는 데까지만 씁니다.** 같은 버킷에 왔다고 같은 값이 아닙니다. 최종 판단은 비교가 합니다. 그래서 버킷 안에서 하나씩 맞춰 봅니다. - **없는 값을 찾을 때도 그 버킷만 봅니다.** 3번 버킷에 없으면 없는 것입니다. 있었다면 3번에 있어야 하니까요. 다른 버킷을 훑을 이유가 없습니다. ## 얼마나 빠른가 **담긴 개수를 올려도 해시 테이블 쪽은 안 움직입니다.** 적재율만 봅니다. 적재율은 재해싱으로 관리하니 결국 개수와 상관없이 일정하게 유지됩니다. | | 있는지 찾기 | 개수가 늘면 | | --- | --- | --- | | 배열 · `List` 에서 내용으로 | 전부 훑는다 | 그만큼 느려진다 | | 해시 테이블 | 계산해서 그 버킷만 | 거의 그대로 | ## 평균 O(1), 최악 O(N) 지금까지 본 것에는 이름이 있습니다. `O` 는 담긴 개수가 늘 때 비용이 어떻게 늘어나는지를 적는 표기입니다. **O(1)** 은 안 늘어난다, **O(N)** 은 개수에 비례해서 늘어난다는 뜻입니다. 해시 테이블은 **평균 O(1)** 입니다. 계산 한 번으로 버킷을 찾고 그 안에서 한두 번 비교합니다. **최악은 O(N)** 입니다. 앞에서 본, 모든 값이 한 버킷으로 몰린 경우입니다. 그 줄을 처음부터 훑게 되니 `List` 와 똑같아집니다. 실제로 재 보면 이렇습니다. `GetHashCode` 가 항상 0을 돌려주는 키를 넣은 것입니다. | 담긴 개수 | 가장 긴 줄 | 한 건 찾는 데 | | --- | --- | --- | | 1,000 | 1,000 | 6.9µs | | 2,000 | 2,000 | 13.4µs | | 4,000 | 4,000 | 22.2µs | | 8,000 | 8,000 | 64.0µs | | 16,000 | 16,000 | 81.0µs | **가장 긴 줄이 담긴 개수와 같습니다.** 그리고 개수를 두 배로 하면 시간도 두 배가 됩니다. 이게 O(N) 입니다. 평균이 O(1) 이 되는 **조건이 둘**이라는 것도 이제 보입니다. - 해시 코드가 고르게 나와야 합니다. - 적재율이 기준 아래로 관리돼야 합니다. 둘 중 하나가 깨지면 평균이 최악 쪽으로 끌려갑니다. 적재율은 재해싱이 알아서 관리합니다. 남는 건 해시 코드입니다. `int` 나 `string` 처럼 자주 쓰는 타입은 잘 만들어져 있으니 걱정할 것이 없습니다. **직접 만든 타입을 키로 쓸 때가 문제입니다.** ## 직접 만든 타입을 키로 쓸 때 앞에서 `HashSet` 에 직접 만든 타입을 담으면 내용이 같아도 다른 것으로 본다고 했습니다. 이유가 이제 보입니다. 찾는 과정에서 봤듯이, 해시 테이블이 두 값을 같다고 판단하려면 **두 가지가 맞아야** 합니다. - 해시 코드가 같아야 같은 버킷으로 갑니다. - 그 버킷 안에서 비교했을 때 같다고 나와야 합니다. 그래서 규칙이 하나 나옵니다. `GetHashCode` 와 `Equals` 의 **계약** 이라고 부릅니다. > **같다고 볼 두 값은 반드시 같은 해시 코드를 내놓아야 합니다.** 반대는 성립하지 않습니다. 해시 코드가 같아도 다른 값일 수 있습니다. 그게 해시 충돌입니다. 그러니 해시 코드는 **버킷을 좁히는 데까지**만 쓰고, 최종 판단은 `Equals` 가 합니다. 아무것도 안 하면 직접 만든 타입은 내용이 아니라 **만들어진 개체 단위**로 판단합니다. 내용이 같아도 따로 만든 것이면 다른 값입니다. 한 가지 더 있습니다. **키로 쓴 값을 나중에 바꾸면 안 됩니다.** 넣을 때 계산한 버킷에 놓여 있는데, 값이 바뀌면 해시 코드도 바뀝니다. 그러면 새 해시 코드로 계산한 버킷에는 그게 없습니다. 넣어 두고도 못 찾습니다. 키는 안 바뀌는 값으로 씁니다. 숫자, 문자열, `enum` 이 키로 자주 쓰이는 이유입니다. ### 그래서 어떻게 만드나 직접 쓰지 않는 것이 답입니다. **`record` 로 선언하면 컴파일러가 만들어 줍니다.** ```csharp public readonly record struct Cell(int X, int Y); ``` `Equals` 와 `GetHashCode` 가 값 기준으로 같이 생깁니다. 계약도 저절로 지켜집니다. `record` 를 못 쓰는 자리면 `HashCode.Combine` 을 씁니다. ```csharp public override int GetHashCode() => HashCode.Combine(X, Y); ``` 직접 쓸 때 지킬 것은 셋입니다. - **`Equals` 에서 쓰는 필드를 전부, 그리고 그것만** 섞습니다 - **`^` 나 `+` 만 쓰지 않습니다.** 둘 다 순서를 구분 못 해서 `(1, 2)` 와 `(2, 1)` 이 같아집니다 - **안 바뀌는 필드만** 씁니다 64×64 격자 좌표 4096개를 키로 넣고 조합 방식만 바꿔 재 보면 차이가 이렇게 납니다. 버킷 개수는 4099로 같습니다. | 조합 방식 | 쓴 버킷 | 가장 긴 줄 | | --- | --- | --- | | `X ^ Y` | 64 | **64** | | `X + Y` | 127 | **64** | | `X * 31 + Y` | 2,017 | 3 | | `HashCode.Combine(X, Y)` | 2,581 | 6 | `^` 만 쓰면 4096개가 버킷 64개에만 들어갑니다. 나머지는 영원히 빕니다. 소수인 버킷 개수도 재해싱도 이건 못 구합니다. **애초에 서로 다른 해시 코드가 안 나왔으니까요.** ### 누가 무엇을 책임지나 | 키 타입 | 안전한가 | 왜 | | --- | --- | --- | | `string` | 안전 | 해시가 잘 만들어져 있고, 100번 충돌하면 무작위 해시로 갈아탐 | | `int` · `long` · `enum` | 안전 | 값을 그대로 쓰지만 버킷 개수가 소수라 흩어짐 | | `record` | 안전 | 컴파일러가 모든 필드를 제대로 섞음 | | **직접 쓴 `GetHashCode`** | **위험** | 아무도 안 막아 줌 | **마지막 줄만 조심하면 나머지는 신경 쓸 일이 없습니다.** ## 다른 방법도 있다: 개방 주소법 여기까지가 C# 의 해시 테이블입니다. 충돌을 처리하는 방법이 하나 더 있습니다. **개방 주소법**(open addressing) 은 아예 안 매답니다. 버킷이 차 있으면 **다른 빈 버킷을 찾아 거기 넣습니다.** 값이 자기 버킷이 아닌 곳에 앉을 수 있으니 "주소가 열려 있다" 는 이름이 붙었습니다. 빈 버킷을 한 칸씩 옆으로 찾아가는 방식을 **선형 탐사**(linear probing) 라고 합니다. 같은 값을 같은 순서로 넣으면서 방식만 바꿔 봅니다. 물약이 4번으로, 반지가 0번까지 밀립니다. 반지는 빈 자리를 찾느라 네 번 옆을 봤습니다. 자기 자리 근처가 이미 차 있으면 그 덩어리를 통째로 지나가야 하는데, 이렇게 값이 한쪽에 뭉치는 것을 **군집화**(clustering) 라고 합니다. 선형 탐사의 고질적인 약점입니다. 지우는 것도 다릅니다. 값을 지우고 그 버킷을 그냥 비우면, **뒤로 밀려 있던 값들이 통째로 안 보이게 됩니다.** 찾을 때 빈 버킷을 만나면 없다고 판단하고 멈추기 때문입니다. 그래서 지운 자리에는 비었다는 표시가 아니라 **지웠다는 표시**를 남깁니다. 이 표시를 **톰스톤**(tombstone) 이라고 합니다. 찾을 때는 지나가고, 넣을 때는 쓸 수 있는 자리입니다. ### 무엇을 얻고 무엇을 잃는가

장점

적재율이 1을 넘어도 동작합니다. "꽉 찼다" 는 상태 자체가 없습니다. 버킷 하나가 목록을 들고 있으니 자리가 모자랄 일이 없습니다.
지우기가 간단합니다. 줄에서 빼면 끝이고 뒷정리가 없습니다.
천천히 나빠집니다. 적재율이 올라가도 줄이 조금씩 길어질 뿐입니다. 어느 지점에서 갑자기 무너지지 않습니다.
해시 코드가 고르지 못해도 덜 다칩니다. 한 버킷의 줄만 길어지고 나머지 버킷은 멀쩡합니다.

단점

캐시가 안 듣습니다. 값이 버킷 배열 밖에 흩어져 있어서, 줄을 따라갈 때마다 전혀 다른 주소로 뜁니다. 배열이 주변을 한 덩어리로 가져다 두는 이점을 못 씁니다.
값마다 참조가 따로 듭니다. 다음을 가리키는 몫이 값마다 붙습니다. 담는 값이 작을수록 이 비용의 비율이 커집니다.

장점

캐시에 유리합니다. 값이 전부 버킷 배열 안에 있습니다. 옆 버킷을 보는 일은 이미 손에 들어와 있는 것을 보는 일이라 거의 공짜입니다.
메모리가 덜 듭니다. 따라갈 참조가 없으니 배열 하나면 끝입니다.
적재율만 낮게 유지되면 체이닝보다 확실히 빠릅니다. 대부분 탐사 없이 한 번에 맞고, 맞아도 옆 버킷 한둘입니다.

단점

적재율이 1을 넘을 수 없습니다. 그리고 1에 닿기 한참 전인 0.7 언저리부터 급격히 나빠집니다.
군집화. 한번 뭉치기 시작하면 그 덩어리를 통째로 지나가야 하고, 지나가면서 덩어리를 더 키웁니다.
지우는 게 일입니다. 톰스톤을 남겨야 하고, 톰스톤은 빈 버킷이 아니라서 쌓이면 탐사가 다시 길어집니다. 주기적으로 청소해 줘야 합니다.
해시 코드가 고르지 못하면 크게 무너집니다. 체이닝은 한 줄만 길어지지만 여기는 뭉친 자리 근처가 전부 느려집니다.

한 줄로 줄이면 **체이닝은 안정적이고, 개방 주소법은 조건이 맞으면 더 빠릅니다.** | 이럴 때 | 쓸 것 | | --- | --- | | 담길 개수를 짐작하기 어렵다 | 체이닝 | | 넣고 지우기가 자주 일어난다 | 체이닝 | | 담는 값이 크거나 참조 타입이다 | 체이닝 | | 개수를 알아서 적재율을 낮게 잡아 둘 수 있다 | 개방 주소법 | | 값이 작고, 쓰기보다 읽기가 압도적으로 많다 | 개방 주소법 | **C# 이 체이닝을 고른 이유가 여기 있습니다.** 어떤 용도로 쓰일지 모르는 표준 라이브러리라 안정적인 쪽을 골랐습니다. 개방 주소법은 조건을 직접 통제할 수 있는 자리에서 씁니다. `Span` 을 직접 굴리는 고성능 코드나, 그런 선택을 한 다른 언어의 표준 라이브러리에서 만납니다. **둘 중 무엇이 맞다가 아니라, 무엇을 포기했느냐가 다릅니다.** ## 정리 - 해시 테이블은 값을 보고 자리를 계산합니다. 찾아다니지 않습니다. - 해시 함수가 값을 해시 코드 하나로 줄입니다. 같은 값이면 항상 같은 해시 코드여야 합니다. - **버킷 인덱스 = 해시 코드 % 버킷 개수.** 나누기는 이 한 번뿐입니다. - **버킷 개수는 언제나 소수입니다.** 해시 코드가 규칙적이어도 소수로 나누면 고르게 퍼집니다. - 버킷보다 값의 가짓수가 많으니 해시 충돌은 반드시 생깁니다. C# 은 체이닝으로 그 버킷에 매답니다. - 적재율이 기준을 넘으면 버킷 개수를 다음 소수로 늘리고 전부 다시 계산합니다. - 담을 개수를 짐작할 수 있으면 처음부터 알려주세요. 재해싱이 사라지고 버킷도 덜 잡습니다. - 재해싱은 고르게 만드는 게 아니라 짧게 만듭니다. 고르게 만드는 것은 해시 코드와 소수인 버킷 개수입니다. - 그래서 해시 코드가 나쁘면 늘려도 소용없습니다. 줄이 실제로 계속 길어집니다. - 문자열 키는 한 줄에서 100번 넘게 충돌하면 C# 이 무작위 해시로 바꿔 다시 흩습니다. - 찾을 때도 같은 계산을 합니다. 그 버킷만 보고, 없으면 없는 것입니다. - 담긴 개수가 늘어도 찾는 비용이 거의 안 늘어납니다. 평균 O(1) 입니다. 한 버킷에 다 몰리면 최악 O(N) 입니다. - `GetHashCode` 와 `Equals` 는 계약 관계입니다. 키로 쓴 값은 나중에 바꾸면 안 됩니다. - 직접 만든 타입은 `record` 로 선언하면 끝입니다. 구멍은 `GetHashCode` 를 직접 쓸 때만 열립니다. - 충돌 처리에는 개방 주소법도 있습니다. 캐시에 유리한 대신 적재율이 1을 못 넘고 군집화와 톰스톤을 떠안습니다.