Map interface takes you to learn advanced features of Java language

Map インターフェイス

以前に Collection インターフェイスとそのサブインターフェイスを学びましたが、Collection インターフェイスに格納されるデータはすべて単一のオブジェクトであることがわかりました。データ構造においては、単一オブジェクトだけでなく、キーと値のペアを格納することもできます。オブジェクトは「キー=値」の形式で格納され、ペアで格納する核心的な意味は、キーを通じて対応する値を取得することにあります。

開発において、Collection コレクションにデータを保存する目的は出力のためであり、Map コレクションにデータを保存する目的はキーによる検索のためです。

Map インターフェイスは、キーと値のペアを格納する最上位の親インターフェイスです。インターフェイスの定義は以下の通りです：

public interface Map
このインターフェイスは独立した親インターフェイスであり、インターフェイスオブジェクトをインスタンス化する際に Key と Value の型を設定する必要があります。つまり、全体の操作を通じてキーと値の 2 つのコンテンツを保存する必要があります。Map インターフェイスには多くの操作メソッドが定義されていますが、以下のコア操作メソッドを覚えておく必要があります。

Map コレクションのデータは「キー=値」の形式で格納され、of() メソッドを使用する場合はデータの重複が許可されません。重複した場合、IllegalArgumentException 例外が発生します。null のコンテンツを設定した場合、NullPointerException が発生します。

ここで見た of() メソッドは、厳密には Map コレクションの標準的な使い方ではありません。通常の開発では、Map コレクションのサブクラスを使用してインターフェイスオブジェクトをインスタンス化する必要があり、よく使われるサブクラスは HashMap、HashTable、TreeMap、LinkedHashMap です。

HashMap サブクラス
HashMap は Map インターフェイスで最もよく使われるサブクラスです。このクラスの主な特徴は、データが順序付けされずに格納されることです。まず Java ドキュメントを通じて HashMap サブクラスの定義を確認しましょう：

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
このクラスの定義と継承形式は、前述のコレクション定義形式に準拠しており、依然として抽象クラスが提供され、Map インターフェイスも改めて実装する必要があります。

HashMap サブクラス

例：Map コレクションの使用を確認する

import java.util.HashMap;
import java.util.Map;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
Map map = new HashMap();
map. put("one",1);
map. put("two",2);
map.put("one",101); //key repeat
map.put(null,0); //key is null
map.put("zero",null); //value is null
System.out.println(map.get("one")); //key exists: 101
System.out.println(map.get(null)); //key exists: 0
System.out.println(map.get("ten")); //key does not exist: null
}
}
上記の操作形式は、Map コレクションで使用される最も標準的な処理形式です。コードを通じて、HashMap を介してインスタンス化された Map インターフェイスは、キーまたは値に null データを格納できることがわかります。エラーは発生せず、コンテンツの置換が発生します。

ただし、Map インターフェイス自体が提供する put() メソッドには戻り値があり、この戻り値はキーが重複した場合に古い値を返すことを指します。
例：put() メソッドを確認する

import java.util.HashMap;
import java.util.Map;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
Map map = new HashMap();
System.out.println(map.put("one", 1)); //key is not repeated, return null: null
System.out.println(map.put("one", 101)); //key is repeated, return old data: 1
}
}
同じキーのコンテンツが設定された場合、put() メソッドは元のデータコンテンツを返します。

HashMap の基本機能を明確にした後、次は HashMap で与えられたソースコードを研究します。大量のデータは必ず HashMap に格納される必要があるため、データ格納について、HashMap がどのように操作を行うかを見てみましょう：

public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
引数なしコンストラクタを使用する場合、loadFactor 属性があり、この属性のデフォルト内容は「0.75」です（static final float DEFAULT_LOAD_FACTOR = 0.75f;）

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put() メソッドを使用してデータを保存する場合、putVal() メソッドが呼び出され、同時にキーがハッシュ化され（ハッシュコードを生成）、putVal() メソッドでは、データ格納のために Node ノードクラスが提供され、putVal() メソッドを使用する過程で、容量拡張のために resize() メソッドが呼び出されます。

