4

私はハッシュテーブルとCでの実装方法についてたくさん読んでいますが、頭の中にはほとんどすべての概念があるので、自分でコーディングを開始できると思います。まだいくつか質問があります。正しく理解します。

参考までに、私はこれを読んでいます：http: //eternallyconfuzzled.com/jsw_home.aspx

1）上記のサイトで読んだように、ハッシュテーブルのサイズには2の累乗または素数をお勧めします。これは基本的に配列であり、配列のサイズは固定されているため、探している値をすばやく検索できます。大きな入力がある場合は収まらないため、小さな配列を宣言できません。また、入力データがそれほど大きくないためにメモリが無駄になるため、非常に大きな配列を宣言できません。

ハッシュテーブルの最適なサイズはどれくらいですか？何に基づいて決定する必要がありますか？

2）また、そのサイトには、まだすべてを読んでいないハッシュ関数がいくつかあります。また、よく知られたアルゴリズムを使用し、独自のアルゴリズムを使用することが常に最善であるとも述べています。そして、私はまさにそれを行うかもしれません。そのサイトから1つを選び、コードでテストして、入力データに基づいて衝突が最小限に抑えられるかどうかを確認します。

私を悩ませているのは、ハッシュ範囲をどのように制御するかです。ハッシュを返すことができず、ハッシュテーブルのサイズよりも大きい整数を返すことができません。そうしないと、深刻な問題が発生します。どうすればこれに対処できますか？

4

2 に答える 2

4

1）参照しているのは、ハッシュテーブルの負荷率（いっぱいになると予想されるバケットの割合）です。ウィキペディアには次のように書かれています。

優れたハッシュ関数を使用すると、負荷率が0から0.7程度に増加しても、平均ルックアップコストはほぼ一定になります。そのポイントを超えると、衝突の可能性とそれらを処理するためのコストが増加します。

Java実装（およびおそらく他の実装）は、負荷率を許容範囲内に保つために定期的にサイズ変更されると思います。

2）モジュロ演算子（％）を使用して、バケットインデックスを有効に保ちます。2番目の演算子は、バケット配列のサイズである必要があります。

于 2010-02-20T23:45:48.730 に答える
1

ハッシュテーブルに小さいサイズを選択してください。テーブルにデータを追加するときは、テーブルの何パーセントが使用されているかを確認してください。70％を超える場合は、テーブルを大きくします。これは、要素を削除するときにも当てはまります。たとえば、テーブルが60％未満の場合は、テーブルを小さくします。ウィキペディアには、動的なサイズ変更のいくつかの戦略についての適切な説明がありますが、それが一般的な考え方です。

あなたが既知の入力データを持っているように見えるので、私はこれを言うだけです：

ハッシュテーブルに格納するデータ量の大まかな順序がわかっている場合は、通常、その大きさのテーブルを作成するだけで十分です。（すべてが適合するかどうかを心配する必要はありません。代わりに、衝突の回数とその処理方法について考えるのが正しいでしょう。）

正しいハッシュ関数に関しては、入力の構造がどちらが正しいかを示唆している可能性があります。たとえば、入力のどの側面が均等に分散される可能性がありますか？

于 2010-02-21T03:45:49.770 に答える