RustのMap(辞書型)はDashMap + (RapidHash or aHash)が速いよ

背景

プログラミングにおいて、Map（辞書型）はキーで値を高速に検索・挿入・削除できるため、多くの用途で多用されます。キャッシュ、インデックス、設定値、統計集計など様々な場面で使われる基本的なデータ構造です。
一方で辞書型には、ハッシュ計算コスト、バケットの衝突、並列環境でのロック競合など性能上の課題があるため、用途に応じて実装やハッシュ関数を選ぶことが重要です。

DashMapとは

DashMapはスレッドセーフなハッシュマップ実装で、標準のHashMapと比べて、複数スレッドが同時に読み書きしてもロック競合が起きにくく、実運用でのスループットを高めています。

なぜ高速なのか

DashMapの実装の要点はシャーディングにあります。シャーディングとは、データやバケットを複数の小さな領域に分割し、それぞれを独立して管理する手法を指します。DashMapにおいては、データ領域を複数のシャードに分け、各シャードごとに独立したロックを持たせることで同時並行性を高めています。
これにより、単一のグローバルロックによる競合や単一点のボトルネックが避けられ、マルチスレッドで同一のMapに高頻度なアクセスを行うワークロードで標準実装より高いスループットを発揮します。

辞書型とBuildHasher

Rustでは、ハッシュテーブルの実装において、内部で使うハッシュ関数を差し替えられる仕組み（BuildHasher）が一般的に用意されています。これにより、同じハッシュテーブル実装でもハッシュ関数を入れ替えるだけで性能や耐性を変えられます。

RandomState はハッシュテーブルが内部で使う BuildHasher の実装を指し、RandomState を速いハッシュ（例えば rapidhash::fast::RandomState や ahash::RandomState）に差し替えると、ハッシュ計算コストが下がり、結果として全体の挿入/検索スループットが上がります。

つまり、辞書型のデータ構造の実装と、ハッシュ関数の選択を分けて考えることができます。

高速なハッシュ関数の実装

RapidHashとは

Rapidhashは乗算・回転・XOR といった低レイテンシ整数演算を中心に設計された非暗号ハッシュで、短いキーや大量の短いハッシュを扱うケースで非常に高速です。V1/V2/V3 の世代があり、用途に応じて fast（最高速）と quality（統計品質重視）といった実装パスを切り替えられます。

aHashとは

aHashは AES 命令（AES-NI）が利用可能なプラットフォームで高速化されるハッシュ実装を持つライブラリです。AES 命令によるブロック混合や SIMD 命令でのデータシャッフルを利用し、高速かつ均一な分布を実現します。

ただし、aHash（や rapidhash のRust実装における fast 系など）はインメモリ用途に特化しており、実装や最適化の変更でハッシュ出力がバージョン間で変わる可能性があります。あるバージョンで出力したハッシュ値を永続化して将来のバージョンで照合する用途には適しません。そのため永続化やクロスバージョンのキー同一性が必要な用途には注意が必要です。

RapidHashとaHashの比較

実運用での違いを整理します。

• 性能特性:

  • rapidhash::fast は乗算/回転/XOR中心で低オーバーヘッドなので、短いキーやインライン化が効くケースで極めて高速です
  • ahash（AES-NI 経路）は AES 命令が効く環境では非常に高速ですが、命令セット依存性や短入力での起動コストが影響する場合もあります

• 可搬性:

  • Rapidhash の fast は幅広いプラットフォームで安定して高性能を出すよう設計されています
  • aHash の最速ルートは x86/x86_64 の AES-NI に依存するため、環境次第で差が出ます

• セキュリティ/品質:

  • どちらも暗号ハッシュではなく「インメモリ用ハッシュ」。種（seed）やシークレットで DoS 耐性を持たせられるが、暗号的に安全とは限りません

補足:ハッシュ関数の品質と速度について

SMHasherやその再設計版であるSMHasher3が、ハッシュ関数の品質やパフォーマンスを試験する指標として用いられています。SMHasherのサマリには、高速なハッシュ関数がリスト化されています。RapidHashもaHashも載っています。

各自のハッシュ実装がこれらのテストの通過をアピールしていますし、ベンチマークも公開しています。ただし各自のベンチマークは自分が有利なケースに偏って報告されていますし、結局は利用するプログラミング言語や環境、用途に左右されるので、本当に性能が重要な場合はいくつか試すほうが良いです。

サンプルコード

DashMap + RapidHash

use dashmap::DashMap;
use rapidhash::fast::RandomState as RapidHashRS;

fn main() {
	let map = DashMap::<String, usize, RapidHashRS>::with_capacity_and_hasher(1024, RapidHashRS::default());
	map.insert("foo".to_string(), 42);
	if let Some(v) = map.get("foo") {
		println!("foo = {}", *v);
	}
}

DashMap + aHash

use dashmap::DashMap;
use ahash::RandomState as AHashRS;

fn main() {
	let map = DashMap::<String, usize, AHashRS>::with_capacity_and_hasher(1024, AHashRS::new());
	map.insert("bar".to_string(), 7);
	if let Some(v) = map.get("bar") {
		println!("bar = {}", *v);
	}
}

まとめ

• DashMap と高速ハッシュ（rapidhash::fast や ahash）を組み合わせると、並列ワークロードで非常に高いスループットが得られます。特に DashMap + Rapidhash は多くのシナリオで優れた結果を示しました
• ハッシュ選択はワークロード次第で、短いキーや多数の並列アクセスが中心なら rapidhash::fast、AES-NI が活用でき特定の入力に最適化された場合は ahash を試してください