ハッシュルックアップとバイナリサーチはどちらが速いか？

質問

最適なパフォーマンスで繰り返される同時検索が必要な、静的なオブジェクトのセット (一度ロードされるとほとんど変更されないという意味での静的) が与えられたとき、どちらの方が良いでしょうか？ HashMap またはカスタム コンパレーターを使用したバイナリ検索による配列のどちらが良いでしょうか?

答えはオブジェクトまたは構造体タイプの関数ですか？ ハッシュおよび/またはイコール関数のパフォーマンス？ ハッシュの一意性？ リストサイズ？ Hashset サイズ/セットサイズ？

私が見ているセットのサイズは、500kから10mまでです。

私はC#の答えを探していますが、真の数学的な答えは言語にはないと思うので、そのタグは含んでいません。 しかし、もしC#特有の注意すべき点があれば、その情報は望まれます。

どのように解決するのですか？

わかりました、手短に説明します。

C#のショートアンサーです。

2つの異なるアプローチをテストします。

.NET は、1 行のコードでアプローチを変更するためのツールを提供します。 そうでなければ、System.Collections.Generic.Dictionary を使用し、初期容量として大きな数で初期化することを確認してください。または、古いバケット配列を収集するために GC が行う仕事のために、残りの人生をアイテムの挿入で過ごすことになります。

長い回答です。

ハッシュテーブルのルックアップ時間はほぼ一定で、実世界でハッシュテーブルの項目にたどり着くには、単にハッシュを計算するだけではいけません。

ハッシュテーブルの項目へのアクセスは次のように行われます。

• キーのハッシュを取得する
• そのハッシュのバケット番号を取得する（通常、map関数は以下のようになります。 bucket = hash % bucketsCount)
• アイテムチェーン（基本的には、同じバケットを共有するアイテムのリストです。 ほとんどのハッシュテーブルでは、バケツ/ハッシュの処理に バケットとハッシュの衝突を処理するためにこの方法を使用します。 の衝突を処理するためにこの方法を使います)。 バケットから始まり、各キーを と比較します。 追加/削除/更新/含まれているかどうかの確認 が含まれているかどうかを確認します。

検索時間は、ハッシュ関数がどれだけ優れているか（出力がどれだけまばらか）、高速か、使用しているバケットの数、キーの比較器がどれだけ高速かに依存し、常に最良の解決策とは限りません。

より良い、より深い説明です。 http://en.wikipedia.org/wiki/Hash_table