Faster Go maps with Swiss Tables
take0For example, Go 1.19 switched the sort package from a traditional quicksort, to pattern-defeating quicksort, a novel sorting algorithm from Orson R. L. Peters, first described in 2015.
たとえば、Go 1.19 では、ソート パッケージが従来のクイックソートから、2015 年に初めて説明された Orson R. L. Peters による新しいソート アルゴリズムであるパターン回避クイックソートに変更されました。(後でクイックソートのアップデートについても調べよう)
(https://go.dev/doc/go1.19#sortpkgsort)
(https://arxiv.org/pdf/2106.05123.pdf)
Like sorting algorithms, hash table data structures continue to see improvements. In 2017, Sam Benzaquen, Alkis Evlogimenos, Matt Kulukundis, and Roman Perepelitsa at Google presented a new C++ hash table design, dubbed “Swiss Tables”. In 2018, their implementation was open sourced in the Abseil C++ library.
ソートアルゴリズムと同様に、ハッシュ テーブルのデータ構造も改善され続けています
2017年、GoogleのSam Benzaquen氏、Alkis Evlogimenos氏、Matt Kulukundis氏、Roman Perepelitsa氏は、「Swiss Tables」と呼ばれる新しいC++ハッシュテーブル設計を発表しました。2018年には、その実装がAbseil C++ライブラリとしてオープンソース化されました。
take0Open-addressed hash table
Swiss Tables are a form of open-addressed hash table,
スイステーブルはオープンアドレスハッシュテーブルの一種(form ofでその一種のような表現になるのか)
In an open-addressed hash table, all items are stored in a single backing array.
オープンアドレスのハッシュ テーブルでは、すべての項目が単一のバッキング配列に格納されます。
We’ll call each location in the array a slot. The slot to which a key belongs is primarily determined by the hash function, hash(key).
配列内の各位置をスロットと呼ぶことにします。
キーが属する（所持する）スロットは、主にハッシュ関数 hash(key) によって決定されます。（キー:スロット＝1:1？？）
The hash function maps each key to an integer, where the same key always maps to the same integer, and different keys ideally follow a uniform random distribution of integers.
ハッシュ関数は各キーを整数にマッピングします。
同じキーは常に同じ整数にマッピングされ、異なるキーは理想的には整数の均一なランダム分布に従います。
The defining feature of open-addressed hash tables is that they resolve collisions by storing the key elsewhere in the backing array
So, if the slot is already full (a collision), then a probe sequence is used to consider other slots until an empty slot is found
オープンアドレスハッシュテーブルの特徴は、キーをバッキング配列の別の場所に格納することで衝突を解決することである
したがって、スロットがすでにいっぱいの場合（衝突）、空のスロットが見つかるまで他のスロットを検討するためにプローブシーケンスが使用されます。
Example
Below you can see a 16-slot backing array for a hash table, and the key (if any) stored in each slot.
The values are not shown, as they are not relevant to this example.
| Slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Key | 56 | 32 | 21 | 78 |
To insert a new key, we use the hash function to select a slot. Since there are only 16 slots, we need to restrict to this range, so we’ll use hash(key) % 16 as the target slot.
新しいキーを挿入するには、ハッシュ関数を使ってスロットを選択します。スロットは16個しかないため、この範囲に制限する必要があります。そのため、対象のスロットとして hash(key) % 16 を使用します。
Suppose we want to insert key 98 and hash(98) % 16 = 7. Slot 7 is empty, so we simply insert 98 there.
On the other hand, suppose we want to insert key 25 and hash(25) % 16 = 3. Slot 3 is a collision because it already contains key 56. Thus we cannot insert here.
キー98とhash(98)%16=7を挿入するとします。スロット7は空なので、そこに98を挿入するだけです。
一方、キー25とhash(25)%16=3を挿入するとします。スロット3にはすでにキー56が含まれているため衝突が発生します。したがって、ここに挿入することはできません。
We use a probe sequence to find another slot. There are a variety of well-known probe sequences. The original and most straightforward probe sequence is linear probing, which simply tries successive slots in order.
別のスロットを見つけるために、プローブシーケンス（探索系列）を使用します。よく知られたプローブシーケンスにはさまざまな種類があります。最も基本的で分かりやすいプローブシーケンスは線形探索（linear probing）で、これは単純にスロットを順番に試していく方法です。
So, in the hash(25) % 16 = 3 example, since slot 3 is in use, we would consider slot 4 next, which is also in use. So too is slot 5. Finally, we’d get to empty slot 6, where we’d store key 25.
したがって、hash(25) % 16 = 3 の例では、スロット3が使用中なので、次にスロット4を検討します。スロット4も使用中です。スロット5も同様です。最後に、空のスロット6にキー25が格納されます。
Lookup follows the same approach. A lookup of key 25 would start at slot 3, check whether it contains key 25 (it does not), and then continue linear probing until it finds key 25 in slot 6.
検索も同じアプローチに従います。キー25の検索はスロット3から開始し、キー25が含まれているかどうかを確認します（含まれていないため）。その後、スロット6でキー25が見つかるまで線形探索を続けます。
This example uses a backing array with 16 slots. What happens if we insert more than 16 elements? If the hash table runs out of space, it will grow, usually by doubling the size of the backing array. All existing entries are reinserted into the new backing array.
この例では、16スロットの配列を使用しています。16を超える要素を挿入するとどうなるでしょうか？
ハッシュテーブルのスペースが不足した場合、通常はバッキング配列のサイズを2倍にすることでハッシュテーブルは拡張されます。既存のエントリはすべて新しいバッキング配列に再挿入されます。
Open-addressed hash tables don’t actually wait until the backing array is completely full to grow because as the array gets more full, the average length of each probe sequence increases. In the example above using key 25, we must probe 4 different slots to find an empty slot. If the array had only one empty slot, the worst case probe length would be O(n). That is, you may need to scan the entire array. The proportion of used slots is called the load factor, and most hash tables define a maximum load factor (typically 70-90%) at which point they will grow to avoid the extremely long probe sequences of very full hash tables.
オープンアドレスのハッシュ テーブルは、実際にはバッキング配列が完全にいっぱいになるまで待機せずに拡張します。これは、配列がいっぱいになるにつれて、各プローブ シーケンスの平均長が増加するためです。
上記のキー25の例では、空きスロットを見つけるために4つの異なるスロットをプローブする必要があります。配列に空きスロットが1つしかない場合、最悪の場合のプローブ長はO(n)になります。（16番目のみ空いているケースは16回計算必要）つまり、配列全体をスキャンする必要がある可能性があります。
使用されているスロットの割合は負荷係数と呼ばれ、ほとんどのハッシュ テーブルは最大負荷係数 (通常 70 ～ 90%) を定義しており、その時点でハッシュ テーブルは大きくなり、非常にいっぱいのハッシュ テーブルの極端に長いプローブ シーケンスを回避します。
プローブシーケンス：ハッシュ衝突が発生したときに、空いているスロットを探すために使う探索手法。
線形探索（Linear Probing）：(hash + i) % size のように、1つずつ順番に次のスロットを試していくアルゴリズム。実装が簡単でメモリの局所性も高いですが、**クラスタリング（連続的な空きスロットの集まり）**が発生しやすいという欠点もあります。