1

ハッシュテーブルルックアップと線形検索のパフォーマンスを比較してみました。1000個のアイテムを含むハッシュテーブルを作成し、ハッシュテーブルでルックアップを実行するのにかかる時間が0.0002であることDateTime.Nowがわかりました（ルックアップの前後のシステム時間を調べて、それらを差し引いていました）。配列に同じ1000行があり、線形検索を使用して同じ値を検索しました。そして、それはハッシュテーブルのルックアップにかかる時間よりも短いことが判明しました。

ハッシュテーブルは線形検索よりも高速だと思いました。それはどのように機能しますか？

4

2 に答える 2

3

まず、タイミングのメカニズムが良くありません。パフォーマンスをテストする場合は、のような高解像度タイマーを使用する必要がありますSystem.Diagnostics.Stopwatch。

次に、特定の1つのアイテムのルックアップ時間だけでなく、ルックアップスペース全体にランダムかつ均一に分散されている多くのルックアップの平均ルックアップ時間を見つける必要があります。

于 2011-08-13T00:29:04.467 に答える
1

答えはこの記事で見つけることができます：

C＃2.0を使用したデータ構造の広範な調査、

「 System.Collections.Hashtableクラス」というセクションで

これが（非常に）短い概要です：

コレクションへの追加（Add(object key, object value)）：

  1. 受信keyとvalueパラメータ
  2. パラメータにハッシュアルゴリズムを適用しkeyます。これは、このメソッドを使用し、0とハッシュサイズ（ハッシュテーブルObject.GetHashCode()のスロット数（で使用される内部ルックアップ構造）の間のインデックス内の位置を生成する複雑な式です。System.Collections.HashTable
  3. その位置にDictionaryEntryオブジェクトを挿入します。

コレクション内のアイテムへのアクセス（object this[object key] { set; get; }）：

  1. keyパラメータを受け取る
  2. パラメータのハッシュアルゴリズムを使用して、ハッシュテーブル内の位置を計算しkeyます。
  3. valueその位置に保存されているアイテムのを返します
于 2013-10-15T22:50:12.117 に答える