HashMap は、データを (Key, Value) ペアで保存するデータ構造で、Python の Dictionary に似ています。
ハッシュマップの内部動作を理解するために、以下の用語に親しんでください。 ハッシュ関数は、数学的アルゴリズムにしたがって新しい値を生成するために使用されます。 ハッシュ関数の結果は、ハッシュ値または単にハッシュとして知られています。 8147>
真のハッシュ関数はこのルールに従わなければならない –
「ハッシュ関数は、同じまたは等しいオブジェクトに関数を適用すると、毎回同じハッシュコードを返す必要がある。 言い換えれば、2 つの等しいオブジェクトは一貫して同じハッシュ コードを生成する必要があります」
Java のすべてのオブジェクトは Object クラスで定義された hashCode() 関数のデフォルト実装を継承します。
2 つのキーが同じハッシュを生成し、それが同じアドレスにつながる可能性があることに留意してください。 この現象は衝突として知られています。
HashMap Functions
1. Public V get(Object key) : キーをもとにマップから値を取り出す。 Public V put(K key, V value) : またはキーと値のペアをマップに挿入する。
注意：一般に、equals()メソッドがオーバーライドされるときは、hashCode()メソッドをオーバーライドする必要があります。 指定された initial
capacity と load factor で空の HashMap を構築します。
public HashMap(int initialCapacity, float loadFactor)
2.Constructing an empty HashMap with the specified initial
capacity and the default load factor (0.75). 指定された initial
capacity とデフォルト負荷係数 (0.75) で、空の HashMap を構築します。
public HashMap(int initialCapacity)
3. デフォルトの初期容量 (16) およびデフォルトの負荷率 (0.75) で、空の HashMap を構築します。75).
public HashMap()
Load Factor and Initial Capacity.
HashMapのインスタンスは、そのパフォーマンスに影響を与える2つのパラメータを持っています。
1. 初期容量
2. 負荷係数.
初期容量 :
容量はハッシュテーブルのバケット数で、初期容量は単にハッシュテーブルが作成された時の容量です.
負荷係数.初期容量 :
初期容量はハッシュテーブルのバケット数で、初期容量はハッシュテーブルが作成された時の容量です.
負荷係数:
ロードファクターは、ハッシュテーブルがどの程度一杯になると自動的に容量が増加するかを示す指標である。 ハッシュ テーブル内のエントリの数がロード ファクターと現在の容量の積を超えると、ハッシュ テーブルは再ハッシュされ (つまり、内部データ構造が再構築され)、ハッシュ テーブルには約 2 倍のバケット数が存在するようになります。 より高い値はスペース オーバーヘッドを減少させますが、ルックアップ コストが増加します (get と put を含む HashMap クラスのほとんどの操作に反映されます。
マップ内のエントリの予想数とその負荷率を考慮して初期容量を設定し、リハッシュ処理の数を最小限にするようにします。
HashMap in Java 8
A HashMap (from java 8) stores data into multiple singlely linked lists of entries or multiple Red BlacK Trees or mixture of both , depending on the threshold, also called buckets or bins.
すべてのリスト/ツリーは、Entry (Entry<K,V> table)の配列に登録され、この内部配列のデフォルト容量は 16 です。
HashMapの1つのレコードまたはキーと値の1つのペアをEntry<Key,Value>と呼びます。
Entry
HashMapでは、データを格納するのに内部クラスEntry<K, V>を使用します。
このエントリは単純なキーと値のペアで、次のような 2 つの値が追加されています：
1. HashMap が単一リンクリストのようにエントリを格納できるように、またはより良い検索を提供するために左と右のノードを持つツリーとして別のエントリへの参照。
2. キーのハッシュ値を表すハッシュ値。 このハッシュ値は、HashMap がそれを必要とするたびにハッシュの計算を避けるために格納されます。
Java 8 のエントリは、2 つのタイプの LinkedList Node または RedBlack Tree Node になります。
transient Node<K,V> table; //すべてのエントリを含む。
テーブルでは、各インデックスは LinkedList または RedBlackTree のノードである。
Entryの階層は次のようになります：Map.Entry<K,V> → implements → Node<K,V> → extends → TreeNode<K,V>
LinkedList Node:
static class Node<K,V> implements Map.Node.Entry。Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //LinkedListを保持するためのクラスです。
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.K,V> next; //Node
はLinkedListを保持する。next = next;
}TreeNode:
HashMap, in java 8 , TREEIFY_THRESHOLD (default value 8) として知られる特定の閾値の後に RedBlackTree を使用します。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // 赤黒い木のリンク
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev.TREENode <K,V>; // 黒っぽい木
TREENODE <K, Vboolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}HashMap 関数の動作
1.Key, val, next, Node <K >1.nextを削除する。 keyがNULLかどうかをチェックします。 もしキーがNULLなら、NULLキーは常にハッシュ0、つまりテーブルのインデックス0にマップされます。 キーがNULLでない場合、メソッドはキーオブジェクトのhashCode()メソッドを呼び出し(それぞれのキークラスでユーザーによってオーバーライドされます)、返されたhashValueを独自の静的ハッシュ関数に適用して、キーと値がEntryという入れ子クラスの形で格納されるバケットの位置(バック配列)を見つけます。
注: 質の悪いハッシュ関数から保護するために、hash(hashValue) を使用してハッシュ値を再度計算しています。
3. 最終ハッシュ値は Entry オブジェクトが格納されるバケット位置を見つけるために使用されます。
get() と put() の複雑さは O(1) で、ハッシュ関数がバケット間で要素を適切に分散させると仮定します。注：ハッシュ衝突の場合、エントリオブジェクトはリンクリストのノードとして格納され、キーを比較するのに equals() メソッドが使われることは、もうお分かりでしょう。 この問題に対処するため、Java 8 のハッシュ要素は、ある閾値に達した後、リンクリストの代わりにバランス ツリーを使用します。 つまり、HashMap は最初は Entry オブジェクトをリンクリストに格納していますが、ハッシュ内のアイテム数がある閾値より大きくなると、ハッシュはリンクリストの使用からバランスドツリーに変わり、最悪の場合のパフォーマンスが O(n) から O(log n) に改善されるのです。 どれが必要かを判断するために、HashMap は equals() の助けを借ります。
解決策として equals() メソッドが助けに来てくれます。 バケットが1つで、同じハッシュコードを持つ2つのオブジェクトがあるので、
そこで、キーのインデックスを取得した後、そのインデックスに存在する最初のノードを取得する。
Else では、ノードのインスタンスを見つけ、このインデックスに格納されているデータがリンクリストまたは RedBlack ツリーの形式であるかどうかを判断します。public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {
Node<K,V> tab; //Entry
Node<K,V> first, e;
int n; K k;/*テーブルにエントリーがあるか調べる …*/if (first.hash == hash && /* 常に最初のノードをチェック*/
((k = first.key) == key|| (key != null && key.equals(k)))
return first;/* そのインデックスで最初のノードが検索中の値ではない場合、トラバースに進みます。
if ((e = first.next) != null) {
if (first instance of TreeNode)
/*赤黒木からの取得は、TreeNodeのifインデックスでNodeを開始した場合。return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {/* Start Node is of Node and not of Tree if the LinkedList from Fetchting the type of Nodes.*/
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))
return e;
}.
while ((e = e.next) != null);
}}
return null;
}PUT:
1. もしキーがヌルなら、ヌルキーは常にハッシュ0にマップされ、テーブルのインデックス0になります。 もしキーがヌルでなければ、このメソッドはキーオブジェクトのhashCode()メソッドを呼び出し（それぞれのキークラスでユーザーによってオーバーライドされる）、返されたhashValueを独自の静的ハッシュ関数に適用して、キーと値がEntryという入れ子のクラスの形で保存されるべきバケットの場所（バック配列）を見つけることができます。バケットの位置はEntryのインデックス、すなわちテーブルの位置である。
3 最終的なハッシュ値は、Entryオブジェクトが格納されるバケットの位置を見つけるために使用される。 そして、get()で説明したのと同じようにKeyを走査し、Keyがすでに存在するかどうかを調べ、存在する場合はその値を新しい値に置き換えます。
その後、リストのサイズをチェックし、
TREEIFY_THRESHOLD（デフォルト8）を超えた場合、ノードをRedBlackTreeに再構築し、新しいkeyをその値で保存する。
閾値を超えない場合、新しいEntryを各key-valueで作成し、それを保存する。public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V> tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null ｜| (n = tab.V) == null) { final V putVal(int hash, K key, value, v value)length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traversing as in get()*/
Node <K,V> e; K k;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.Hash == hash &&((p.key) == key !equals(k)))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.Null,
p.next = newNode(hash, key, value, null);
/*TREEIFY_THRESHOLD が超過しているかどうかをチェックするためです。*/if (binCount >= TREEIFY_THRESHOLD – 1) /* -1 for 1st*/
treeifyBin(tab, hash);
break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))
break;
p = e;
}if (e != null) { /* existing mapping for key*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = e.values; />
f (e != null))if (!value = value;
afterNodeAccess(e);
return oldValue;
}++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;}More To Read
キーの不滅性。
HashMap のキーの実装として Strings と Integer が優れている理由は何ですか? ほとんどの場合、これらは不変だからです! 8147>Rehashing:
Rehashing は、すでに保存されているエントリ (Key-Value ペア) のハッシュコードを再計算するプロセスで、Load factor threshold に達したときにそれらを別の大きなサイズのハッシュマップに移動させるために行います。
マップ内のアイテム数がLoad factorの制限を超えると、その時点でハッシュマップの容量が2倍になり、新しいバケットにKey-Valueペアを均等に分散するために、すでに保存されている要素のハッシュコードが再計算されます。なぜそれが必要なのか？
容量を2倍にした後、バケットにすでに存在するキーと値のペアをどうするか？既存のキーと値のペアをそのままにするなら、容量の倍増は助けにならないかもしれません。なぜなら、O（1）の複雑さは、すべてのバケットにアイテムが均一に分散されている場合にのみ達成されるからです。
そこで、既存のキーと値のペアのそれぞれについて、増加したハッシュマップの容量をパラメータとしてハッシュコードを再度計算し、その結果、アイテムを同じバケットに配置するか、別のバケットに配置するかを決定します。