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

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

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

チェーン法派閥

• 今となっては少数派

C++ std::unordered_map

• std::unordered_map
  • バイナリ互換を維持しないとならないので高速化がむずかしい
    • 後述のswiss tables(abseil)が開発される原因となった

オープンアドレス法派閥

• 勢いがある

SwissTable派閥

Abseil(C++)

• abseil/abseil-cpp - GitHub
  • 本家本元

Rust

• std::collections::HashMap
• 実体はhashbrown
  • quadratic probing (triangular numbers)
• ハッシュ関数
  • 標準ライブラリはSipHash 1-3 (HashDOS対策)
  • hashbrownはahash

Go

• WIP: runtime: use SwissTable
  • 今はチェーン法っぽいけどほぼ確定で代わるのでこっちに書いた

Robin-hood probing派閥

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

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

• martinus/unordered_dense - GitHub
  • Robin-hood probing + backward shift deletion

V言語

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

PyPy派閥

Python

• Open Addressing (PyPyがオリジナル)
  • もともとOpen Addressingな実装で、3.6からPyPyの最適化実装を取り込んでいるらしい
  • PyPy: faster more memory efficient and more
  • スライド: new dict implementation in python 3.6

Ruby派閥

Ruby

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

Crystal

• Rubyの実装ベース
  • PR: Hash now uses an open addressing algorithm
  • src/hash.cr
• ハッシュ関数は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
    • (commit in dmd, same as above)
  • Issue 14385 - AA should use open addressing hash

• テーブルサイズ: 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
• ハッシュ関数はWang Yi's hashことwyhashを採用

Zig派閥

Zig

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

まとめ？

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

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

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

参考資料

• Swiss Tables and absl::Hash
• Optimizing Open Addressing
• Optimization of Hash Tables (pdf in repo)
• Comprehensive C++ Hashmap Benchmarks 2022
• abseil(Google)がhash tableを高速化
• 様々なハッシュテーブルたち
• Swisstable Hash に使われているビット演算の魔術
• RubyのHash実装

1. いつ？？？？？ ↩