ハッシュ化

(原文)

HashSet と HashMap は広く使われる2つの型です。デフォルトのハッシュアルゴリズムは指定されていませんが、執筆時点では SipHash 1-3 と呼ばれるアルゴリズムがデフォルトとなっています。このアルゴリズムは高い品質を持っており衝突に対する高い保護性能を持ちますが、その一方で特に整数のような短いキーについては遅いという特徴があります。

もしプロファイリングによりハッシュ化がホットであると判明し、HashDoS attacks がアプリケーションにおいて懸念にならない場合には、より高速なハッシュアルゴリズムを持つハッシュテーブルの使用により、大きな速度の改善ができます。

• rustc-hash は HashSet や HashMap の代替となる FxHashSet や FxHashMap を提供しています。ハッシュアルゴリズムは低品質ですが、特に整数キーの場合にはとても高速で、rustc 内の他のどのハッシュアルゴリズムよりも性能が優れています（fxhash は同じアルゴリズムと型の実装を持ちますが、rustc-hash に比べると古くあまりメンテナンスされていません）
• fnv は FnvHashSet 及び FnvHashMap 型を提供しています。ハッシュアルゴリズムは rustc-hash よりも高品質ですが、その分速度はやや劣ります
• ahash は AHashSet 及び AHashMap を提供しています。ahash のハッシュアルゴリズムはいくつかのプロセッサで利用可能な AES 命令をサポートしています

ハッシュ化のパフォーマンスがプログラムにおいて重要であれば、これらの代替案をいくつか試す価値があるでしょう。例えば、rustc では次の結果が得られました：

• fnv から fxhash への移行は最大6%の高速化をもたらしました
• fxhash から ahash への移行の試みは 1-4%の速度低下という結果でした
• fxhash からデフォルトのハッシュアルゴリズムに戻す試みは4-84%の速度低下という結果でした！

FxHashSet や FxHashMap のような代替案を一般に採用することを決めた場合、ある場所で HashSet や HashMap を誤って使ってしまうということが容易に起こり得ます。clippy を使用するとこの問題を回避できます。

いくつかの型はハッシュ化を必要としません。例えば、整数型を包んだ newtype があり、その値はランダムまたはランダムに近いものであるとします。そのような型の場合、ハッシュ化された値の分布は値自体のそれとさほど変わらないでしょう。こういうケースでは nohash_hasher が役立つこともあります。

ハッシュ関数の設計は複雑なトピックであり、この本の範囲外です。ahash のドキュメントには参考になる情報が載っています。