More than 1 year has passed since last update.

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

Last updated at 2022-02-21Posted at 2020-06-20

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

ハッシュテーブル

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

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

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のレポジトリで適当にHashmapと検索するとHashMapの宣言部分が見つかります．

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

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

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

バージョン1.35以前のRustのHashMap

最初に，以前のバージョンのRustのHashMapで使用されていたHashMapの動作について見ておきます．以前のバージョンのRustのHashMapではRobin Hood Hashingが用いられています．Robin Hood Hashingを採用している（いた）主流の言語はRust以外は知りません．
((参考) Robin Hood Hashingの原著は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のレポジトリを確認すると，確かにhashbrownクレートではなく素朴な雰囲気でハッシュテーブルが実装されています．

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

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%です．

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を使ってランダムなシード値を用いてハッシュ関数を生成していることが分かります．

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

RawTable

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

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は身近なインターフェースですが，内部では上で言及したtable::Bucketを介してRawTableの生ポインタを操作することになります．
insertはハッシュテーブルに対する操作なので当然内部では，上で確認したRobin Hood Hashingに従った挙動が確認されるはずです．

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

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()はハッシュで解決された理想的なインデックスのロケーションと現在のカーソルの距離を返します．インサート対象のデータではなく，カーソルが示す位置にあるデータ，つまり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()の実装は上のものとほとんど同じです)，table::Bucket(RawTableへのアクセス)経由でデータを挿入するという3パターンの処理が実行されます．

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の内部処理も非常に直感的なので興味ある人は確認してみてください.

バージョン1.36移行のRustのHashMap実装

(githubのレポジトリを見た感じバージョン1.35から標準のHashMapとして採用されているように見えましたがhashbrownには1.36からと書いてあります．一応．)

rust-lang側

最初にrust-lang側のHashMapの実装を簡単に見ておくと，上で見たようにhashbrownの宣言があって,baseという名前でHashMap内に持っています．
例えば，HashMap::insertが示すようにrust-lang側の実装は，hashbrownのinsertの実装をラップしてインターフェースを提供しているのみです．

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

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をサポートしていますので．128ビット幅のSSE命令で16×8ビットのビット列に対して並列処理をしていきます．RustでSIMD命令を使うのはかなり簡単だと思います．

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

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

次に，値の比較のために$H_2$値(= 0b110110)を，これもSIMDでセットします．(Rustだとcore::arch::x86_64::_mm_set1_epi8)

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

次に比較を行って，位置を特定します．これも16×8ビットのSIMDで比較命令を実行します．(Rustだとcore::arch::x86_64::_mm_cmpeq_epi8)．あくまで$H_2$を比較しているだけなのでこの比較結果は必ずしも正しいものではなく，偽陽性を含みます¹．

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

最後は，上の結果をSIMDのマスク命令で16ビットに圧縮します． (Rustだとcore::arch::x86_64::_mm_movemask_epi8)

---------------------------------------------     ------------
|    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の定義自体は前の実装とあまり変わりません

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

RawTableの定義はやや変わっています．ctrlが生ポインタになってデータの実体のアドレスを持っています．

/// 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を介して生データにアクセスしており，このメソッドを見ていけばよさそうということが分かります．
前バージョンの実装とほとんど同様に，bucketはRawTableのデータへの抽象的なアクセサになっていて，論理的なインデックスを物理アドレスに変換して実際のデータへのアクセスを提供しています．

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がいくつかのSIMD命令のラッパーとして機能していることが分かります．findメソッド内で呼ばれているloadの実装を見ると，まさに先ほどあげたRustのSIMD命令インターフェースを通じてポインタから値を読み込んでいることが分かります．

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

次のGroup::match_byteの実装を見ると，こちらも先に説明したようにx86::_mm_set1_epi8，x86::_mm_cmpeq_epi8，x86::_mm_movemask_epi8が呼ばれていることが分かります．

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を介して行われます．

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でインサートするインデックスを見つけます．このメソッドの中では，先ほど紹介したのと同様GroupによってSIMD命令が発行されています．tombstoneつまり，削除済みのデータもインサートする場所の候補とすることで省メモリになっているとも書いてあります．

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

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

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

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の解説をしました．
ハッシュテーブルはもう何十年も前に発明されて，時代のニーズに合わせて進化を重ねてきましたが，まだまだ健在でほんとに興味深いデータ構造だと思います．最近だと，ブルームフィルタとかカッコウハッシュとかの確率的データ構造がハッシュテーブルのさらに進化としていろんなアプリケーションに使われていて注目しています(この記事が分かりやすいです)．時代を超えて普遍的に使われる理論だと思うので，今回のようにハッシュテーブルの内部実装を眺めてみたりするのもそれなりに有意義だと思います．

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

参考文献

ここで起こる偽陽性は、一般的な意味でのハッシュテーブルの衝突とは異なります．（@methane さんにコメント頂きました．ありがとうございます．） ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up