java - HashMap.get メソッドの仕組み

Question

HashMap.getJava のメソッドの背後にあるアルゴリズムを理解しようとしています。

特定のオブジェクトの検索はどのように実行されますか? は Java でどのようにhashMap実装され、どのタイプの検索アルゴリズムを使用していますか?

Answer 1

Java HashMap は、同じハッシュ コードを持つ異なるオブジェクトをどのように処理しますか?からの抜粋

ハッシュマップは次のように機能します (これは少し単純化されていますが、基本的なメカニズムを示しています)。

キーと値のペアを格納するために使用する「バケット」がいくつかあります。各バケットには一意の番号があり、それがバケットを識別します。キーと値のペアをマップに入れると、ハッシュマップはキーのハッシュ コードを調べ、キーのハッシュ コードを識別子とするバケットにペアを格納します。例: キーのハッシュ コードは 235 -> ペアはバケット番号 235 に格納されます (1 つのバケットに複数のキーと値のペアを格納できることに注意してください)。

ハッシュマップでキーを指定して値を検索すると、指定したキーのハッシュ コードが最初に調べられます。次に、ハッシュマップは対応するバケットを調べ、指定したキーとバケット内のすべてのペアのキーを equals() で比較します。

これで、これがマップ内のキーと値のペアを検索するのに非常に効率的であることがわかります。キーのハッシュ コードによって、ハッシュマップは検索対象のバケットをすぐに認識できるため、そのバケットの内容に対してテストするだけで済みます。

上記のメカニズムを見ると、キーの hashCode() および equals() メソッドに必要な要件もわかります。

2 つのキーが同じ (比較すると equals() が true を返す) 場合、それらの hashCode() メソッドは同じ数値を返す必要があります。キーがこれに違反すると、等しいキーが異なるバケットに格納される可能性があり、ハッシュマップはキーと値のペアを見つけることができなくなります (同じバケットを検索するため)。

2 つのキーが異なる場合、それらのハッシュ コードが同じかどうかは問題ではありません。ハッシュコードが同じ場合、それらは同じバケットに格納されます。この場合、ハッシュマップは equals() を使用してそれらを区別します。