内部のJavaHashMap

投稿日: 2022-10-18 2022-10-18
タグ: Java, Java Collections, Java Map

1. 概要

この記事では、Javaコレクションフレームワークからの Map インターフェースの最も一般的な実装について詳しく説明し、イントロの記事が中断したところを取り上げます。

実装を開始する前に、プライマリListおよびSetコレクションインターフェイスはCollectionを拡張しますが、Mapは拡張することを指摘することが重要です。いいえ。

簡単に言うと、 HashMap はキーごとに値を保存し、保存されたデータをさまざまな方法で追加、取得、操作するためのAPIを提供します。実装はハッシュテーブルの原則に基づいています。これは最初は少し複雑に聞こえますが、実際には非常に理解しやすいものです。

キーと値のペアは、バケットと呼ばれるものに格納されます。バケットは、実際には内部配列であるテーブルと呼ばれるものを一緒に構成します。

オブジェクトが保存されている、または保存されるキーがわかれば、ストレージおよび取得操作は一定時間、 O（1）で適切なサイズのハッシュマップで実行されます。

内部でハッシュマップがどのように機能するかを理解するには、 HashMap。これらに重点を置きます。

最後に、 HashMap関連の質問はインタビューで非常に一般的であるため、これはインタビューを準備するか、インタビューの準備をするための確実な方法です。

**2. put（） API**

ハッシュマップに値を格納するために、2つのパラメーターを受け取る putAPIを呼び出します。キーと対応する値：

V put(K key, V value);

キーの下のマップに値が追加されると、キーオブジェクトの hashCode（） APIが呼び出され、初期ハッシュ値と呼ばれるものが取得されます。

これが実際に動作することを確認するために、キーとして機能するオブジェクトを作成しましょう。ハッシュの最初のフェーズをシミュレートするためのハッシュコードとして使用する単一の属性のみを作成します。

public class MyKey {
    private int id;
   
    @Override
    public int hashCode() {
        System.out.println("Calling hashCode()");
        return id;
    }

    // constructor, setters and getters 
}

これで、このオブジェクトを使用して、ハッシュマップの値をマップできます。

@Test
public void whenHashCodeIsCalledOnPut_thenCorrect() {
    MyKey key = new MyKey(1);
    Map<MyKey, String> map = new HashMap<>();
    map.put(key, "val");
}

上記のコードでは何も起こりませんが、コンソールの出力に注意してください。実際、hashCodeメソッドが呼び出されます。

Calling hashCode()

次に、ハッシュマップの hash（） APIが内部的に呼び出され、初期ハッシュ値を使用して最終ハッシュ値が計算されます。

この最終的なハッシュ値は、最終的には内部配列のインデックス、またはバケットの場所と呼ばれるものに要約されます。

HashMapのhash関数は次のようになります。

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

ここで注意すべきことは、最終的なハッシュ値を計算するためにキーオブジェクトからのハッシュコードを使用することだけです。

put 関数内では、最終的なハッシュ値は次のように使用されます。

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

内部putVal関数が呼び出され、最初のパラメーターとして最終ハッシュ値が指定されていることに注意してください。

ハッシュ値の計算にキーをすでに使用しているので、なぜこの関数内でキーが再び使用されるのか不思議に思うかもしれません。

その理由は、ハッシュマップがキーと値の両方をバケットの場所にMap.Entryオブジェクトとして格納するためです。

前に説明したように、すべてのJavaコレクションフレームワークインターフェイスは Collection インターフェイスを拡張しますが、Mapは拡張しません。前に見たMapインターフェースの宣言をSetインターフェースの宣言と比較してください。

public interface Set<E> extends Collection<E>

その理由は、マップは、他のコレクションのように単一の要素を正確に格納するのではなく、キーと値のペアのコレクションを格納するためです。

したがって、 add 、 toArrayなどのCollectionインターフェイスの一般的なメソッドは、Mapに関しては意味がありません。

最後の3つの段落で説明した概念は、最も人気のあるJavaコレクションフレームワークのインタビューの質問の1つになります。したがって、理解する価値があります。

ハッシュマップの特別な属性の1つは、null値とnullキーを受け入れることです。

@Test
public void givenNullKeyAndVal_whenAccepts_thenCorrect(){
    Map<String, String> map = new HashMap<>();
    map.put(null, null);
}

put操作中にnullキーが検出されると、最終ハッシュ値0 が自動的に割り当てられます。これは、基になる配列の最初の要素になることを意味します。

これは、キーがnullの場合、ハッシュ操作がないため、キーの hashCode APIが呼び出されず、最終的にnullポインター例外が回避されることを意味します。

