6

Javaでのハッシュについて何かを理解しようとしています。たとえば、ハッシュマップにデータを保存したい場合、ハッシュ値を持つ何らかの基礎となるハッシュテーブルがありますか? または、ハッシュがどのように機能するかについて、誰かが適切で簡単な説明を提供できれば、本当に感謝しています。

4

6 に答える 6

4

たとえば、ハッシュマップにデータを保存したい場合、ハッシュ値を持つ何らかの基礎となるハッシュテーブルがありますか?

AHashMap はハッシュテーブルの形式です（そしてHashTable別のものです）。これらは、 s キー タイプによって提供されるhashCode()およびequals(Object)メソッドを使用して機能します。HashMapキーの動作方法に応じて、 ...によって実装されたhashCode/メソッドを使用するか、それらをオーバーライドできます。equalsjava.lang.Object

または、ハッシュがどのように機能するかについて、誰かが適切で簡単な説明を提供できれば、本当に感謝しています。

ウィキペディアのハッシュ テーブルのページを読んで、それらがどのように機能するかを理解することをお勧めします。(FWIW、HashMapおよびHashTableクラスは「リンクされたリストを使用した個別のチェーン」と、平均パフォーマンスを最適化するためのその他の微調整を使用します。)

ハッシュ関数は、オブジェクト (つまり「キー」) を整数に変換することによって機能します。これをどのように行うかは、実装者次第です。しかし、一般的なアプローチは、オブジェクトのフィールドのハッシュコードを次のように組み合わせることです。

  hashcode = (..((field1.hashcode * prime) + field2.hashcode) * prime + ...)

どこprimeは のような小さめの素数31です。重要なのは、さまざまなキーのハッシュコード値を適切に分散させることです。あなたが望まないのは、すべて同じ値にハッシュする多くのキーです。これは「衝突」を引き起こし、パフォーマンスに悪影響を及ぼします。

hashcodeおよびメソッドを実装するときはequals、ハッシュ テーブルが正しく機能するために、次の制約を満たす方法で実装する必要があります。

 1. O1.equals(o2) => o1.hashcode() == o2.hashcode()
 2. o2.equals(o2) == o2.equals(o1)
 3. The hashcode of an object doesn't change while it is a key in a hash table.

hashCodeによって提供されるデフォルトとequalsメソッドはObject、ターゲット オブジェクトの ID に基づいていることにも注意してください。

「しかし、ハッシュ値はどこに保存されていますか?それは HashMap の一部ではないので、HashMap に関連付けられた配列はありますか?」

通常、ハッシュ値は保存されません。むしろ、必要に応じて計算されます。

クラスの場合、HashMap各キーのハッシュコードは実際にはエントリのNode.hashフィールドにキャッシュされます。しかし、それはパフォーマンスの最適化です...ハッシュチェーンの検索を高速化し、ハッシュテーブルのサイズが変更された場合にハッシュの再計算を回避するためです。しかし、このレベルの理解が必要な場合は、質問をするのではなく、ソース コードを読む必要があります。

于 2013-06-19T16:31:44.177 に答える
4

Java のハッシュ値は、クラスでpublic int hashCode()宣言された実装を通じてオブジェクトによって提供され、すべての基本データ型に対して実装されます。Objectそのメソッドをカスタム データ オブジェクトに実装すると、これらが Java によって提供されるさまざまなデータ構造でどのように使用されるかについて心配する必要がなくなります。

public boolean equals(Object o)注: そのメソッドを実装するには、一貫した方法で実装する必要もあります。

于 2013-06-19T16:15:01.070 に答える
2

これは、Java で最も基本的なコントラクトである.equals()/.hashCode()コントラクトです。ここで最も重要な部分は、考慮される 2 つのオブジェクトが.equals()同じ を返す必要があるということ.hashCode()です。

逆は真ではありません。等しいと見なされないオブジェクトは、同じハッシュ コードを返す可能性があります。しかし、それはできるだけまれな出来事であるべきです。次の実装を考えてみましょう.hashCode()。これは完全に合法ですが、存在できる限り壊れた実装です。

@Override
public int hashCode() { return 42; } // legal!!

この実装はコントラクトに従いますが、ほとんど役に立ちません...したがって、最初に適切なハッシュ関数が重要になります。

現在:コントラクトは、 aに重複する要素を含めてはならないSetことを規定しています。Setただし、Set実装の戦略は残されています... まあ、実装に。の javadoc を見ると、Mapそのキーは というメソッドで取得できることがわかります.keySet()。したがって、MapとSetはこの点で非常に密接に関連しています。

a HashSet(そして、最終的には) の場合、それはandHashMapに依存します: アイテムを追加するとき、最初にこのアイテムのハッシュ コードを計算し、このハッシュ コードに従って、アイテムを指定されたバケットに挿入しようとします。対照的に、 a (and ) は要素の自然順序付けに依存します ( Comparableを参照)。.equals().hashCode()TreeSetTreeMap

ただし、オブジェクトを挿入する必要があり、このオブジェクトのハッシュ コードが空でないハッシュ バケットへの挿入をトリガーする場合 (上記の正当ではあるが壊れた.hashCode()実装を参照)、.equals()そのオブジェクトが本当に一意であるかどうかを判断するために使用されます。

内部的に aHashSetはHashMap...であることに注意してください。

于 2013-06-19T16:24:22.307 に答える