3

HashTable（およびその後の派生物）に関して、.netおよびJavaがどのハッシュアルゴリズムを使用しているかを知っている人はいますか？

List と Dictionary はどちらも Hashtable の直接のデスカンデントですか?

4

7 に答える 7

6

ハッシュ関数はハッシュ テーブルに組み込まれていません。ハッシュ テーブルは、キー オブジェクトのメソッドを呼び出してハッシュを計算します。そのため、ハッシュ関数はキー オブジェクトのタイプによって異なります。

Java では、aListはハッシュ テーブルではありません (つまり、Mapインターフェイスを拡張しません)。List内部的にハッシュ テーブル (リスト インデックスがハッシュ テーブルへのキーであるスパース リスト) を使用して を実装することもできますが、そのような実装は標準 Java ライブラリの一部ではありません。

于 2009-05-21T18:46:04.393 に答える
3

私は .NET については何も知りませんが、Java について話そうと思います。

Java では、ハッシュ コードは最終的に、特定のオブジェクトの hashCode() 関数によって返されるコードと、HashMap/ConcurrentHashMap クラス内の 2 次ハッシュ関数の組み合わせになります (興味深いことに、この 2 つは異なる関数を使用します)。Hashtable と Dictionary (HashMap と AbstractMap の前身) は廃止されたクラスであることに注意してください。そして、リストは実際には単なる「別のもの」です。

例として、String クラスは、現在のコードに 31 を繰り返し掛けて次の文字を追加することにより、ハッシュ コードを構築します。詳細については、文字列ハッシュ関数のしくみに関する私の記事を参照してください。数値は通常、ハッシュ コードとして「自分自身」を使用します。フィールドの組み合わせを持つ Rectangle などの他のクラスは、多くの場合、小さな素数を掛けて加算する String 手法の組み合わせを使用しますが、さまざまなフィールド値を加算します。(素数を選択するということは、特定の値とハッシュ コード幅の間で「偶発的な相互作用」が発生する可能性が低いことを意味します。

ハッシュ テーブルのサイズ (つまり、それが持つ「バケット」の数) は 2 のべき乗であるため、ハッシュ コードが範囲内に収まるまで上位ビットを削除することによって、ハッシュ コードからバケット番号が導出されます。二次ハッシュ関数は、乱数の一部が最下位ビットで終了し、欠落しないように「ビットを分散させる」ことにより、ランダム性のすべてまたはほとんどが上位ビットにあるハッシュ関数から保護します。String ハッシュ コードは実際には、この混合がなくてもかなりうまく機能しますが、ユーザーが作成したハッシュ コードはそれほどうまく機能しない可能性があります。2 つの異なるハッシュ コードが同じバケット番号に解決される場合、Java の HashMap 実装は「連鎖」手法を使用することに注意してください。つまり、各バケットにエントリのリンク リストを作成します。これ' したがって、アイテムが特定の範囲のバケットにクラスター化されないように、ハッシュ コードが十分なランダム性を持つことが重要です。(ただし、完全なハッシュ関数を使用しても、平均の法則により、連鎖が発生することが予想されます。)

ハッシュコードの実装は謎ではありません。選択した任意のクラスの hashCode() ソースを確認できます。

于 2009-05-21T20:06:29.580 に答える
2

HASHING アルゴリズムは、HashTable 内の項目のハッシュ コードを決定するために使用されるアルゴリズムです。

HASHTABLE アルゴリズム (この人が求めているのはこれだと思います) は、ハッシュ コードを指定して要素を整理するために HashTable が使用するアルゴリズムです。

Java はたまたま連鎖ハッシュ テーブル アルゴリズムを使用しています。

于 2009-05-21T18:56:00.410 に答える
1

HashTable や .NET のようなものであると主張するものは、独自のハッシュ アルゴリズムを実装していません。これらは常に、ハッシュされるオブジェクトのGetHashCode()メソッドを呼び出します。

このメソッドが何をするか、または何をすべきかについては、特に基本 Object 実装をオーバーライドするユーザー定義またはその他のカスタム クラスに関して、多くの混乱があります。

于 2009-05-21T18:54:35.140 に答える
1

.NET の場合、Reflector を使用してさまざまなアルゴリズムを確認できます。汎用ハッシュ テーブルと非汎用ハッシュ テーブルには異なるものがあります。もちろん、各クラスは独自のハッシュ コード式を定義します。

于 2009-05-21T18:55:14.530 に答える
1

.NETDictionary<T>クラスは、を使用IEqualityComparer<T>してキーのハッシュ コードを計算し、ハッシュ ルックアップを行うためにキー間の比較を実行します。IEqualityComparer<T>インスタンスを構築するときに を指定しないDictionary<T>場合 (コンストラクターへのオプションの引数です)、デフォルトでobject.GetHashCodeおよびobject.Equalsメソッドを使用するデフォルトのインスタンスが作成されます。

標準GetHashCode実装がどのように機能するかについては、文書化されているかどうかわかりません。特定のタイプについては、Reflector のメソッドのソース コードを読むか、Rotor のソース コードをチェックして、そこにあるかどうかを確認してください。

于 2009-05-21T20:40:13.943 に答える