最近のC++のハッシュマップ事情 - Faith and Brave - C++で遊ぼう

C++標準ライブラリのハッシュマップであるstd::unordered_mapより2〜3倍速いハッシュマップ実装が、外部ライブラリとしていくつもあります。なぜ標準のものが遅いのか、どれを選べばいいのか、乗り換えるときに何に気をつけるべきかをまとめていきます。 なぜstd::unordered_mapは (ほかと比べて) 遅いと言われるのか std::unordered_mapの実装を速くすることに限界があるのは、仕様がクローズドアドレッシング (closed addressing、実装としては分離連鎖法) 方式を前提にした設計・仕様になっているからです。とくに、以下の2つが方式を限定する要因になっています。 参照安定性の要求 - 変更操作やリハッシュをしても参照とポインタが (削除した要素以外) 無効にならないという要求がある。そのために、要素をひとつずつヒープに確保してポインタでつなぐノ

[ad2217]

O(1)でも速さに定数倍の違いがある。

[nguyen-oi]

std::unordered_mapの制限とSwiss Table等の最新事情が分かりやすくまとまってて助かる