jdk 1.8 HashMap詳細
JDK 1.8 HashMap詳細
一、基礎補充 hash競合解決方法(面接で質問される可能性があります) オープンアドレス法:競合するアドレスの次のアドレスが占有されているかどうかをクエリーし、空のアドレスが見つかるまで知る. 再ハッシュ法:ハッシュ関数を用いて前のhash値を再ハッシュする. 連アドレス法:hash値が等しいものについてはチェーンテーブルでリンクされているが,HashMapではこの方式 が採用されている.
二、ソース分析
HashMapの構造
まず、hashMapの主幹は、1つのノード配列(jdk 1.7および以前はEntry配列)であり、各ノードは、1つのnext、nextが次のnodeを指し、hashMapは複数のノードオブジェクトからなるkeyとvalueのキー値ペアを含む.
Nodeは、HhaspMapの静的内部クラスです.補足説明: Nodeは内部クラスであり、Map.Entry を継承している. NodeのhashCodeメソッドkeyとvalueのhashcode値異和演算を使用して を生成する.
HashMapのいくつかの重要なフィールド補足解釈 チェーンツリー化の臨界値は8であり、チェーンテーブルに劣化する臨界値は6であり、チェーンテーブル長が7と8で往復変化すると赤黒ツリーの頻繁な確立と劣化を引き起こし、効率がより低い を防止するためである.
構築方法
putのプロセス put()メソッド:
そのコアはputVal()メソッドであり、最初のパラメータはkeyに入力されたhashであり、hashを計算する方法は以下の通りである.
ここで、入力されたintタイプの値:①あるObjectタイプにintの値を割り当てると、int値は自動的にIntegerにカプセル化されます.2 integerタイプのhashcodeはすべて彼自身の値であり、すなわちh=keyである.h>>>16は符号なしで右に16ビット移動し、低位は押し出し、高位は0を補う.^ビット別または、すなわちバイナリに変換された後、異なる値は1であり、同じ値は0であることから、入力された値が2の16乗−1未満の場合、このメソッドを呼び出して返される値は、いずれも自身の値であることがわかる. putVal()メソッド: put全体を補足的に説明する過程は、 のステップにまとめることができる. tableが空または長さが0である、すなわちput操作が以前に行われていない場合はresize()を呼び出して初期化し、初期化後tableの長さをnに付与する. (n-1)&hashのハッシュ関数を使用して、配列内のtableに新たに追加された要素の位置を計算し、このハッシュ関数について詳細に説明する. は、その位置が空であるか否かを判断する、空であればその位置に直接新たなノードオブジェクトを付与し、空でなければその位置のノードのkeyが新たなノードのkeyと同一であるか否かを判断し、同一であれば置き換え、異なるならば現在のノードがTreeNodeであるか否か(すなわちツリー化されているか否か)を判断し、ツリー化されていればputTreeVal()メソッドを呼び出して赤黒ツリーに挿入する、ツリー化されていなければ、現在のノードをはじめとするチェーンテーブルをループし、最後まで尾挿し法で挿入し、ループ中にチェーンテーブル長を記録し、追加が完了した後にツリー化のしきい値8に達したらtreeifyBin()メソッドを呼び出してツリー化する. は、追加プロセスによってhash競合が発生したかどうかを判断し、競合が発生した場合、チェーンテーブルの前のノードの要素の値を返す. 修正回数、modCount++を記録し、fast-failメカニズムのために; 容量size++は、その後、臨界値より大きいか否かを判断し、臨界値より大きい場合はresize()を呼び出して拡容 を行う.
resize()メソッド補足解釈 まず、拡張後の容量は必ず元の2倍であり、境界判断がある. 拡張後、古い配列oldTableの要素を新しい配列tableにコピーします.この場合、元の要素については2つの場合しかありません.1つはアドレスが変わらないこと、2つは古い位置+oldCapの位置になることです.具体的な原因は後で詳しく説明します. jdk 1.8は挿入要素と拡張コピー時にテールプラグ法を採用し、jdk 1.7はヘッドプラグ法を採用し、マルチスレッドが動作するとリングチェーンテーブルを形成してデッドサイクルを引き起こす可能性があり、CPU 100% をもたらす.
get()メソッド
putに交差するプロセスでは、getは簡単で、ソースコードに直接接続されます.
コアはgetNode()メソッドを呼び出します.まとめ: hash値に基づいて配列中の位置を計算し、依然として(n−1)&hashを使用する. は、次に、現在位置の第1のノードが探しているノードであるかどうか、すなわち空またはkeyが等しいかどうかを判断し、等しい場合は第1のノードに直接戻り、そうでない場合は続行する. firstがツリーのヘッダノードであるか否かを判断し、first.getTreeNode(hash,key)を呼び出して赤黒ツリーを検索する. 木でなければ、チェーンテーブルをループすればよい.
いくつかの詳細 hashCodeに関する計算 なぜ符号なしで16ビット右シフトした後に異或演算 をするのか.
(h=key.hashCode()^(h>>16)演算を行うと、高領域と低領域のバイナリ特徴を低領域に混合することができますが、なぜそうするのでしょうか.
再計算された新しいハッシュ値は、hashmapにおける配列スロットの計算に後で関与することを知っています.計算式:(n-1)&hash、このとき配列スロットが16個あると、上記をよく見ると、高領域の16ビットが配列スロットのビット数のバイナリ符号ロックによって遮断される可能性が高いことがわかります.スロットビットを計算すると、高領域の特徴が失われます.高領域の特徴が異なるhashcodeを失っても異なるスロットビットを計算できると言えるかもしれませんが、2つのハッシュコードが近い場合、この高領域のわずかな違いがハッシュ衝突を引き起こす可能性があるので、パフォーマンスを極めた体現でもあります.異或演算を用いる原因異或演算は各部分の特徴をよりよく保持することができ、&演算で算出した値が1に近づくと、|演算で算出した値が0に近づく .
3.なぜスロット数が2^nでなければならないのか1、ハッシュ後の結果をより均一にするため 2、ビット演算e.hash&(newCap-1)で計算でき、a%(2^n)はa&(2^n-1)に等価であり、ビット演算の演算効率は算術演算より高い.算術演算がビット演算に変換されるか、ここでコードシート が挿入される
一、基礎補充
二、ソース分析
HashMapの構造
まず、hashMapの主幹は、1つのノード配列(jdk 1.7および以前はEntry配列)であり、各ノードは、1つのnext、nextが次のnodeを指し、hashMapは複数のノードオブジェクトからなるkeyとvalueのキー値ペアを含む.
Nodeは、HhaspMapの静的内部クラスです.
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
// hashCode key value hashcode
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry,?> e = (Map.Entry,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
HashMapのいくつかの重要なフィールド
// 16，0000 0001 4 0001 0000 16， 16，
// 2 ( 2 )
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// int 2
static final int MAXIMUM_CAPACITY = 1 << 30;
// 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// ， 8，
static final int TREEIFY_THRESHOLD = 8;
//hash ， 6，
static final int UNTREEIFY_THRESHOLD = 6;
// hashmap 64 ，
static final int MIN_TREEIFY_CAPACITY = 64;
// = *
int threshold;
構築方法
//initialCapacity ，loadFactor
public HashMap(int initialCapacity, float loadFactor) {
// 0，
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 0，
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 2
this.threshold = tableSizeFor(initialCapacity);
}
//tableSizeFor ， A， A 0， ，
// A 2 A， A A 2 。
// 7 8， 8 8， 9 16
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// ， ， 0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// ， 0.75， DEFAULT_INITIAL_CAPACITY=16， put
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// MAP
public HashMap(Map extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
putのプロセス
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
そのコアはputVal()メソッドであり、最初のパラメータはkeyに入力されたhashであり、hashを計算する方法は以下の通りである.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
ここで、入力されたintタイプの値:①あるObjectタイプにintの値を割り当てると、int値は自動的にIntegerにカプセル化されます.2 integerタイプのhashcodeはすべて彼自身の値であり、すなわちh=keyである.h>>>16は符号なしで右に16ビット移動し、低位は押し出し、高位は0を補う.^ビット別または、すなわちバイナリに変換された後、異なる値は1であり、同じ値は0であることから、入力された値が2の16乗−1未満の場合、このメソッドを呼び出して返される値は、いずれも自身の値であることがわかる.
//onlyIfAbsent true ，
//evict true ，
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// table ， 0， resize ， table （resize ）
if ((tab = table) == null || (n = tab.length) == 0)
/* resize， put ， 。
resize ：
newCap = DEFAULT_INITIAL_CAPACITY; 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
threshold = newThr; 16*0.75
Node[] newTab = (Node[])new Node[newCap];
table = newTab; node table， return newTab
resize ：
int oldThr = threshold;
newCap = oldThr; threshold， threshold 2 ，
tableSizeFor ， ，
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
threshold = newThr; (int)( * )
Node[] newTab = (Node[])new Node[newCap];
table = newTab; return newTab;
*/
n = (tab = resize()).length; // resize n
if ((p = tab[i = (n - 1) & hash]) == null) // hash
tab[i] = newNode(hash, key, value, null);// ， i node
else { //
Node e; K k;
if (p.hash == hash && // old new key
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // e=p
else if (p instanceof TreeNode) // p ，
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else { //p ，p treenode
for (int binCount = 0; ; ++binCount) { //
if ((e = p.next) == null) { //e=p.next, p next null
p.next = newNode(hash, key, value, null); //
if (binCount >= TREEIFY_THRESHOLD - 1) // 8
treeifyBin(tab, hash); //
break;
}
if (e.hash == hash && // ，
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // p next p, node p，
//
}
}
if (e != null) { // ： hash ，
//put ，
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) // ， oldvalue
// newvalue， oldvalue； ， oldvalue
e.value = value;
afterNodeAccess(e); //
return oldValue;
}
}
++modCount; //
if (++size > threshold) // ，
resize(); //
afterNodeInsertion(evict);
return null;
}
if (e != null)
resize()メソッド
// resize ，
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { //
if (oldCap >= MAXIMUM_CAPACITY) { // ， int
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // 2 ， 2
newThr = oldThr << 1;
}
else if (oldThr > 0) //
newCap = oldThr;
else { //
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { //
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // threshold
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab; // table
// ，
if (oldTab != null) { //
for (int j = 0; j < oldCap; ++j) { //
Node e;
if ((e = oldTab[j]) != null) { // node ， j
// e, oldTab ， ， ？？
// oldTab ， ？？
oldTab[j] = null;
if (e.next == null) // node
newTab[e.hash & (newCap - 1)] = e; // ， ，
// (oldCap - 1) & e.hash , ， ，
// +oldCap
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
/* ， 。 oldCap 1， e.hash 0， ， ， loHead ， newTab[j]；
， +oldCap， lodCap 1， e.hash 1， ， hiHead ， newTab[j + oldCap]
：
：oldCap=16 ：0001 0000
oldCap-1=15 ：0000 1111
e1.hash=10 ：0000 1010
e2.hash=26 ：0101 1010
e1 ：e1.hash & oldCap-1 ：0000 1010
e2 ：e2.hash & oldCap-1 ：0000 1010
， e1 e2 ， 。
， ， e.hash & oldCap-1
， oldCap*2=32 0010 0000 newCap=32，
e1.hash & newCap-1
：0000 1010 & 0001 1111
0000 1010 。
e2.hash & newCap-1
：0101 1010 & 0001 1111
0001 1010, +oldCap。
e.hash & newCap-1 e.hash & oldCap， ，
0， 1。 0， ， 1 +oldCap。
loTail loHead （ (e.hash & oldCap) == 0 ）：
：
e oldTab[j] node ， e
loTail , loHead e node ， loTail node 。
， e next， oldTab
：
lotail null， lotail.next e， lotail node next e，
，loHead next e， oldTab 。 loHead
node 2 。 lotail=e 。
：
，loHead 3， node，loTail node
......
hiTail hiHead ， 。
，loHead ，loTail ，
。 (e.hash & oldCap) == 0 。
(e.hash & oldCap) == 0 ， oldCap ，
loHead hiHead ， newTab[j]
newTab[j+oldCap]
*/
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null; // next
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null; // next
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get()メソッド
putに交差するプロセスでは、getは簡単で、ソースコードに直接接続されます.
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
コアはgetNode()メソッドを呼び出します.
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
いくつかの詳細
(h=key.hashCode()^(h>>16)演算を行うと、高領域と低領域のバイナリ特徴を低領域に混合することができますが、なぜそうするのでしょうか.
再計算された新しいハッシュ値は、hashmapにおける配列スロットの計算に後で関与することを知っています.計算式:(n-1)&hash、このとき配列スロットが16個あると、上記をよく見ると、高領域の16ビットが配列スロットのビット数のバイナリ符号ロックによって遮断される可能性が高いことがわかります.スロットビットを計算すると、高領域の特徴が失われます.高領域の特徴が異なるhashcodeを失っても異なるスロットビットを計算できると言えるかもしれませんが、2つのハッシュコードが近い場合、この高領域のわずかな違いがハッシュ衝突を引き起こす可能性があるので、パフォーマンスを極めた体現でもあります.
3.なぜスロット数が2^nでなければならないのか