RustのHashMapを通じて，最近のハッシュテーブルをもう一歩理解してみる

この記事はハッシュテーブルについて1から説明する内容ではなくて，一度は学習したことがある人向けです．
Rustにおける2つのバージョンの，異なるHashMapで使われる理論と実装を解説しています．Rustに限らずハッシュテーブルへの理解を深める役に立てば幸いです．

# ハッシュテーブル
ハッシュテーブルは**平均**$O(1)$でのインサート，サーチ，デリートをサポートするデータ構造です．
いろんな言語にいろんなハッシュテーブルの実装があります．それぞれ中身の実装に微妙に差があったりして厳密な議論をする際にはその中身が大事になってきたりします．実装は大まかには類似していると思いますが，衝突処理や探索方法，冪乗or素数スロットなどに明確なバリエーションが存在します．このあたりの選択は使用するハッシュ関数の性質とアプリケーションの要件によってある程度決定されることです．よく使われるものもありますが，最もよいという組み合わせがあるわけではありません．
このような基本的な部分は英語版のwikipediaページ[Hashtable](https://en.wikipedia.org/wiki/Hash_table)に網羅的にまとめられています．

もし興味ある方がいれば，各言語の特徴的なハッシュテーブルに関するマテリアルを簡単にまとめておきます．中には癖のある実装が合って面白いものもあるので，自分に馴染みのない言語のハッシュテーブルの実装も知っておくと何かのヒントになるかもしれません．

- Python
    - https://mail.python.org/pipermail/python-dev/2012-December/123028.html
        - 元々は1エントリ24バイトでハッシュ値，キーのポインタ，値へのポインタを持っていたけど無駄すぎるのでやめたという話題です．
        - pythonの辞書型が順序づけられている理由が分かりそうです．
    - https://github.com/python/cpython/blob/master/Objects/dictobject.c
        - 最新のソースに書いてあるコメントを読むのが一番理解が早そうです．メモリレイアウトについても詳しく書かれています．
- Java
    - JavaのHashMapの特徴は衝突処理が連鎖法がベースになっています．しかし，最初はデータをLinkedListに格納しますが、ハッシュの項目数がある閾値以上になると、LinkedListから平衡木に変わります．
    - https://www.nurkiewicz.com/2014/04/hashmap-performance-improvements-in.html
        - ちなみに，後に説明する`load factor`はデフォルトで0.75のようです．
- C++
    - STLの`std :: unordered_set`は連鎖法で実装されています
    - https://stackoverflow.com/questions/31112852/how-stdunordered-map-is-implemented/31113618#31113618
- Golang
    - https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics
        - C++の実装との比較が詳細に書かれています
        - 連鎖法ですが，初期のバケットの数が8のようです．
- C#
    - https://docs.microsoft.com/en-us/previous-versions/ms379571(v=vs.80)?redirectedfrom=MSDN#collision-resolution-in-the-hashtable-class
      - 他の実装にはあまり見ない，double hashingを使っているようです．
- PHP
    - http://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html#the-new-hashtable-implementation
        - 実はPHP7からはハッシュテーブルの実装が新しくなったようです
    - https://nikic.github.io/2011/12/28/Supercolliding-a-PHP-array.html
        - 2011年時点では，HashDoSが容易に可能であったようです．
- Ruby
    - https://speakerdeck.com/south37/ruby-2-dot-4-falsehatusiyuteburugao-su-hua-woli-jie-suru
        - Ruby2.4でopen addresingになったことで以前より早くなったという話題です．これはわりと有名な話題かもしれません．

- Linux KernelのHash Tableの実装もあるようです．
  - https://computing.ece.vt.edu/~changwoo/ECE-LKP-2019F/l/lec04-flexsc-kds1.pdf

---
ここまではどうでもいいですが，この記事ではRustの標準のハッシュテーブルである`std::collections::HashMap`の中身がどのような構成になっているかを紹介します．

# hashbrown
[Rustのレポジトリ](https://github.com/rust-lang/rust)で適当にHashmapと検索すると`HashMap`の宣言部分が見つかります．

```rust
use hashbrown::hash_map as base;
...
pub struct HashMap<K, V, S = RandomState> {
    base: base::HashMap<K, V, S>,
}
```

上のbaseというのは最初の`use`文で宣言されているように`hashbrown`というクレートのエイリアスであり，この実装がRustの標準のハッシュテーブルとして採用されています．

[`hashbrown`](https://github.com/rust-lang/hashbrown)の公式レポジトリによると，Rustのバージョン1.36から採用されていて，バージョン1.35以前のハッシュテーブルの実装に比べると2倍程度の高速化を達成しているようです．
[`hashbrown`](https://github.com/rust-lang/hashbrown)は，[***SwissTable***](https://abseil.io/blog/20180927-swisstables)と呼ばれる，Googleが考案した高効率のハッシュテーブルのRust実装になっています． この`hashbrown`についてなんとなく理解するというのが本記事の真の目的です．


# バージョン1.35以前のRustのHashMap
最初に，以前のバージョンのRustのHashMapで使用されていたHashMapの動作について見ておきます．以前のバージョンのRustのHashMapでは***Robin Hood Hashing***が用いられています．***Robin Hood Hashing***を採用している（いた）主流の言語はRust以外は知りません．
((参考) [***Robin Hood Hashing***の原著](https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf)は35年くらい前のPedro Celisさんの博士論文)

## Robin Hood Hashing
***Robin Hood Hashing***は，衝突が起こった際にテーブル内の空いているところを線形探索してデータを埋めていきます．つまりオープンアドレッシングで方式です．
一般的には，ハッシュテーブルのオープンアドレッシングではいくつかの議論の観点があって，主要なものの1つに探索にかかる計算量の平均と分散のどちらを重視するかという議論です．直感的には分散を重視するということは，探索時間の最大値が小さいものがより好まれるということになります．

#### 探索時間の分散を小さくすることの重要性
具体例として， 
ハッシュテーブルに`[(a, 1), (b, 2), (c, 3), (d, 4), (e, 5), (f, 6)]`というタプルを格納した場合にそれぞれの値の探索時間がどのように表現されるのかを考えます．タプルのキーはそれぞれハッシュ関数によって`0,0,1,2,1,0`にされるとします．
なんらかのアルゴリズムによってハッシングを行いデータが格納され，ハッシュテーブルのキーが`[a, b, c, d, e, f]`という並びになっていたとします．この時，探索時間は`a,b,c,d,e,f`それぞれに対して`0,1,1,1,3,5`となります．
また，別のアルゴリズムによってハッシングした場合には`[a,b,f,e,c,d]`となっていて，この時は`a,b,c,d,e,f`それぞれに対して`0,1,3,3,2,2`となることが分かります．
ちなみに，前者が単純ないわゆる***FCFS***のアルゴリズムに従って結果であり，後者が***Robin Hood Hashing***に従った結果です．
***Robin Hood Hashing***がどうしてこのような並びになるのかは後に説明します．この2つの結果を比較すると，探索時間の平均は同じですが，分散が後者の方が小さくなっていることが分かります．

***Robin Hood Hashing***では明確に分散を重視しており，探索時間の最大値をいかに減らすかということを意識しています．多くのアプリケーションでこの最大値が脆弱性やボトルネックの原因になり得ます．(c.f ***HashDoS***)
とは言え，分散を減らす最も大きなメリットはキャッシュの恩恵を最大化できることです．データへのアクセスにかかる時間のボトルネックはキャッシュラインのフェッチなので同じキャッシュラインにデータが含まれていれば，探索時間はほとんど変わりません．(L1キャッシュの参照は約1~2nsですが，キャッシュラインのフェッチは100ns程度かかります．)なので，目標とすべきなのは，任意のデータに対して探索範囲が1キャッシュラインで収まることと言えます．***Robin Hood Hashing***の目標もまさにこのことです．


#### メモリ効率
また，データアクセスの際の計算時間が安定することは，メモリ空間的にもよいパフォーマンスにつながります．なぜなら，ハッシュテーブルにおける`load factor`を高く設定してもパフォーマンスが安定するためです．
ハッシュテーブルには大抵の場合，ハッシュテーブルの`initial capacity`と`load factor`の2つのパラメータがあると思います．`load factor`は現在の容量のうちどの程度の割合のデータが埋まったらハッシュテーブルを拡張するかを決定する閾値です．つまり，`load factor`は探索時間とメモリサイズのトレードオフを与えて調節させてくれます．`load factor`が大きいほどハッシュ値が重複する可能性が短く済むので探索が高速になるということです．

Robin Hood Hashingを使用した場合は，たとえ`load factor`が高くても探索時間が安定しているので，高めの設定が可能であり，結果メモリ空間的にパフォーマンスがよいと言えます．一般的には，適切なハッシュ関数を使っていれば*90%*程度にしても問題なく動作するようです．以下に見るようにRustの実装でもそのくらいの閾値を設定していました．

#### アルゴリズム
探索は基本的に通常の線形探索によって行われます．
インサートを行う際は，空の場合は問題なくインサートします．
すでにデータが埋まっている場合，インサートする要素と，インサートしたい位置に入っている要素のどちらが正規の位置から離れているかを比較します．
インサートする要素の方が近かった場合はスルーして，インサートする要素の方が距離が離れていた場合，さらに離れることがないように元々のデータが追い出されて，そこに新しい要素がインサートされます．
次に追い出されたデータは空いているスペースを発見するまで再帰的に同じ動作を繰り返します．

#### 簡単な例
言葉では分かりづらいので以下に例を示します．
`[(a, 1), (b, 2), (c, 3), (d, 4), (e, 5), (f, 6)]`をデータとして仮定し，タプルのキーはそれぞれハッシュ関数によって`0,0,1,2,1,0`にされるとします．例えば，`a`と`b`はインデックスの0番地で衝突します．

```
[           ] array initial
[a          ] a inserted
[a b        ] b inserted (a displaces b because it was first)
[a b c      ] c inserted (b displaces c because c is farther)
[a b c d    ] d inserted (c displaces d because d is farther)
[a b c e d  ] e inserted (b displaces e (farther)
                        , c displaces e (tie)
                        , e displaces d (farther))
[a b f e c d] f inserted (a displaces f (tie)
                        , b displaces f (tie)
                        , f displaces c (farther)
                        , e displaces c (tie)
                        , c displaces d (farther))
[0 1 2 2 3 3] final distances from ideal

```
(https://gankra.github.io/blah/robinhood-part-1/ より)

最も単純なオープンアドレッシングである***FCFS***と比較すると維持コストがかかりますが，その分計算量的に安全にデータにアクセスできるようになることが分かると思います．


### ソースコードを見てみる
[バージョン1.34のrustのレポジトリ](https://github.com/rust-lang/rust/blob/91856ed52c58aa5ba66a015354d1cc69e9779bdf/src/libstd/collections/hash/map.rs#L409)を確認すると，確かに`hashbrown`クレートではなく素朴な雰囲気でハッシュテーブルが実装されています．

メインの構造体は一貫したハッシュ値を生成する責務を持っていそうな`hash_builder`，データを実際に格納してプリミティブなアクセサを提供しそうな`RawTable`，ハッシュテーブルのリハッシュ時の挙動のポリシーを司りそうな雰囲気の`DefaultResizePolicy`という構成になっています．

```rust
pub struct HashMap<K, V, S = RandomState> {
    // All hashes are keyed on these values, to prevent hash collision attacks.
    hash_builder: S,

    table: RawTable<K, V>,

    resize_policy: DefaultResizePolicy,
}
```

#### DefaultResizePolicy
せっかくなので上で説明した`load factor`はどうなっているのかということを見てみます．

ソースコードを眺めると，`DefaultResizePolicy`はハッシュテーブルのサイズに関する条件のチェックに使用されていて，`try_raw_capacity`は受け取ったサイズを格納するのに必要なハッシュテーブルの容量を返します．
細かいですが11倍して10で割っている値を2の冪乗の数と比較していることから分かる通り，上で述べた`load factor`は約90%です．

```rust
impl DefaultResizePolicy {
   ...

    /// A hash map’s “capacity” is the number of elements it can hold without
    /// being resized. Its “raw capacity” is the number of slots required to
    /// provide that capacity, accounting for maximum loading. The raw capacity
    /// is always zero or a power of two.
    #[inline]
    fn try_raw_capacity(&self, len: usize) -> Result<usize, CollectionAllocErr> {
        if len == 0 {
            Ok(0)
        } else {
            // 1. Account for loading: `raw_capacity >= len * 1.1`.
            // 2. Ensure it is a power of two.
            // 3. Ensure it is at least the minimum size.
            let mut raw_cap = len.checked_mul(11)
                .map(|l| l / 10)
                .and_then(|l| l.checked_next_power_of_two())
                .ok_or(CollectionAllocErr::CapacityOverflow)?;

            raw_cap = max(MIN_NONZERO_RAW_CAPACITY, raw_cap);
            Ok(raw_cap)
        }
    }
...
```

#### hash_builder

`hash_builder`について見ていくと，普通に[SipHash](https://en.wikipedia.org/wiki/SipHash)を使ってランダムなシード値を用いてハッシュ関数を生成していることが分かります．

```rust
impl BuildHasher for RandomState {
    ...
    fn build_hasher(&self) -> DefaultHasher {
        DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1))
    }
}
```

#### RawTable

メインのプロパティである`RawTable`は[ここ](https://github.com/rust-lang/rust/blob/91856ed52c58aa5ba66a015354d1cc69e9779bdf/src/libstd/collections/hash/table.rs#L106)に定義されています．
幽霊型を使ってコンパイル時に型検査ができるようになっています．すごいざっくり見ると，データはポインタ`TaggedHashUintPtr`とサイズ`size`で持っています．`capacity_mask`は現在の容量を`u64`で2進数のマスク表現で持っている感じです．その方が論理積でサイズのチェックをしたりできるので便利だからです．こうすることで明確に連続領域にデータを持ち，高速にアクセスできて，例えば`Vec<Option<_,_>>`とかよりもキャッシュが効くデータ配置になっているようです．

```rust
pub struct RawTable<K, V> {
    capacity_mask: usize,
    size: usize,
    hashes: TaggedHashUintPtr,

    // Because K/V do not appear directly in any of the types in the struct,
    // inform rustc that in fact instances of K and V are reachable from here.
    marker: marker::PhantomData<(K, V)>,
}
```

`RawTable`のデータの実体は上のように生ポインタで表現されているために`table::Bucket`という構造体が安全に`RawTable`へのViewを提供する役割を持っているように見えます．Rustにはこういうデザインパターンがあるんでしょうか．この`Bucket`はハッシュテーブルにおける値を格納するバケツを意味する専門用語ですが，Rustの実装では，`Bucket`は`RawTable`に対する動的なビューという役割に抽象化されているように見えます．

#### Robin Hood Hashingの実装
ここから***Robin Hood Hashing***の実装を抜粋してみます．

[`HashMap::insert`](https://doc.rust-lang.org/beta/std/collections/struct.HashMap.html#method.insert)は身近なインターフェースですが，内部では上で言及した`table::Bucket`を介して`RawTable`の生ポインタを操作することになります．
`insert`はハッシュテーブルに対する操作なので当然内部では，上で確認した***Robin Hood Hashing***に従った挙動が確認されるはずです．

とりあえず***Robin Hood Hashing***の実装を確認するために以下のように`insert`から`search_hashed_nonempty`の実装まで降りていきます．

```rust
pub fn insert(&mut self, k: K, v: V) -> Option<V> {
    let hash = self.make_hash(&k);
    self.reserve(1);
    self.insert_hashed_nocheck(hash, k, v)
}
...
fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> Option<V> {
    let entry = search_hashed(&mut self.table, hash, |key| *key == k).into_entry(k);
    match entry {
        Some(Occupied(mut elem)) => Some(elem.insert(v)),
        Some(Vacant(elem)) => {
            elem.insert(v);
            None
        }
        None => unreachable!(),
    }
}
...
fn search_hashed_nonempty<K, V, M, F>(table: M, hash: SafeHash, mut is_match: F,
                                      compare_hashes: bool)
    ...
{
    // Do not check the capacity as an extra branch could slow the lookup.

    let size = table.size();
    let mut probe = Bucket::new(table, hash);
    let mut displacement = 0;

    loop {
        let full = match probe.peek() {
            Empty(bucket) => {
                // Found a hole!
                return InternalEntry::Vacant {
                    hash,
                    elem: NoElem(bucket, displacement),
                };
            }
            Full(bucket) => bucket,
        };

        let probe_displacement = full.displacement();

        if probe_displacement < displacement {
            // Found a luckier bucket than me.
            // We can finish the search early if we hit any bucket
            // with a lower distance to initial bucket than we've probed.
            return InternalEntry::Vacant {
                hash,
                elem: NeqElem(full, probe_displacement),
            };
        }

        // If the hash doesn't match, it can't be this one..
        if !compare_hashes || hash == full.hash() {
            // If the key doesn't match, it can't be this one..
            if is_match(full.read().0) {
                return InternalEntry::Occupied { elem: full };
            }
        }
        displacement += 1;
        probe = full.next();
        debug_assert!(displacement <= size);
    }
}
```

`let mut probe = Bucket::new(table, hash);`は`RawTable`へのカーソル(hashによるインデックス指定)付きのViewであり，これを経由してデータがあるかどうかを確認します．ここでデータがなければ，`InternalEntry::Vacant {NoElem}`を返します．データがあれば，`probe.displacement()`が呼ばれます．
[probe.displacement()](https://github.com/rust-lang/rust/blob/91856ed52c58aa5ba66a015354d1cc69e9779bdf/src/libstd/collections/hash/table.rs#L511)はハッシュで解決された理想的なインデックスのロケーションと現在のカーソルの距離を返します．インサート対象のデータではなく，カーソルが示す位置にあるデータ，つまり`probe`の理想のロケーションとの距離です．メソッドの実装が示すようにこの値は各データが持っているわけではなく，その場で計算されています．
この概念は***Robin Hood Hashing***においてインサートの判断に使用されます．関数内では，もし，インサート対象のデータの理想的なインデックスとの距離の方が`probe`のそれよりも大きければその時点で`InternalEntry::Vacant {NeqElem}`を返します．
外側のループ内でカーソルの位置と距離がインクリメントされていき，どこかで空きが見つかるかもしくは，距離が逆転することになります．
すでに全く同一のキーを持つデータが入っていた場合は，`InternalEntry::Occupied { elem: full }`を返します．ちなみにRustの`HashMap::insert`の挙動では元々入っていたデータがリターンされる仕様になっています．

あとは本質的ではないですが，`insert_hashed_nocheck`でその返り値を受け取り， `InternalEntry::hogehoge`に実行を移譲します．
以下のように`mem::swap`で既存のものと入れ替える，再帰的に`robin_hood`を実行する([`robin_hood()`](https://github.com/rust-lang/rust/blob/91856ed52c58aa5ba66a015354d1cc69e9779bdf/src/libstd/collections/hash/map.rs#L563)の実装は上のものとほとんど同じです)，`table::Bucket`(`RawTable`へのアクセス)経由でデータを挿入するという3パターンの処理が実行されます．

```rust
impl<'a, K, V> OccupiedEntry<'a, K, V> {
...
pub fn insert(&mut self, mut value: V) -> V {
    let old_value = self.get_mut();
    mem::swap(&mut value, old_value);
    value
}
...
}

impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
...
pub fn insert(self, value: V) -> &'a mut V {
    let b = match self.elem {
        NeqElem(mut bucket, disp) => {
            if disp >= DISPLACEMENT_THRESHOLD {
                bucket.table_mut().set_tag(true);
            }
            robin_hood(bucket, disp, self.hash, self.key, value)
        },
        NoElem(mut bucket, disp) => {
            if disp >= DISPLACEMENT_THRESHOLD {
                bucket.table_mut().set_tag(true);
            }
            bucket.put(self.hash, self.key, value)
        },
    };
    b.into_mut_refs().1
}
...
}
```

これでRustのHashMapの処理の流れをだいたい見ることができました．
***Robin Hood Hashing***は，非常に効率の良い一方で，実装はかなり単純で理解しやすいものであるということが分かります．

[`remove`の内部処理](https://github.com/rust-lang/rust/blob/91856ed52c58aa5ba66a015354d1cc69e9779bdf/src/libstd/collections/hash/map.rs#L537)も非常に直感的なので興味ある人は確認してみてください.


# バージョン1.36移行のRustのHashMap実装
(githubのレポジトリを見た感じバージョン1.35から標準のHashMapとして採用されているように見えましたが[`hashbrown`](https://github.com/rust-lang/hashbrown)には1.36からと書いてあります．一応．)

## rust-lang側
最初にrust-lang側の[`HashMap`](https://github.com/rust-lang/rust/blob/34c5cd9a64d8537236626c4ccbed39a924cd38e2/src/libstd/collections/hash/map.rs#L203-L205)の実装を簡単に見ておくと，上で見たように[`hashbrown`](https://github.com/rust-lang/hashbrown)の宣言があって,`base`という名前で`HashMap`内に持っています．
例えば，[`HashMap::insert`](https://github.com/rust-lang/rust/blob/34c5cd9a64d8537236626c4ccbed39a924cd38e2/src/libstd/collections/hash/map.rs#L818-L820)が示すようにrust-lang側の実装は，[`hashbrown`](https://github.com/rust-lang/hashbrown)の`insert`の実装をラップしてインターフェースを提供しているのみです．

```rust
use hashbrown::hash_map as base;
...
pub struct HashMap<K, V, S = RandomState> {
    base: base::HashMap<K, V, S>,
}

impl<K, V, S> HashMap<K, V, S> {
...
pub fn insert(&mut self, k: K, v: V) -> Option<V> {
    self.base.insert(k, v)
}
```

## SwissTable
[`hashbrown`](https://github.com/rust-lang/hashbrown)は***SwissTable***のRust実装です．
***SwissTable***とは，https://www.youtube.com/watch?v=ncHmEUmJZf4 で紹介されているように，Googleが開発したハイパフォーマンスなハッシュテーブルの実装です．この動画は2017年のCPPConにおける講演です．***SwissTable***は少なくとも現段階では学術的な用語というよりは，単に[Abseil](https://abseil.io/)が提供する新しいハッシュテーブルの実装である，

- `absl::flat_hash_map`
- `absl::flat_hash_set`
- `absl::node_hash_map`
- `absl::node_hash_set`

これらまとめてのコードネームだと思います．これらは従来の`std::unordered_set`と`std::unordered_map`に代わって使用されることが期待されています．これらはC++の話です．

***SwissTable***のベースは，やはりオープンアドレッシングのハッシュテーブルです．以下に示すような工夫をすることで，高いパフォーマンスを達成することがGoogle内部での検証などで確認されています．

### ポイント
ポイントは線形探索の改善であり，メタデータの追加+SIMDによる並列処理によって実現されています．

***SwissTable***では以下のように，テーブルの各エントリに対して新たに1バイトの制御用のメタデータを含みます．`ctrl`が各エントリに追加されたメタデータを表します．

```
 index |   0    |   1    |   2    |   3    |   4    | ... |   n    |
-------|--------|--------|--------|--------|--------|     |--------|
 value |        |        |        |        |        | ... |        |
-------|--------|--------|--------|--------|--------|     |--------|
 ctrl  |00000000|00000000|00000000|00000000|00000000| ... |00000000|
```

ただしメモリレイアウトは直感的ではない可能性があり，メタデータは全て同一のキャッシュラインに含まれていて欲しいので連続領域に並んでいます．`hashbrown`では，16個のエントリが1つのグループという概念でまとめられていて，1つのグループのメタデータ128ビットが1つのキャッシュラインに載ることが想定されています． 

次に2つのハッシュ関数が必要で，1つは通常のハッシュ関数$H_1$で，もうひとつはそのハッシュ値に対して下位7桁のビット配列を得る$H_2$です．($H_2$は`hashbrown`の実装だと上位7ビットになっています．こっちの方がわずかに早い可能性があります...)
例としては，インサートされるデータ(key=1, value=2)に対して以下のような値を得られます．

```
H_1(1)= 12638147618137026400
H_2 = H(1) >> (bit_length_of_hash - 7) = 87 = 0b1010111
```
$H_2$から得られたこの7ビットを，メタデータの下位7ビットに対応させて，下のようなルールに従ってメタデータを設定します．
`0b1111_1111 = エントリが空のとき`
`0b1000_0000 = 削除済みのとき (tombstone)`
`0b0xxx_xxxx = データが埋まっているとき (下位7ビットが上で得られたもの)`

例えば，`(5,7)`と`(39, 8)`をインサートしたあとのレイアウトは以下のようになります．（ハッシュ関数は適当です）

```
## 最初の状態
 index |   0    |   1    |   2    |   3    |   4    | ... |   15   |
-------|--------|--------|--------|--------|--------|     |--------|
 value |        |        |        |        |        | ... |        |
-------|--------|--------|--------|--------|--------|     |--------|
 ctrl  |11111111|11111111|11111111|11111111|11111111| ... |11111111|

## (5,7)をインサートする, H(5) % 16 == 0, H_2(5) => 0b1010111
 index |   0    |   1    |   2    |   3    |   4    | ... |   15   |
-------|--------|--------|--------|--------|--------|     |--------|
 value | (5,7)  |        |        |        |        | ... |        |
-------|--------|--------|--------|--------|--------|     |--------|
 ctrl  |01010111|11111111|11111111|11111111|11111111| ... |11111111|

## (39, 8)をインサートする, H(39) % 16 == 2, H_2(39) => 0b110110
 index |   0    |   1    |   2    |   3    |   4    | ... |   15   |
-------|--------|--------|--------|--------|--------|     |--------|
 value | (5,7)  |        | (39,8) |        |        | ... |        |
-------|--------|--------|--------|--------|--------|     |--------|
 ctrl  |01010111|11111111|00110110|11111111|11111111| ... |11111111|
```

このようなメタデータを付与した状態を作ることで，効率よく探索を行うことができます．
ここでのポイントはいくつかのSIMD命令を組み合わせることです．今のIntelのCPUはほとんどが[SIMDをサポート](https://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%88%E3%83%AA%E3%83%BC%E3%83%9F%E3%83%B3%E3%82%B0SIMD%E6%8B%A1%E5%BC%B5%E5%91%BD%E4%BB%A4)していますので．128ビット幅のSSE命令で16×8ビットのビット列に対して並列処理をしていきます．RustでSIMD命令を使うのはかなり簡単だと思います．

まず探索対象のデータのハッシュ値を$H_1$,$H_2$に対して計算します．
次に$H_1$値から，取得するキャッシュラインを特定し，SIMDのロード命令によって128ビットレジスタにデータをロードします．(Rustだと[`core::arch::x86_64::_mm_loadu_si128`](https://doc.rust-lang.org/nightly/core/arch/x86_64/fn._mm_loadu_si128.html))

```
---------------------------------------------     ------------
| 01010111 | 11111111 | 00110110 | 11111111 | ... | 11111111 |
---------------------------------------------     ------------
```

次に，値の比較のために$H_2$値(= 0b110110)を，これもSIMDでセットします．(Rustだと[`core::arch::x86_64::_mm_set1_epi8`](https://doc.rust-lang.org/nightly/core/arch/x86_64/fn._mm_set1_epi8.html))

```
---------------------------------------------     ------------
| 00110110 | 00110110 | 00110110 | 00110110 | ... | 00110110 |
---------------------------------------------     ------------
```

次に比較を行って，位置を特定します．これも16×8ビットのSIMDで比較命令を実行します．(Rustだと[`core::arch::x86_64::_mm_cmpeq_epi8`](https://doc.rust-lang.org/nightly/core/arch/x86_64/fn._mm_cmpeq_epi8.html))．あくまで$H_2$を比較しているだけなのでこの比較結果は必ずしも正しいものではなく，偽陽性を含みます[^1]．

```
---------------------------------------------     ------------
| 00000000 | 00000000 | 11111111 | 00000000 | ... | 00000000 |
---------------------------------------------     ------------
```

最後は，上の結果をSIMDのマスク命令で16ビットに圧縮します． (Rustだと[`core::arch::x86_64::_mm_movemask_epi8`](https://doc.rust-lang.org/nightly/core/arch/x86_64/fn._mm_movemask_epi8.html))

```
---------------------------------------------     ------------
|    0     |    0     |    1     |    0     | ... |    0     |
---------------------------------------------     ------------
```

このように4つのCPU命令で16個分の候補に対して結果を得ることができます．
値がヒットしていれば，そのインデックスを用いて，グループに対してエントリ内の実データを確認しにいきます．
データが違っていた，もしくは，値がヒットしていなければ，次のグループのメタデータをフェッチしてきて同様の操作を行います．
以上が，***SwissTable***及び`hashbrown`のおおまかな探索の流れになります．

デリートやインサートも同様に行うことができます．

一応，上の動画とAbseilの公式ページにはもう一つのポイントとしてStorage Optimizationsという項目がありましたが，これはC++のメモリアロケーションの改善の話だったので`hashbrown`に関係なさそうなので割愛します．

ちなみに，直感的には上のメタデータはオーバヘッドになっているような気はしますが，CPPCon2017の発表内では，格納するデータのサイズが極端に小さい場合はオーバヘッドが勝つ可能性があると言ってました．***SwissTable***の性質に関する実際のチューニングのトレードオフ的な知見はまだまとまった情報がなさそうで，ここに色々書くことはできませんでした．

あまり***Robin Hood Hashing***との対比的な部分も本記事では示せていないですが， https://github.com/rust-lang/hashbrown#performance ここにRustにおける簡単な実験の比較があるので確認してみてもよいかもしれません．

### Rustにおける実装
アルゴリズムがだいたい分かったので`hashbrown`のソースコードを少し見て見ます．
[`HashMap`の定義自体](https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/map.rs#L188-L191)は前の実装とあまり変わりません

```rust
pub struct HashMap<K, V, S = DefaultHashBuilder> {
    pub(crate) hash_builder: S,
    pub(crate) table: RawTable<(K, V)>,
}
```

[`RawTable`の定義](https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/raw/mod.rs#L359-L376)はやや変わっています．`ctrl`が生ポインタになってデータの実体のアドレスを持っています．

```rust
/// A raw hash table with an unsafe API.
pub struct RawTable<T> {
    // Mask to get an index from a hash value. The value is one less than the
    // number of buckets in the table.
    bucket_mask: usize,

    // [Padding], T1, T2, ..., Tlast, C1, C2, ...
    //                                ^ points here
    ctrl: NonNull<u8>,

    // Number of elements that can be inserted before we need to grow the table
    growth_left: usize,

    // Number of elements in the table, only really used by len()
    items: usize,

    // Tell dropck that we own instances of T.
    marker: PhantomData<T>,
}
```

実装をチラチラ眺めると，`HashMap::insert`も`HashMap::get`も`HashMap::remove`も，以下の[`RawTable::find`](https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/raw/mod.rs#L912-L931)を介して生データにアクセスしており，このメソッドを見ていけばよさそうということが分かります．
前バージョンの実装とほとんど同様に，`bucket`は`RawTable`のデータへの抽象的なアクセサになっていて，論理的なインデックスを物理アドレスに変換して実際のデータへのアクセスを提供しています．

```rust
impl<T> RawTable<T> {
...
pub fn find(&self, hash: u64, mut eq: impl FnMut(&T) -> bool) -> Option<Bucket<T>> {
    unsafe {
        for pos in self.probe_seq(hash) {
            let group = Group::load(self.ctrl(pos));
            for bit in group.match_byte(h2(hash)) {
                let index = (pos + bit) & self.bucket_mask;
                let bucket = self.bucket(index);
                if likely(eq(bucket.as_ref())) {
                    return Some(bucket);
                }
            }
            if likely(group.match_empty().any_bit_set()) {
                return None;
            }
        }
    }

    // probe_seq never returns.
    unreachable!();
}
```

`find`のロジックを見てみます．
上でグループという概念が登場しましたが，説明した通りここでそのグループが出てきています．
`let group = Group::load(self.ctrl(pos));`
そしてこの[`Group`](https://github.com/rust-lang/hashbrown/blob/master/src/raw/sse2.rs)がいくつかのSIMD命令のラッパーとして機能していることが分かります．`find`メソッド内で呼ばれている[`load`の実装](https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/raw/sse2.rs#L46-L48) を見ると，まさに先ほどあげたRustのSIMD命令インターフェースを通じてポインタから値を読み込んでいることが分かります．

```rust
pub unsafe fn load(ptr: *const u8) -> Self {
    Group(x86::_mm_loadu_si128(ptr as *const _))
}
```

次の[`Group::match_byte`の実装](https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/raw/sse2.rs#L73-L86)を見ると，こちらも先に説明したように`x86::_mm_set1_epi8`，`x86::_mm_cmpeq_epi8`，`x86::_mm_movemask_epi8`が呼ばれていることが分かります．

```rust
unsafe {
    let cmp = x86::_mm_cmpeq_epi8(self.0, x86::_mm_set1_epi8(byte as i8));
    BitMask(x86::_mm_movemask_epi8(cmp) as u16)
}
```
`group`を介してSIMD命令を発行して効率よく探索ができている雰囲気が感じ取れました．
そのあとの実データへのアクセスについては後で少し触れますが抽象化されているため特に難しくなさそうに見えます．

最後に`insert`の処理を眺めてデータの実体に対して観察を行います．
`HashMap::insert`は[`RawTable::insert`](https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/raw/mod.rs#L864-L884)を介して行われます．

```rust
pub fn insert(&mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64) -> Bucket<T> {
    unsafe {
        let mut index = self.find_insert_slot(hash);

        // We can avoid growing the table once we have reached our load
        // factor if we are replacing a tombstone. This works since the
        // number of EMPTY slots does not change in this case.
        let old_ctrl = *self.ctrl(index);
        if unlikely(self.growth_left == 0 && special_is_empty(old_ctrl)) {
            self.reserve(1, hasher);
            index = self.find_insert_slot(hash);
        }

        let bucket = self.bucket(index);
        self.growth_left -= special_is_empty(old_ctrl) as usize;
        self.set_ctrl(index, h2(hash));
        bucket.write(value);
        self.items += 1;
        bucket
    }
}
```

最初に[`find_insert_slot`](https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/raw/mod.rs#L561-L592)でインサートするインデックスを見つけます．このメソッドの中では，先ほど紹介したのと同様`Group`によってSIMD命令が発行されています．tombstoneつまり，削除済みのデータもインサートする場所の候補とすることで省メモリになっているとも書いてあります．

`bucket`は前のバージョンと同様に`RawTable`へのビューを提供し，これを介して`index`が示す論理的な位置を物理アドレスへと変換して値を書き込んでいます．
`bucket`を介して実データは[baseとなっているアドレス](https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/raw/mod.rs#L366)から[マイナス方向に] (https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/raw/mod.rs#L298) ，制御用メタデータは[プラス方向に](https://github.com/rust-lang/hashbrown/blob/efbd03661fc9df0e594ecc89784107353cc71060/src/raw/mod.rs#L476) index分先のデータをメモリとして提供するというデータの配置になっています．生ポインタ1つとデータの個数だけでこのように複雑な配置を表現しているのは面白いと思いました．（ここ合っているか微妙です．）

```
## メモリのレイアウト
...|00011...000||ベースアドレス||11111111|...
   　　実データ　←　　　　　　　→  メタデータ
```

ここで確認したいのは，`set_ctrl(index, h2(hash))`です．これは，メタデータ`ctrl`に対しての書き込みを行っていることが名前から分かります．
`h2`の実装をみてみると，先に説明したように，入力の上位7ビットのデータを取得して返すことが分かります．
この1バイトの値を`set_ctrl`によって制御用のメタデータとして格納します．

```rust
fn h2(hash: u64) -> u8 {
    // Grab the top 7 bits of the hash. While the hash is normally a full 64-bit
    // value, some hash functions (such as FxHash) produce a usize result
    // instead, which means that the top 32 bits are 0 on 32-bit platforms.
    let hash_len = usize::min(mem::size_of::<usize>(), mem::size_of::<u64>());
    let top7 = hash >> (hash_len * 8 - 7);
    (top7 & 0x7f) as u8 // truncation
}
```

細かいところまで詰めていけばキリがないのでこのくらいで終わっておきます．

# まとめ
RustのHashMapで新旧で実装されている***Robin Hood Hashing***と***SwissTable***の解説をしました．
ハッシュテーブルはもう何十年も前に発明されて，時代のニーズに合わせて進化を重ねてきましたが，まだまだ健在でほんとに興味深いデータ構造だと思います．最近だと，ブルームフィルタとかカッコウハッシュとかの確率的データ構造がハッシュテーブルのさらに進化としていろんなアプリケーションに使われていて注目しています([この記事が分かりやすいです](https://medium.com/techlog/cuckoo-filter-vs-bloom-filter-from-a-gophers-perspective-94d5e6c53299))．時代を超えて普遍的に使われる理論だと思うので，今回のようにハッシュテーブルの内部実装を眺めてみたりするのもそれなりに有意義だと思います．

本記事は，ソースコードの解釈などは特に，自分の感覚的な解釈が多いのであまり真に受けずよろしくお願い致します．

[^1]: ここで起こる偽陽性は、一般的な意味でのハッシュテーブルの衝突とは異なります．（@methane さんに[コメント](https://qiita.com/fumilemon/items/5f5a58fa3b9920b5d2bc#comment-a8aed606ef933d46ea9d)頂きました．ありがとうございます．）


#### 参考文献
- https://gankra.github.io/blah/robinhood-part-1/
- https://gankra.github.io/blah/hashbrown-tldr/
- https://abseil.io/blog/20180927-swisstables
- https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
- https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/
- http://shlegeris.com/2017/01/06/hash-maps
- https://blog.waffles.space/2018/12/07/deep-dive-into-hashbrown/
- https://abseil.io/about/design/swisstables