put 操作中に、以前に値を格納するためにすでに使用されたキーを使用すると、キーに関連付けられた以前の値が返されます。

@Test
public void givenExistingKey_whenPutReturnsPrevValue_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("key1", "val1");

    String rtnVal = map.put("key1", "val2");

    assertEquals("val1", rtnVal);
}

それ以外の場合は、 null：を返します。

@Test
public void givenNewKey_whenPutReturnsNull_thenCorrect() {
    Map<String, String> map = new HashMap<>();

    String rtnVal = map.put("key1", "val1");

    assertNull(rtnVal);
}

put がnullを返す場合、キーに関連付けられている以前の値がnullであることを意味する場合もありますが、必ずしも新しいキーと値のマッピングであるとは限りません。

@Test
public void givenNullVal_whenPutReturnsNull_thenCorrect() {
    Map<String, String> map = new HashMap<>();

    String rtnVal = map.put("key1", null);

    assertNull(rtnVal);
}

containsKey APIを使用して、次のサブセクションで説明するようなシナリオを区別できます。

**3. get API**

ハッシュマップにすでに保存されているオブジェクトを取得するには、そのオブジェクトが保存されているキーを知っている必要があります。 get APIを呼び出し、それにキーオブジェクトを渡します。

@Test
public void whenGetWorks_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("key", "val");

    String val = map.get("key");

    assertEquals("val", val);
}

内部的には、同じハッシュ原理が使用されます。 キーオブジェクトのhashCode（） APIが呼び出され、初期ハッシュ値が取得されます。

@Test
public void whenHashCodeIsCalledOnGet_thenCorrect() {
    MyKey key = new MyKey(1);
    Map<MyKey, String> map = new HashMap<>();
    map.put(key, "val");
    map.get(key);
}

今回は、MyKeyのhashCodeAPIが2回呼び出されます。 put に1回、 get に1回：

Calling hashCode()
Calling hashCode()

次に、内部 hash（） APIを呼び出してこの値を再ハッシュし、最終的なハッシュ値を取得します。

前のセクションで見たように、この最終的なハッシュ値は、最終的にバケットの場所または内部配列のインデックスに要約されます。

次に、その場所に格納されている値オブジェクトが取得され、呼び出し元の関数に返されます。

戻り値がnullの場合、キーオブジェクトがハッシュマップのどの値にも関連付けられていないことを意味している可能性があります。

@Test
public void givenUnmappedKey_whenGetReturnsNull_thenCorrect() {
    Map<String, String> map = new HashMap<>();

    String rtnVal = map.get("key1");

    assertNull(rtnVal);
}

または、単にキーがnullインスタンスに明示的にマップされたことを意味する場合もあります。

@Test
public void givenNullVal_whenRetrieves_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("key", null);
        
    String val=map.get("key");
        
    assertNull(val);
}

2つのシナリオを区別するために、 containsKey APIを使用できます。このAPIにキーを渡し、ハッシュマップで指定されたキーに対してマッピングが作成された場合にのみtrueを返します。

@Test
public void whenContainsDistinguishesNullValues_thenCorrect() {
    Map<String, String> map = new HashMap<>();

    String val1 = map.get("key");
    boolean valPresent = map.containsKey("key");

    assertNull(val1);
    assertFalse(valPresent);

    map.put("key", null);
    String val = map.get("key");
    valPresent = map.containsKey("key");

    assertNull(val);
    assertTrue(valPresent);
}

上記のテストのどちらの場合も、 get API呼び出しの戻り値はnullですが、どちらがどちらであるかを区別できます。

**4. HashMapのコレクションビュー**

HashMap は、そのキーと値を別のコレクションとして扱うことを可能にする3つのビューを提供します。マップのすべてのキーのセットを取得できます。

@Test
public void givenHashMap_whenRetrievesKeyset_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set<String> keys = map.keySet();

    assertEquals(2, keys.size());
    assertTrue(keys.contains("name"));
    assertTrue(keys.contains("type"));
}

セットはマップ自体によって支えられています。したがって、セットに加えられた変更は、マップに反映されます。

@Test
public void givenKeySet_whenChangeReflectsInMap_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    assertEquals(2, map.size());

    Set<String> keys = map.keySet();
    keys.remove("name");

    assertEquals(1, map.size());
}

値のコレクションビューを取得することもできます。

@Test
public void givenHashMap_whenRetrievesValues_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Collection<String> values = map.values();

    assertEquals(2, values.size());
    assertTrue(values.contains("baeldung"));
    assertTrue(values.contains("blog"));
}

