背景
Rustで辞書型のデータ構造を扱う際にはHashMapとBTreeMapの二種類があってどちらを使うかよく悩みますよね。私は今まではよくBTreeMapのほうを使用していました。確かにHashMapのほうが多くの操作がO(1)でBTreeMapのO(logN)よりも理論上は速いのですが、Nがそこまで大きくない場合にはあまり有意な差は出ず、むしろキーの順番がランダムに変わるということで、すべての要素に対して処理を行う際にソートを忘れると結果の再現性に影響が出る場合がありました。
図は筆者が社内勉強会で作成したスライドより
一方でBTreeMapのほうにも問題があって、CodeLLDBなどのデバッガーで見たときに全くHuman-Readableではないというものです。
本題
結論: IndexMap1 を使う。
IndexMapはRDBなどのようにデータ自体を連続な配列で保持し、それとは別に検索用のインデックスをHashTableで持っておくというデータ構造です。連続な配列はRustの標準ライブラリのVecをそのまま使用していますのでCodeLLDBでもちゃんと読める形で表示されますし、
すべての要素に対して走査する場合もインサートした順なので同じ条件であれば必ず同じ結果になります。
あとは細かい話ですが、RustのデフォルトのHasherはセキュリティを重視していてパフォーマンスがあまりよくないので、計算系のプログラムの場合には上記のコードのようにFxBuildHasherなどの高速なものを代わりに使用することをお勧めします。
結論
以下に各種Mapをまとめました。基本はIndexMapあるいはFxIndexMapを使用し、範囲検索が必要な場合だけBTreeMapを使用すればいいと思います。
| HashMap | BTreeMap | IndexMap | FxIndexMap | |
|---|---|---|---|---|
| Computational Complexity | O(1) | O(logN) | O(1) | O(1) |
| Overhead | Hash function needs unignorable overhead | Smaller | Hash function needs unignorable overhead | Smaller |
| Data Order | Stochastic | Sorted by key | Deterministic | Deterministic |
| Range Search | No | Yes | No | No |
| Iteration for all elements | Slower | Faster | Faster | Faster |
| Debugging | Easy | Difficult | Easy | Easy |