面接質問：HashMap の put() 操作を実行する際の容量拡張の実現方法は？

HashMap クラスには初期容量設定として「DEFAULT_INITIAL_CAPACITY」定数が提供されており、この定数のデフォルトサイズは 16 要素です。つまり、デフォルトで保存できる最大内容は 16 です。
保存する内容の容量が閾値（DEFAULT_LOAD_FACTOR=0.75f）を超えた場合、つまり「容量 * 閾値 = 12」に相当し、12 個の要素を保存する際に容量拡張が行われます。
拡張時、HashMap は 2 倍拡張方式を採用しています。つまり、毎回容量を 2 倍に拡張します。
面接質問：HashMap の動作原理を説明してください（JDK1.8 以降）

HashMap のデータ格納は依然として Node クラスを使用して行われるため、この場合、使用可能なデータ構造は 2 つしかないことが証明されます：連結リスト（時間計算量「O(n)」）、二分木（時間計算量「O(logn)」）。
JDK1.8 以降、HashMap の実装に変更が加えられました。ビッグデータ時代の膨大なデータ問題に適応する必要があるため、その格納方法が変更され、HashMap クラス内部に定数が提供されています：「static final int TREEIFY_THRESHOLD = 8;」。HashMap を使用してデータを保存する際、保存データが閾値 8（TREEIFY_THRESHOLD）を超えない場合は連結リストの形式で格納されます。閾値を超えた場合、連結リストは赤黒木に変換され、木のバランスを実現し、左回転と右回転を使用してデータの検索性能を確保します。
LinkedHashMap サブクラス
HashMap は Map コレクションで最もよく使われるサブクラスですが、格納されるデータは順序付けされていません（順序の有無は Map に影響しません）。Map コレクション内の格納データの順序を保持したい場合は、サブクラスを LinkedHashMap（リンクリストベース）に置き換えることができ、LinkedHashMap クラスの定義形式を確認できます：

public class LinkedHashMap extends HashMap implements Map
リンクリストで格納されるため、一般的に LinkedHashMap クラスを使用する際、データ量は特に大きくないはずです。時間計算量の上昇を引き起こすためです。継承構造を通じて、LinkedHashMap が HashMap のサブクラスであることがわかります。継承関係は以下の通りです：

LinkedHashMap

例：LinkedHashMap の使用

import java.util.LinkedHashMap;
import java.util.Map;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
Map map = new LinkedHashMap();
map. put("one", 1);
map. put("two", 2);
map. put("one", 101);
map. put("null", 0);
map. put("zero", null);
System.out.println(map); //{one=101, two=2, null=0, zero=null}
}
}
この時のプログラムの実行を通じて、LinkedHashMap を使用して格納する場合、すべてのデータの格納順序は追加順であることがわかります。

HashTable サブクラス
HashTable クラスは JDK1.0 から提供されており、Vector と Enumeration は最も初期の動的配列実装クラスに属していました。その後、保持するために、追加で Map インターフェイスの実装が許可されました。HashTable クラスの定義は以下の通りです：

public class Hashtable extends Dictionary implements Map, Cloneable, Serializable
HashTable の継承構造は以下の通りです：

HashTable サブクラス

例：HashTable サブクラスの使用方法を確認する

import java.util.Hashtable;
import java.util.Map;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
Map map = new Hashtable();
map. put("one", 1);
map. put("two", 2);
map. put("one", 101);
// map.put(null, 0); // cannot be empty
// map.put("zero",null); //Cannot be empty, Exception in thread "main" java.lang.NullPointerException
System.out.println(map); // {two=2, one=101}
}
}
観察を通じて、HashTable でデータを格納する際に設定されるキーまたは値は null を許可しないことがわかります。そうでなければ NullPointerException が発生します。

面接質問：HashMap と HashTable の違いを説明してください。

HashMap のメソッドはすべて非同期操作であり、スレッドセーフではありません。HashMap は null データの保存を許可します。
HashTable は同期メソッド（スレッドセーフ）であり、HashTable は null の保存を許可しません。そうでなければ NullPointerException が発生します。