ハッシュマップ！トレンド！2024年版


**近年**[^1]、ハッシュマップの実装トレンドとしてキャッシュフレンドリーなオープンアドレス法が隆盛を極めているっぽいふいんき(なぜか変換できない)を感じているがちゃんと調べたことなかったなと思ったので、かなり雑に調べてまとめてみました。

性能比較とかはしてないので自分でベンチマークとってください。

## チェーン法派閥

- 今となっては少数派

### C++ std::unordered_map

- [std::unordered_map](https://en.cppreference.com/w/cpp/container/unordered_map)
  - バイナリ互換を維持しないとならないので高速化がむずかしい
    - 後述のswiss tables(abseil)が開発される原因となった

## オープンアドレス法派閥

- 勢いがある

### SwissTable派閥

#### Abseil(C++)

- [abseil/abseil-cpp - GitHub](https://github.com/abseil/abseil-cpp)
  - 本家本元

#### Rust

- [std::collections::HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html)
- 実体は[hashbrown](https://github.com/rust-lang/hashbrown)
  - quadratic probing (triangular numbers)
- ハッシュ関数
  - 標準ライブラリはSipHash 1-3 (HashDOS対策)
  - hashbrownはahash

#### Go

- [WIP: runtime: use SwissTable](https://github.com/golang/go/issues/54766)
  - 今はチェーン法っぽいけどほぼ確定で代わるのでこっちに書いた

### Robin-hood probing派閥

- robin-hoodはたんなるprobingの手法だがここにまとめる

#### ankerl::unordered_dense::map(C++)

- [martinus/unordered_dense - GitHub](https://github.com/martinus/unordered_dense)
  - Robin-hood probing + backward shift deletion

#### V言語

- Robin-Hood hashing (Open Addressing)
  - [hashmap: new and fast hashmap with dynamic size](https://github.com/vlang/v/pull/3554)
- [ka-weihe/hashmap-v](https://github.com/ka-weihe/hashmap-v)
  - PR作者が開発していたレポジトリ
  - V言語のハッシュマップを実装した人が書いた論文がレポジトリにある
- ハッシュ関数はwyhashを採用

### PyPy派閥

#### Python

- Open Addressing (PyPyがオリジナル)
  - もともとOpen Addressingな実装で、3.6からPyPyの最適化実装を取り込んでいるらしい
  - [PyPy: faster more memory efficient and more](https://www.pypy.org/posts/2015/01/faster-more-memory-efficient-and-more-4096950404745375390.html)
  - [スライド: new dict implementation in python 3.6](https://speakerdeck.com/methane/new-dict-implementation-in-python-3-dot-6-klab-tech-meetup-2017-09-04)

### Ruby派閥

#### Ruby

- Open Addressing (Pythonと似た感じの)
  - 2.4から変わったらしい(もともとチェーン法)
  - [RubyのHash実装](https://blog.8-p.info/ja/2020/11/19/ruby-hash/)
- probingはlinearっぽい
- ハッシュ関数はSipHash 1-3(HashDOS対策)だが、一部内部実装により高速なFNVやMurMurHash3を使っているらしい
- PyPy派閥としてくくってもよいかもしれない？

#### Crystal

- Rubyの実装ベース
  - [PR: Hash now uses an open addressing algorithm](https://github.com/crystal-lang/crystal/pull/8017)
  - [src/hash.cr](https://github.com/crystal-lang/crystal/blob/881773922173d81512351da33a6613c1e60d3069/src/hash.cr#L43)
- ハッシュ関数は[funny_hash](https://github.com/funny-falcon/funny_hash)をCrystalにポート
  - ほぼMurMurHash3?

### quadratic + tombstone派閥

- robin-hood同様probingの手法
  - 以下のような実装
    - 1ループ目: hash & mask
    - 2ループ目: ((hash & mask) + 1) & mask = 1進む
    - 3ループ目: ((((hash & mask) + 1) & mask) + 2) & mask = 2進む

#### D言語

- Open Addressing
  - 2015年にchain法から変わった
  - [PR: AA should use open addressing hash](https://github.com/dlang/druntime/pull/1229)
    - [(commit in dmd, same as above)](https://github.com/dlang/dmd/commit/79bc91b41334c1805f557ef2f1606de31c6764d1)
  - [Issue 14385 - AA should use open addressing hash](https://issues.dlang.org/show_bug.cgi?id=14385)

- テーブルサイズ: pow2 table
- 削除: tombstone
- ハッシュ関数はMurMurHash2?
  - ユーザ定義の型はhash関数の実装によって変更はできる
- forumではrobin-hood probingも試したが思うように性能が出なかったとのことが書かれていた

### Linear Probing + back shift deletion派閥

#### Nim

- Open Addressing + linear probing
- tombstoneではなくback shift deletion
  - [explain better why delImplIdx is the way it is](https://github.com/nim-lang/Nim/pull/15108)
- ハッシュ関数はWang Yi's hashことwyhashを採用

### Zig派閥

#### Zig

- SwissTableを改変したものらしい？
  - [New hashmap implementation](https://github.com/ziglang/zig/pull/5999)
  - linear probing + tombstoneっぽくみえる
  - metadataの持ち方はそうだけどグループ単位で並列にチェックしてないからあんま意味なくないか？
- ハッシュ関数はwyhashを採用

## まとめ？

いかがでしたか！！？？！？？？

- 性能的な理由によってオープンアドレス法を採用しているものが増えてきている
- オープンアドレス法と一口にいっても意外と実装には独自性がある
- やたらwyhashが人気ある

といったあたりがうかがえたかなと思います。

## 参考資料

- [Swiss Tables and absl::Hash](https://abseil.io/blog/20180927-swisstables)
- [Optimizing Open Addressing](https://thenumb.at/Hashtables/)
- [Optimization of Hash Tables (pdf in repo)](https://github.com/ka-weihe/hashmap-v)
- [Comprehensive C++ Hashmap Benchmarks 2022](https://martin.ankerl.com/2022/08/27/hashmap-bench-01/)
- [abseil(Google)がhash tableを高速化](https://note.com/usop/n/ncf8ca154c1ce)
- [様々なハッシュテーブルたち](https://eukaryote.hateblo.jp/entry/2020/10/22/034619)
- [Swisstable Hash に使われているビット演算の魔術](https://methane.hatenablog.jp/entry/2022/02/22/Swisstable_Hash_%E3%81%AB%E4%BD%BF%E3%82%8F%E3%82%8C%E3%81%A6%E3%81%84%E3%82%8B%E3%83%93%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97%E3%81%AE%E9%AD%94%E8%A1%93)
- [RubyのHash実装](https://blog.8-p.info/ja/2020/11/19/ruby-hash/)

[^1]: いつ？？？？？