C++の高速なハッシュテーブルの実装を読んだ (ankerl::unordered_dense) - QiitaC++の高速なハッシュテーブル、ankerl::unordered_dense::{map, set}の実装を読んでみた。 作者によるとabsl::flat_hash_map(通称SwissTable。Google製)と同程度に挿入・検索が速く、特にイテレートはstd::vectorと同等で最速らしい。 Comprehensive C++ Hashmap Benchmarks 2022にベンチマークがある。 (作者自身による計測なので、多少のバイアスはあるかもしれない) 基本のアルゴリズム Robin Hood hashing + Backward shift deletionを使用している。 まずこれを理解すると分かりやすい。 アニメーション付き Robin Hood Hashing | Programming.Guide 詳細な説明 Robin Hood hashing | Code