キーセットと同様に、このコレクションで行われたの変更は、基になるマップに反映されます。

最後に、マップ内のすべてのエントリのセットビューを取得できます。

@Test
public void givenHashMap_whenRetrievesEntries_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set<Entry<String, String>> entries = map.entrySet();

    assertEquals(2, entries.size());
    for (Entry<String, String> e : entries) {
        String key = e.getKey();
        String val = e.getValue();
        assertTrue(key.equals("name") || key.equals("type"));
        assertTrue(val.equals("baeldung") || val.equals("blog"));
    }
}

ハッシュマップには特に順序付けされていない要素が含まれているため、 foreachループのエントリのキーと値をテストするときに任意の順序を想定していることに注意してください。

多くの場合、最後の例のようにコレクションビューをループで使用し、より具体的にはそれらのイテレータを使用します。

上記のすべてのビューのイテレータはフェイルファストであることを覚えておいてください。

マップ上で構造上の変更が行われた場合、イテレータが作成された後、同時変更の例外がスローされます。

@Test(expected = ConcurrentModificationException.class)
public void givenIterator_whenFailsFastOnModification_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set<String> keys = map.keySet();
    Iterator<String> it = keys.iterator();
    map.remove("type");
    while (it.hasNext()) {
        String key = it.next();
    }
}

で許可されている構造変更は、イテレータ自体を介して実行されるremove操作のみです。

public void givenIterator_whenRemoveWorks_thenCorrect() {
    Map<String, String> map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set<String> keys = map.keySet();
    Iterator<String> it = keys.iterator();

    while (it.hasNext()) {
        it.next();
        it.remove();
    }

    assertEquals(0, map.size());
}

これらのコレクションビューについて覚えておくべき最後のことは、反復のパフォーマンスです。これは、ハッシュマップが対応するリンクされたハッシュマップおよびツリーマップと比較して非常にパフォーマンスが低い場所です。

ハッシュマップの反復は、最悪の場合 O（n）で発生します。ここで、nはその容量とエントリ数の合計です。

5. HashMapのパフォーマンス

ハッシュマップのパフォーマンスは、初期容量と負荷率の2つのパラメーターの影響を受けます。容量はバケットの数または基になるアレイの長さであり、初期容量は単に作成中の容量です。

負荷率（LF）は、要するに、サイズ変更される前にいくつかの値を追加した後、ハッシュマップがどれだけいっぱいになるかを示す尺度です。

デフォルトの初期容量は16で、デフォルトの負荷率は0.75です。初期容量とLFのカスタム値を使用してハッシュマップを作成できます。

Map<String,String> hashMapWithCapacity=new HashMap<>(32);
Map<String,String> hashMapWithCapacityAndLF=new HashMap<>(32, 0.5f);

Javaチームによって設定されたデフォルト値は、ほとんどの場合に最適化されています。ただし、独自の値を使用する必要がある場合は、これは非常に問題ありませんが、パフォーマンスへの影響を理解して、自分が何をしているのかを理解する必要があります。

ハッシュマップエントリの数がLFと容量の積を超えると、再ハッシュが発生します。 別の内部配列が最初の配列の2倍のサイズで作成され、すべてのエントリが新しい配列の新しいバケット位置に移動されます。

A 低い初期容量はスペースコストを削減しますが、は再ハッシュの頻度を増やします。再ハッシュは明らかに非常にコストのかかるプロセスです。したがって、原則として、多くのエントリが予想される場合は、かなり高い初期容量を設定する必要があります。

反対に、初期容量を高く設定しすぎると、反復時間でコストを支払うことになります。前のセクションで見たように。

したがって、高い初期容量は、反復がほとんどまたはまったくない多数のエントリに適しています。

低い初期容量は、反復回数が多い少数のエントリに適しています。

**6. HashMapでの衝突**

衝突、より具体的には、 HashMap でのハッシュコードの衝突は、 2つ以上のキーオブジェクトが同じ最終ハッシュ値を生成し、したがって同じバケット位置を指す状況です。または配列インデックス。

このシナリオは、equalsおよびhashCodeコントラクトに従って、Javaの2つの等しくないオブジェクトが同じハッシュコードを持つ可能性があるために発生する可能性があります。

また、基になる配列のサイズが有限であるため、つまりサイズ変更前に発生する可能性もあります。この配列が小さいほど、衝突の可能性が高くなります。

とは言うものの、Javaは、例を使用して見るハッシュコード衝突解決手法を実装していることは言及する価値があります。

