JDKのソースコードのあれらの事の私の目の中のHashMap
ソース部分はHashMapから言えば、筆者がこの種類のソース部分を何度も見たからだ.同時に、ネット上では大雑把な紹介が多いような気がする.間違いがあったらコメントで指摘してください.修正をタイムリーに検証します.ありがとうございます.
次に私の目に映るHashMapについてお話しします.
jdkバージョン:1.8
ソースコードに深く入り込む前に、HashMapの全体的な構造を理解することは非常に重要なことであり、構造もソースコードのいくつかのHashMapに対する操作を体現しており、構造は大体以下の通りである.
上の構造図からもHashMapの実現構造:
類の注釈を見て、直接ソースの部分を見るのが最も良くて、大多数はすべて理解できないかもしれなくて、ここは他の人の翻訳を見ることができます:類の注釈の翻訳.本文の中で筆者は赤黒樹の部分について説明するつもりはなく、挿入と削除操作は様々な状態を引き起こし、対応する調整が必要であり、その後は単独で赤黒樹の基礎を書き、TreeNodeと結びつけて説明する.
まず、いくつかの名詞の概念をまとめて、初心者に理解しやすいようにします.
1.バケツ(bucket):配列に要素が格納されている場所、構造図を参照すると、実際には配列のインデックスの下の要素であり、この要素は木のルートノードまたはチェーンテーブルの最初のノードである可能性があります.もちろん、チェーンテーブルまたは赤と黒の木全体がバケツとして認識されています.
2.bin:バケツの各要素、すなわち赤黒ツリーの要素またはチェーンテーブルの要素.
上の名詞のほかに、ハッシュ表を理解したほうがいいので、参考にしてください.HashMapもハッシュ表の一つの実現であり、簡単に理解することができ、数学における余剰操作を類比することができ、範囲を固定し、大量のデータを境界のある範囲に入れ、余剰配置を求める.この操作はハッシュ表の一つの実現方式である.
次に、ソース・セクションの説明を行います.
クラス定義
AbstraactMapを継承してCloneableインタフェースを実現し、クローン機能を提供してSerializableインタフェースを実現し、シーケンス化をサポートし、シーケンス化伝送を便利にする
ここで興味深い質問があります.なぜHashMapはAbstractMapを継承し、Mapインタフェースを実現しなければならないのですか.興味のある方はstackoverflowの回答を見てみましょう.
https://stackoverflow.com/que...
変数の説明
方法を見る前にNode実装を見てください.
重点説明
注釈には、プロセスの整理を支援するタグを追加します.また、後で対照と参照をまとめるのに便利です(例えば、A 1、A 2は同じレベルです).
ポイントの部分は上のいくつかの方法で、残りのソースコードの部分は一つ一つ貼って分析しないで、私の上で説明した部分を理解することができて、基本的に赤と黒の木とjdk 1.8の新しい特性の関連部分を除いて、残りの部分は基本的にすべて理解することができるべきで、ここで更に1つのシーケンス化の方面の問題を補充します:
なぜHashMapのtable変数をtransientに設定するのですか?この問題を理解する前に、シーケンス化コードwriteObjectとreadObjectを自分で見て、次のリンクを参考に考えてみましょう.
https://segmentfault.com/q/10...
HashMapでは、Entryの格納位置がKeyのHash値に基づいて計算され、配列に格納されるため、同じKeyに対して異なるJVM実装で計算されたHash値が異なる場合がある.私はもともとwindowマシンでAはNode配列の中で0の位置に置かれていたのですが、MacではNode配列の中で5の位置に置かれていたのかもしれませんが、修正しないと逆シーケンス化後もMacでは0の位置になり、これにより後続の増加ノードが錯乱し、私たちが望んでいた結果ではないので、シーケンス化でHashMapはキー値ペアごとのキーと値をシーケンス化し、全体ではなく、逆シーケンス化して1つずつ取り出し、位置の乱れを起こさない.
ではJDK 1.8でHashMapはマルチスレッド環境でデッドサイクルをもたらすのでしょうか?
上记の构造と処理过程の分析から见ると、できないはずですが、データの紛失が発生するかどうかは、私は検証しません.自分でGoogle、手書きコードで検証します.また、HashMapが非スレッドで安全であることを一般開発者が知っている場合は、マルチスレッドの場合はConcurrentHashMapを使えばいいと思います.後でConcurrentHashMapの分析も整理します.
まとめ
重点説明部分ではresizeとputの操作過程を詳しく説明しましたが、一部の新人はまだ整理できないかもしれません.私はここで日常の使用と結びつけて、全体の過程をまとめて、皆さんの理解を便利にします.
1.HashMap作成プロセス(通常の状態):
2.HashMap resizeプロセス(正常状態):
3.HashMapputプロセス(正常状態):
HashMapはまずその内部の実現構造を理解する必要がある:
本文はまず基礎部分から話して、いくつかの名詞を説明して、ハッシュ表に言及して、構造を実現することから各位のもっと良い理解のソースコードの操作部分を助けて、重点のいくつかの部分に対して詳しい説明をして、resizeとputの操作の難点部分も相応の解釈をして、各位に対して役に立つことを望んで、後で暇があれば私は赤い黒い木の部分の理解を分かち合います.ありがとうございます.
次に私の目に映るHashMapについてお話しします.
jdkバージョン:1.8
ソースコードに深く入り込む前に、HashMapの全体的な構造を理解することは非常に重要なことであり、構造もソースコードのいくつかのHashMapに対する操作を体現しており、構造は大体以下の通りである.
上の構造図からもHashMapの実現構造:
+ + が見られるはずです.類の注釈を見て、直接ソースの部分を見るのが最も良くて、大多数はすべて理解できないかもしれなくて、ここは他の人の翻訳を見ることができます:類の注釈の翻訳.本文の中で筆者は赤黒樹の部分について説明するつもりはなく、挿入と削除操作は様々な状態を引き起こし、対応する調整が必要であり、その後は単独で赤黒樹の基礎を書き、TreeNodeと結びつけて説明する.
まず、いくつかの名詞の概念をまとめて、初心者に理解しやすいようにします.
1.バケツ(bucket):配列に要素が格納されている場所、構造図を参照すると、実際には配列のインデックスの下の要素であり、この要素は木のルートノードまたはチェーンテーブルの最初のノードである可能性があります.もちろん、チェーンテーブルまたは赤と黒の木全体がバケツとして認識されています.
2.bin:バケツの各要素、すなわち赤黒ツリーの要素またはチェーンテーブルの要素.
上の名詞のほかに、ハッシュ表を理解したほうがいいので、参考にしてください.HashMapもハッシュ表の一つの実現であり、簡単に理解することができ、数学における余剰操作を類比することができ、範囲を固定し、大量のデータを境界のある範囲に入れ、余剰配置を求める.この操作はハッシュ表の一つの実現方式である.
次に、ソース・セクションの説明を行います.
クラス定義
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable AbstraactMapを継承してCloneableインタフェースを実現し、クローン機能を提供してSerializableインタフェースを実現し、シーケンス化をサポートし、シーケンス化伝送を便利にする
ここで興味深い質問があります.なぜHashMapはAbstractMapを継承し、Mapインタフェースを実現しなければならないのですか.興味のある方はstackoverflowの回答を見てみましょう.
https://stackoverflow.com/que...
変数の説明
/**
* Node ，16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* Node ，
*/
/**
*
* ？
* 。
* ， rehash （ ）。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* ， ，
* ， ， 。
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* resize ，
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* ，
* resize
*
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
*
* ，put
* ，
*/
transient Node[] table;
/**
*
* entrySet key value
*/
transient Set> entrySet;
/**
*
* ，
*/
transient int size;
/**
*
* ，fail-fast ， ， google
* ， ：
* A a,modCount=expectedModCount 1， ， B a,modCount=2， A modCount<>expectedModCount,
* ， ，
*/
transient int modCount;
/**
*
* ， （ * ） ，
*/
int threshold;
/**
*
*
*/
final float loadFactor; 方法を見る前にNode実装を見てください.
/**
* Node
* next
* ，
*/
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() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
/**
* Map.Entry
*
*/
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;
}
} 重点説明
注釈には、プロセスの整理を支援するタグを追加します.また、後で対照と参照をまとめるのに便利です(例えば、A 1、A 2は同じレベルです).
/**
* 0.75f
* A1
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* ，
* A2
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
*
* A2
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//
// ， ，
// resize ，resize ，
// ：https://www.cnblogs.com/liujinhong/p/6576543.html
// ，
this.threshold = tableSizeFor(initialCapacity);
}
/**
* m map
*/
public HashMap(Map extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* evict ， ， afterNodeInsertion(evict)，
* LinkedHashMap ，
*/
final void putMapEntries(Map extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
/**
* table
*/
if (table == null) { // pre-size
// ， m map
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// t
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
/**
* map ， ，
*/
resize();
/**
* ， entrySet putVal m Node key value
* ，
* putVal ，hash(key)，map put
* ：https://www.cnblogs.com/liujinhong/p/6576543.html
* ，
*/
for (Map.Entry extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
/**
* ,
*
* ， 2 N （ ）， HashMap(int initialCapacity)，
* ， resize * ，
* 1000 threshold=1024， ， ，
* 1024 * 0.75 = 768， Node 1024，size=1,
* 769 ， resize ，threshold=1536，Node 2048， ，
* ， HashMap ，
* debug
*/
final Node[] resize() {
//oldTab Node
Node[] oldTab = table;
// oldCap null 0， Node
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//
int oldThr = threshold;
// （ ），
int newCap, newThr = 0;
// 1.
// B1
if (oldCap > 0) {
// Node ， ， Integer.MAX_VALUE
if (oldCap >= MAXIMUM_CAPACITY) {
// C1
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 2 ，
// Node ，
// map 2 ， ,
// ， map 2
// newCap
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// C2
newThr = oldThr << 1; // double threshold
}
// 2.
// oldCap = 0 ， oldThr > 0 map
// ，threshold 0
// B2
else if (oldThr > 0) // initial capacity was placed in threshold
// put （ put ）
//
// ， 1024
newCap = oldThr;
// 3.
// B3
else { // zero initial threshold signifies using defaults
// = ， = *
// 16， 12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
/**
* ， ， newThr ， ， newThr
* 0， ：
* ：
* 1. node node 16
* 2. ， put newThr
* D1
*/
if (newThr == 0) {
// ft = *
float ft = (float)newCap * loadFactor;
// ft ft, int
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// ，
//
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// Node
Node[] newTab = (Node[])new Node[newCap];
// Node ，
table = newTab;
// E1
if (oldTab != null) {
// ，
for (int j = 0; j < oldCap; ++j) {
Node e;
//
if ((e = oldTab[j]) != null) {
// ， GC
oldTab[j] = null;
if (e.next == null)
// Node , 1
// ，
// ？
// ， ， hash （ ， HashMap hash(key) ）
// ， ， ，
// & e.hash n ，n newCap - 1
// 16， 10000， 1111， 4
// tableSizeFor 16
// & ， ，
// putVal ，
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// e.next ， ，
// ， ，
// ， ，
// ， ， ， 。
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
/**
* HashMap ，
* ，
*
* ， ， 16， 32（ ， ）
* ？
* ？
*
* put ， ，putVal
* (n - 1) & hash newTab[e.hash & (newCap - 1)]
* ？ ？
* ， ，
* （hi ） hiHead,hiTail
* （lo ） loHead,loTail
* ？
* ，
*/
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
//
do {
next = e.next;
/**
* e.hash & oldCap = 0
* ，
* ：
* oldCap=32=100000（ ），newCap=64=1000000（ ）
* (oldCap-1) & hash
* 1 ， 0~oldCap-1
* e.hash & oldCap 1
* 0， 0
* ？
* ， ， bucket（ ） （ ）
* (newCap-1) & hash (oldCap-1) & hash ，
* 32 64， 1 ，
* 0， bucket ，
* 0， 1，
* ， bucket （ ）
* ， 1 0
* bucket ， bucket（ bucket），
* bucket（ bucket），
* ， ，
* bucket
* 32 64， 63-31=32=oldCap=10000（ ）
* oldCap
*/
if ((e.hash & oldCap) == 0) {
// Node =
// loHead,loTail ，
if (loTail == null)
// ，
loHead = e;
else
// ， ，next
loTail.next = e;
// ，
loTail = e;
}
else {
//
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// ， ，
if (loTail != null) {
// ， ， next ， next
loTail.next = null;
// j j ，
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// ， oldCap，
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
/**
* put
* hash，key hash ， ，HashMap
* onlyIfAbsent， ，true,
* evict，LinkedHashMap afterNodeInsertion ，
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// F1
if ((tab = table) == null || (n = tab.length) == 0)
// table 0 ， table ，
// ， ， putMapEntries
n = (tab = resize()).length;
// （ ）
// key
// G1
if ((p = tab[i = (n - 1) & hash]) == null)
// ，
tab[i] = newNode(hash, key, value, null);
// G2
else {
// ，
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// （ ） hash
// key ，e p ， key
// e p
e = p;
else if (p instanceof TreeNode)
// ， ，
// key, Node, null( Node)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// （ ）， ，
// ， key
// binCount bin ，
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// next next
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// ， ， treeifyBin ，
// ， bin TREEIFY_THRESHOLD=8， MIN_TREEIFY_CAPACITY=64
// ，
treeifyBin(tab, hash);
break;
}
//
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// map key Node ， ， key
// H1
if (e != null) { // existing mapping for key
//
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// onlyIfAbsent ，
e.value = value;
//
afterNodeAccess(e);
//
return oldValue;
}
}
++modCount;
// ， ， 1，
// ，
// I1
if (++size > threshold)
resize();
// afterNodeAccess，
afterNodeInsertion(evict);
return null;
} ポイントの部分は上のいくつかの方法で、残りのソースコードの部分は一つ一つ貼って分析しないで、私の上で説明した部分を理解することができて、基本的に赤と黒の木とjdk 1.8の新しい特性の関連部分を除いて、残りの部分は基本的にすべて理解することができるべきで、ここで更に1つのシーケンス化の方面の問題を補充します:
なぜHashMapのtable変数をtransientに設定するのですか?この問題を理解する前に、シーケンス化コードwriteObjectとreadObjectを自分で見て、次のリンクを参考に考えてみましょう.
https://segmentfault.com/q/10...
HashMapでは、Entryの格納位置がKeyのHash値に基づいて計算され、配列に格納されるため、同じKeyに対して異なるJVM実装で計算されたHash値が異なる場合がある.私はもともとwindowマシンでAはNode配列の中で0の位置に置かれていたのですが、MacではNode配列の中で5の位置に置かれていたのかもしれませんが、修正しないと逆シーケンス化後もMacでは0の位置になり、これにより後続の増加ノードが錯乱し、私たちが望んでいた結果ではないので、シーケンス化でHashMapはキー値ペアごとのキーと値をシーケンス化し、全体ではなく、逆シーケンス化して1つずつ取り出し、位置の乱れを起こさない.
ではJDK 1.8でHashMapはマルチスレッド環境でデッドサイクルをもたらすのでしょうか?
上记の构造と処理过程の分析から见ると、できないはずですが、データの紛失が発生するかどうかは、私は検証しません.自分でGoogle、手書きコードで検証します.また、HashMapが非スレッドで安全であることを一般開発者が知っている場合は、マルチスレッドの場合はConcurrentHashMapを使えばいいと思います.後でConcurrentHashMapの分析も整理します.
まとめ
重点説明部分ではresizeとputの操作過程を詳しく説明しましたが、一部の新人はまだ整理できないかもしれません.私はここで日常の使用と結びつけて、全体の過程をまとめて、皆さんの理解を便利にします.
1.HashMap作成プロセス(通常の状態):
2.HashMap resizeプロセス(正常状態):
3.HashMapputプロセス(正常状態):
HashMapはまずその内部の実現構造を理解する必要がある:
+ + 、構造の基礎の上でソースコードに対して深く入り込んで、resizeとput操作は最も重要な2つの部分で、この2つのブロックを理解して、基本的にHashMapの全体の処理過程に対して一定の認知があって、また、必ず自分でdebugを手に入れて、データの変換を整理して、HashMapを知るのに役立ちます.本文はまず基礎部分から話して、いくつかの名詞を説明して、ハッシュ表に言及して、構造を実現することから各位のもっと良い理解のソースコードの操作部分を助けて、重点のいくつかの部分に対して詳しい説明をして、resizeとputの操作の難点部分も相応の解釈をして、各位に対して役に立つことを望んで、後で暇があれば私は赤い黒い木の部分の理解を分かち合います.ありがとうございます.