HashMapはどのように実装されているので、キーと値をすばやくマッピングできますか?

1.概要

HashMapはキーで要素を検索できます.
キーと値のリストがあるとします.必要なキーを検索するにはどうすればいいですか?

が望む鍵を見つける前に、すべてのリストを巡回します.

特定の計算によって所望の鍵を直接見つける.

1号法の時間的複雑度はO(N)である.リストがソートされている場合、バイナリ検索ツリーはO(logn)の時間的複雑さを有する.
2号法では時間複雑度は平均O(1)であった.また,HashMapは第2の方法によって実現される.では、HashMapがどのように機能しているかを詳しく見てみましょう.

1.2キーの適当な数は？

では、何個の要素があるか分からない場合、何個のキーを生成する必要があるのでしょうか.
例えば、身長はアルファベットの小文字にすぎないと仮定します.この場合、26個のキーリストだけで十分です.「d」キーを持つエンティティにアクセスするには、位置が4の場合、直接検索できます.
ただし、ユーザーが次のように宣言する場合を考えてみましょう.

HashMap<Integer, String> map = new HashMap<>();

Integer.MAX VALUE値は2147483647です.いくらデータが多くても、整数の最値まですべての要素を含めることはできません.この場合、割り当てられたメモリの多くの部分が未使用になり、スペースが浪費され、検索効率が低下します.
したがって、HashMapは要素をbucketに格納し、これらのbucketの数を容量と呼ぶ.bucketは韓国語でバケツに訳して、要素を入れたバケツだと思うと気持ちがいいです
Mapコレクションに値を入れる場合、キーのhashCode()メソッドは、格納された値のパケットを決定するために使用されます.そして、値を検索するために、HashMapはHashCode()を用いて同じようにパケットを計算する.次に、bucketでオブジェクトを検索し、キーのequals()メソッドを使用して正しい一致するアイテムを検索します.
整理すると、HashMapはすべての要素を巡回するのではなく、キーに基づいて値の位置を計算します.

1.3ハッシュ競合

要素を入れるときに必要な数だけ必要で、検索時にも直接キーを検索するので、どの条件でも時間複雑度はO(1)である可能性がありますが、最悪の場合、時間複雑度はO(N)である可能性があります.
デフォルトでは、同じキーには同じハッシュが必要ですが、異なるキーには同じハッシュがある場合があります.
異なるキーで同じハッシュである場合、そのキーに属する値は同じbucketに格納されます.
bucket内部では、値がListに格納され、すべての要素が巡回検索されます.このときの時間的複雑度はO(N)である.Java 8から、1つのbucketに8つ以上の値が含まれている場合、リストからバランスツリーに変更され、時間複雑度はO(logn)となる.
Javaハッシュ競合の詳細については、次のWebサイトを参照してください.
( https://d2.naver.com/helloworld/831311 )

2.内部実施HashMap

原理を理解した以上、Javaコードがジェネレータと主な方法をどのように実現しているかを見てみましょう.

2.1ジェネレータ

次はJavaのHashMapクラスの内部コードです.

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

   
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

   
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

    
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

コンストラクション関数のパラメータにはinitialCapcityとloadFactorがあります.

2.1.1 initialCapacity

ブラケットの初期容量のパラメータを設定します.基本初期容量は16です.
ちなみに、HashMapは複数の値のbucketを阻止するために、bucketの75%が空でなければcapsityが自動的に倍増します.

2.1.2 load factor

これは、HashMapのパケット容量を増加させるパーセント値です.
デフォルト値は0.75 fであり、容量が75%に達すると再ハッシュが発生する.
Rehashing?
パケットの容量がしきい値に達すると、JavaはRehashingと呼ばれる容量を2倍に増やします.
ex) 24, 25, 26 ...

2.2方法

HashMapには多くの方法があるが,主に検索と挿入に用いられるput()とget()の方法を重点的に紹介する.その他の方法はjava公式APIドキュメントを参照してください.
リンク:https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

2.2.1 put()メソッド

以下にputメソッドを実装するJavaコードを示す.

V put(K key, V value);

次のコードはサンプルコードです.元のインスタントラーメンキーと値を追加すると、キーオブジェクトのhashCode()が呼び出されて初期ハッシュ値が検索されますが、次の例のコードで再定義されたhashCode()は、メソッド呼び出しの出力のみを表示するように記述されます.

public class CustomKey{
    private int id;

   	//Getter, Setter, Constructor

    @Override
    public int hashCode() {
        System.out.println("hashCode Method called");
        return id;
    }
}

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        CustomKey key = new CustomKey(1);
        Map<CustomKey, String> map = new HashMap<>();

        map.put(key, "value");
    }
}

main関数を実行すると、hashCode()メソッドというhashCodeメソッドが出力されます.
次の方法はhash()方法です.この方法は、初期ハッシュ値によって最終ハッシュ値を計算する.この最終ハッシュ値は、内部配列のインデックスまたはパケット位置になります.メソッドの実装部分は次のとおりです.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

返された値から、最終的なハッシュ値は、キーオブジェクトのhashCodeのみを使用して計算されることがわかります.次に、put関数の内部で、最終ハッシュ値は次のようになります.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

内部putVal法の最初のパラメータhash(key)は最終的なハッシュ値である.
我々はkeyを用いてhash値を計算したが,方法の2番目のパラメータが再びkeyを用いたのはhashマッピングがキーと値をbucket位置にマッピングするためである.これはEntryオブジェクトとして格納されているためです.
これもJavaのCollectionフレームワークがMapを実現しなかった理由です.
Mapは他の集合のように個々の要素を正確に格納するのではなく,キー値対の集合を格納するため,AddなどのCollectionインタフェースの方法はMapでは意味がない.

2.2.2 get() method

保存されたオブジェクトを検索するには、そのオブジェクトに格納されている鍵を知る必要があります.get()もput()と同じハッシュ操作を実行する.
オブジェクトのhashCode()メソッドが呼び出され、初期ハッシュ値が取得されます.次にhash()メソッドを呼び出して最終的なhash値を取得し、その値によってパケットの場所を検索します.

2.2.3許容空

HashTableとは異なり、HashMapではキーと値がnullになります.put()メソッドが実行中にnullキーを発見すると、最終的なハッシュ値は自動的に0になります.これは、HashMapの最初の要素になることを意味します.キーがnullの場合、値は0になっているのでhash()操作は発生しないため、Null PointerExceptionは発生しません.