オブジェクトが格納されるバケットを決定するのはキーのハッシュ値であることに注意してください。したがって、2つのキーのハッシュコードが衝突した場合でも、それらのエントリは同じバケットに保存されます。

また、デフォルトでは、実装はリンクリストをバケット実装として使用します。

最初は一定時間のO（1） putおよびget操作は、線形時間 O（n）の場合に発生します。衝突。これは、最終的なハッシュ値でバケットの場所を見つけた後、この場所の各キーが equalsAPIを使用して提供されたキーオブジェクトと比較されるためです。

この衝突解決手法をシミュレートするために、以前のキーオブジェクトを少し変更してみましょう。

public class MyKey {
    private String name;
    private int id;

    public MyKey(int id, String name) {
        this.id = id;
        this.name = name;
    }
    
    // standard getters and setters
 
    @Override
    public int hashCode() {
        System.out.println("Calling hashCode()");
        return id;
    } 
 
    // toString override for pretty logging

    @Override
    public boolean equals(Object obj) {
        System.out.println("Calling equals() for key: " + obj);
        // generated implementation
    }

}

id 属性をハッシュコードとして返すだけで、衝突が発生することに注意してください。

また、equalsおよびhashCodeの実装にログステートメントを追加したことにも注意してください。これにより、ロジックがいつ呼び出されるかを正確に知ることができます。

次に、ある時点で衝突するいくつかのオブジェクトを保存および取得します。

@Test
public void whenCallsEqualsOnCollision_thenCorrect() {
    HashMap<MyKey, String> map = new HashMap<>();
    MyKey k1 = new MyKey(1, "firstKey");
    MyKey k2 = new MyKey(2, "secondKey");
    MyKey k3 = new MyKey(2, "thirdKey");

    System.out.println("storing value for k1");
    map.put(k1, "firstValue");
    System.out.println("storing value for k2");
    map.put(k2, "secondValue");
    System.out.println("storing value for k3");
    map.put(k3, "thirdValue");

    System.out.println("retrieving value for k1");
    String v1 = map.get(k1);
    System.out.println("retrieving value for k2");
    String v2 = map.get(k2);
    System.out.println("retrieving value for k3");
    String v3 = map.get(k3);

    assertEquals("firstValue", v1);
    assertEquals("secondValue", v2);
    assertEquals("thirdValue", v3);
}

上記のテストでは、3つの異なるキーを作成します。1つは一意の id を持ち、他の2つは同じidを持ちます。初期ハッシュ値としてidを使用しているため、これらのキーを使用したデータの保存と取得の両方で、衝突が確実に発生します。

それに加えて、前に見た衝突解決手法のおかげで、保存された各値が正しく取得されることを期待しているため、最後の3行にアサーションがあります。

テストを実行すると、衝突が解決されたことを示す合格となるはずです。生成されたログを使用して、衝突が実際に発生したことを確認します。

storing value for k1
Calling hashCode()
storing value for k2
Calling hashCode()
storing value for k3
Calling hashCode()
Calling equals() for key: MyKey [name=secondKey, id=2]
retrieving value for k1
Calling hashCode()
retrieving value for k2
Calling hashCode()
retrieving value for k3
Calling hashCode()
Calling equals() for key: MyKey [name=secondKey, id=2]

ストレージ操作中に、k1とk2がハッシュコードのみを使用してそれらの値に正常にマッピングされたことに注意してください。

ただし、 k3 の保存はそれほど単純ではなく、システムはそのバケットの場所にk2のマッピングがすでに含まれていることを検出しました。したがって、 equals 比較を使用してそれらを区別し、両方のマッピングを含むリンクリストを作成しました。

キーが同じバケット位置にハッシュされる他の後続のマッピングは、同じルートをたどり、リンクリスト内のノードの1つを置き換えるか、equalsの比較でfalseが返された場合にリストの先頭に追加されます。既存のすべてのノード。

同様に、取得中、k3とk2は等しいでした-値を取得する必要がある正しいキーを識別するために比較されました。

最後に、Java 8から、特定のバケット位置での衝突の数が特定のしきい値を超えた後、リンクリストは衝突解決で平衡二分探索木に動的に置き換えられます。

衝突の場合、 O（log n）。で保存と取得が行われるため、この変更によりパフォーマンスが向上します。

このセクションは、技術面接で非常に一般的であり、特に基本的な保管と検索の質問の後です。

7. 結論

この記事では、Java MapインターフェースのHashMap実装について説明しました。

この記事で使用されているすべての例の完全なソースコードは、GitHubプロジェクトにあります。

getdocs

13036