HashMap: 秘密の部屋、魔法、衝突

HashMap を秘密の部屋 (バケツ) のある城として想像してみましょう。各部屋の前には魔法のドア、ハッシュ関数 があります。この魔法のメカニズムはどのように機能し、2 つの魔法の実体が同じ場所で衝突すると何が起こるのでしょうか? HashMap の秘密の世界に飛び込んでみましょう。まず、HashMap の構成要素を見てみましょう。

HashMap の基本コンポーネント

テーブル配列: この配列はメインのデータ ストレージです。各配列セル (またはバケット) には一意のインデックスが含まれており、そこに値のチェーン、または多数の要素の場合はバイナリ ツリーを保存できます。

LoadFactor: LoadFactor は、HashMap を拡張する前にどれだけ埋められるかを指定します。デフォルトの負荷係数は 0.75 で、メモリの節約とアクセス速度のバランスが取れています。 HashMap が 75% いっぱいになると、効率を維持するためにテーブルのサイズが 2 倍になり、要素が再分散されます。

しきい値: しきい値は、HashMap がテーブルの拡張を決定するポイントです。 (容量 * 負荷係数) として計算されます。たとえば、capacity が 16、loadFactor が 0.75 の場合、しきい値は 12 になります。HashMap の要素が 12 に達すると、サイズが増加します。

サイズは、HashMap 内のキーと値のペアの現在の数を追跡します。

HashMap 内の各キーと値のペアは、以下を含むノードと呼ばれる構造に保存されます。

key - ペアのキー、
value - ペアの値
hash - hashCode() キー
に基づいて計算されたハッシュ next - 衝突が発生した場合のチェーン内の次の要素へのリンク。

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    ....
}

各ノードは衝突時に同じバケット内の次のノードに接続され、リンクされたリストを作成します。バケット内に 8 つを超える要素が蓄積されると、これらのリストは自動的にバランスの取れたバイナリ ツリーに変わります。

ハッシュ関数: 鍵が自分の部屋を見つける方法

HashMap がたくさんの部屋がある巨大な城だと想像してください。各部屋には固有の番号が付いていますが、どの部屋に行くかは鍵でどのように決まるのでしょうか?これはハッシュ関数の仕事です。ハッシュ関数は、特定のキーがどのバケット (部屋) に配置されるかを決定するのに役立つ魔法のツールです。

キーを追加すると、putVal メソッドがキーの hashCode() メソッドを呼び出してハッシュを作成し、バケット全体に均等に分散されるように調整されます。
インデックス計算: 式 int Index = hashCode & (length- 1) を使用して、HashMap はテーブル配列内のバケットを指すインデックスを計算します。

ここで hashCode は、キーがハッシュ関数を通じて受け取る一意のコードです。次に、長さ - 1 に対してビット単位の AND 演算を実行します。これは、ハッシュ コードをバケットの数で割った余りを計算することに相当し、バケット配列内のインデックスを決定します。

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

その結果、各キーはハッシュ関数を通過して独自の一意のルームに到達し、そのインデックスはビットごとの AND を使用して計算されます。

衝突チェック: バケットが空の場合、新しいキーと値のペアが追加されます。そうでない場合、putVal はキーが一致するかどうかをチェックします:

* に一致 - 値が更新されます。
*一致しません - 競合が発生します - それらについてさらに詳しく説明します。

衝突: 互いに開く秘密の部屋

2 つの鍵が同じ部屋にある場合 (複数の鍵が 1 つのバケツにつながっている場合) はどうなりますか? HashMap では、これを衝突と呼びます。これは、2 つのキーが同じハッシュ コードを持ち、同じバケットに入ろうとしている場合です。これはいつ可能になりますか?たとえば、ハッシュ コードを誤ってオーバーライドしました。

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    ....
}

この例では、KeyWithSameHash クラスには、すべてのインスタンスに同じ値を返すオーバーライドされた hashCode() メソッドがあり、すべてのキーがテーブル配列の同じセルに配置されます。

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

すべてのキーの hashCode() 値は 42 になるため、キーが追加されるたびに、テーブル内のバケット インデックスは同じになります。

しかし、鍵は頭をぶつける代わりに、追加のドアを開き、部屋を新しい部屋につながる魔法の廊下に変えます。これらの新しい部屋は基本的に衝突を解決する方法です。

リンク リスト: 同じハッシュ コードを持つ 2 つのキーが同じバケット内に存在する場合、HashMap はそのバケット内にリンク リストを作成します。キーは引き続きこのリストに保存され、必要に応じて、equals() メソッドを使用してチェックが行われ、キーが実際に同じであることが確認されます。

赤黒ツリー: 1 つのバケット内の衝突数が多すぎる (コリドーが長すぎる) 場合、HashMap はバケットを赤黒ツリーに変換します。これにより、検索が高速化され、高負荷時の速度低下を防ぐことができます。

equals() と hashCode() の仕組み

HashMap マジックが正しく機能するには、同じ値を持つ 2 つの同一のキーが同じハッシュ コードを返し、また、equals() メソッドを使用して正しく比較されることが重要です。これは、2 つのオブジェクトが、異なる方法で表現されている場合でも、同じであるかどうかをチェックする呪文のようなものです。

hashCode(): 各オブジェクトには独自の一意のハッシュ コードが必要です。これにより、HashMap はキーを配置する必要があるバケットを効率的に見つけることができます。
equals(): 2 つのオブジェクトが同じハッシュ コードを持つ場合、equals() メソッドはオブジェクトが実際に同じかどうかを確認します。
このチェックが存在しない場合、HashMap は 2 つの異なるキーを混同し、プログラムの誤った動作につながる可能性があります。

結論

HashMap の世界は、ハッシュ関数と衝突によってキーが自分の部屋を見つけ、城を整理整頓するのに役立つ魔法の世界です。各キーには、ハッシュ関数のおかげで、一意のインデックスにつながる独自のパスがあります。そして、同じバケツの中で 2 つの鍵が衝突しても、魔法は働き続け、リンクされたリストや赤黒の木の形で新しい扉が開き、正しい道を見つけます。

hashCode()、equals()、および魔法のコリジョン コリドーのおかげで、HashMap は Java 開発者の武器庫の中で最も強力なツールの 1 つであり続け、最も混乱した状況でも効率と精度を保証します。

以上がHashMap: 秘密の部屋、魔法、衝突の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。