18

キーにハッシュ手法を適用して、その値をメモリアドレスに格納することを理解しています。

しかし、ここで衝突がどのように起こっているのかわかりませんか? Java がメモリ空間を作成するために使用するハッシュ アルゴリズムはどれですか? MD5ですか？

4

4 に答える 4

47

の基本的な考え方HashMapは次のとおりです。

  1. AHashMapは実際には、キーと値の両方を保持する特別なオブジェクトの配列です。
  2. アレイには、16 などのバケット (スロット) がいくつかあります。
  3. ハッシュアルゴリズムはhashCode()、すべてのオブジェクトが持つメソッドによって提供されます。したがって、新しい を作成するときは、メソッドの適切な実装Classに注意する必要があります。（クラスの）デフォルトのものは、メモリポインタを数値として受け取ります。しかし、これは、使用したいほとんどのクラスには適していません。たとえば、このクラスは、文字列内のすべての文字からハッシュを作成するアルゴリズムを使用します。これは次のように考えてください: (簡略化)。したがって、メモリ内の異なる場所にある場合でも、2 つの等しい文字列は同じになります。hashCode()equals()ObjectStringhashCode = 1.char + 2.char + 3.char...hashCode()
  4. の結果hashCode()、たとえば「132」は、配列がそれほど大きい場合にオブジェクトを格納するバケットの数です。しかし、そうではありません。私たちのバケツの長さはわずか 16 です。したがって、明らかな計算'hashcode % array.length = bucket'orを使用して'132 mod 16 = 4'、キーと値のペアをバケット番号 4 に保存します。
    • まだ他のペアがなければ、大丈夫です。
    • 持っている Key と同じ Key を持つものがあれば、古いものを削除します。
    • 別の Key-Value ペア (衝突) がある場合は、古いペアの後に新しいペアをリンク リストに連鎖させます。
  6. バッキング配列がいっぱいになりすぎて、あまりにも多くのリンクされたリストを作成する必要がある場合は、長さを 2 倍にした新しい配列を作成し、すべての要素を再ハッシュして新しい配列に追加し、古いものを破棄します。これは で最もコストのかかる操作である可能性が高いため、事前にわかっている場合は、使用するバケットの数HashMapを伝えたいと考えています。Maps
  7. 誰かが値を取得しようとした場合、彼はキーを提供し、それをハッシュして変更し、潜在的なリンク リストを調べて完全に一致するものを探します。

ウィキペディアからの画像: グラフィック

この場合、

  • 256 個のバケットを持つ配列があります (もちろん、0 ～ 255 の番号が付けられています)
  • 5人います。それらのハッシュコードは、通過した後mod 256、配列内の 4 つの異なるスロットを指します。
  • Sandra Dee には空きスロットがなかったため、John Smith の後に連鎖していることがわかります。

ここで、Sandra Dee の電話番号を検索しようとすると、彼女の名前をハッシュし、256 で mod して、バケット 152 を調べます。そこに John Smith が見つかります。それはサンドラではありません。もっと見てください...ああ、ジョンの後に鎖でつながれているサンドラがいます。

于 2012-06-05T09:45:21.807 に答える
4

これは、 MD5などHashの手法を意味するものではありません。特定のキーのを格納するために使用されるメモリ位置のHashCode 。HashingObject

読み：

これは、HashMapがどのように機能するかについてのより明確な説明ですか？

于 2012-06-05T09:17:40.190 に答える
1

クラスのデフォルトの実装 hashCode()関数Objectとして、メモリアドレスをHashTable&のキーとして使用されるハッシュとして返しHashMapます。

于 2012-06-05T09:14:20.140 に答える
0

@Slanec の回答を確認した後、Java-8 の javadoc を参照してください。大幅な変更があります。例: 「TREEIFY」。バケットあたりのエントリ数のしきい値 (現在は 8) に達した場合に、LinkedList が TreeMap に変換されます。

于 2015-10-22T19:44:38.500 に答える