1概要

この記事では、Java Collections Frameworkの

Map

インターフェースの最も一般的な実装について説明します。

実装を始める前に、

List



Set

の主要なコレクションインタフェースは

Collection

を拡張していますが

Map

は拡張していないことを指摘することが重要です。

簡単に言うと、

HashMap

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

キーと値のペアは、いわゆるテーブルと呼ばれるものを構成するバケットとして知られているものに格納されます。

オブジェクトが格納されている、または格納されるキーがわかると、** 格納および検索操作は、一定の時間内に発生します。

ハッシュマップが内部でどのように機能するのかを理解するには、__HashMapで採用されている格納および取得メカニズムを理解する必要があります。

最後に、


HashMap

関連の質問はインタビュー

で非常に一般的なので、これはインタビューを準備するか、それを準備するための確かな方法です。


2

put()

API

ハッシュマップに値を格納するために、2つのパラメータをとる

put

APIを呼び出します。キーと対応する値

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 Collections Frameworkのインタビューの質問

の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);
}

内部的には、同じハッシュ原則が使用されています。初期ハッシュ値を取得するために、キーオブジェクトの

The 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



hashCode

APIが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"));
    }
}

ハッシュマップは特に順序付けされていない要素を含んでいるので、

for each

ループ内のエントリのキーと値をテストするときは任意の順序を想定します。

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

上記のすべてのビューの

反復子は

fail-fast


であることを忘れないでください。

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

@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. ハッシュマップパフォーマンス


ハッシュマップのパフォーマンスは、

Initial Capacity



Load Factor

の2つのパラメータの影響を受けます。容量はバケットの数または基本となるアレイの長さであり、初期容量は単に作成中の容量です。

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

デフォルトの初期容量は

16

、デフォルトの負荷率は

0.75

です。

初期容量とLFのカスタム値を使ってハッシュマップを作成できます。

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

Javaチームによって設定されたデフォルト値は、ほとんどの場合に最適化されています。ただし、自分自身の値を使用する必要がある場合(これは大丈夫です)、自分が行っていることがわかるように、パフォーマンスへの影響を理解する必要があります。

ハッシュマップエントリの数がLFと容量の積を超えると、

rehashing

が発生します。つまり、最初のサイズの2倍のサイズで別の内部アレイが作成され、すべてのエントリが新しいアレイの新しいバケット位置に移動されます。 。

  • 低い初期容量

    はスペースコストを削減しますが

    再ハッシュの頻度を増加させます** 。再ハッシュは明らかに非常に高価なプロセスです。そのため、原則として、多数のエントリを予想する場合は、かなり高い初期容量を設定する必要があります。

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

そのため、** 高い初期容量は、ほとんどまたはまったく反復しないで結合された多数のエントリに適しています。

  • 少ない初期容量は、多くの繰り返しを伴う少数のエントリに適しています。


6.

HashMap


での衝突

衝突、より具体的には、

HashMap

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

このシナリオは、

equals



hashCode

の規約に従って、Javaの2つの等しくないオブジェクトが同じハッシュコードを持つ可能性があるために発生する可能性があります。

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

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

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

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

衝突の場合、最初の一定時間

O(1)

put

および

get

操作は線形時間

O(n)

で行われます。これは、最終ハッシュ値を使用してバケットの場所を見つけた後、この場所にある各キーが

equals__APIを使用して提供されたキーオブジェクトと比較されるためです。

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

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

の実装にlogステートメントを追加したので、ロジックがいつ呼び出されるかを正確に知ることができます。

それでは、衝突したいくつかのオブジェクトを格納して検索しましょう。

@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

を使用しているので、これらのキーを使用したデータの格納と取得の両方で衝突が確実に発生します。

それに加えて、前に見た衝突解決のテクニックのおかげで、私たちは格納された値のそれぞれが正しく取り出されることを期待しています。

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

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__実装を調べました。

この記事で使われているすべての例の完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/java-collections-maps[GitHubプロジェクト]にあります。