高度なアーキテクチャの進化のHashMapソースコードはこのように学ぶべきです
引用:面接でよくある質問
質問:「HashMapを使ったことがありますが、私に話してもらえますか?」
「もちろん使ったことがありますが、HashMapはキーのデータput方式を素早く記憶し、getですぐに取り出すことができるストレージ構造です」と言い、「HashMapはスレッドセキュリティではありません.答え:HashTableはスレッドセキュリティで、synchronizedで実現されています.HashMapの値は非常に速いです」などと言います.この時、彼はすでにHashMapの道具を使いこなしていることを示しています.
質問:「HashMapがputやgetでどのように働いているか知っていますか?」
答え:「HashMapはkeyでHash値を算出し、このHash値をオブジェクトの参照にマッピングし、getするときにkeyのhash値を算出してからオブジェクトを見つけます」.この時はもう自信がないように見えます.
質問:「HashMapのkeyはなぜ文字列が多いのか、他のオブジェクトやカスタムオブジェクトが使えるのか.なぜ?」
これは研究したことがなくて、普通はStringを使うことに慣れます.
質問:「HashMapはスレッドセキュリティではないと言いましたが、スレッドセキュリティをどのように理解していますか.原理は何ですか.スレッドセキュリティの問題を回避する方法はいくつかあります.」
答え:「スレッドセキュリティとは、複数のスレッドがアクセスする場合、対象に対して予想外の結果をもたらすことであり、一般的にはロックをかけてこそスレッドが安全になる」HashMapの面接問題は、面接者のスレッド問題、Javaメモリモデル問題、スレッド可視と可変の問題、Hash計算問題、チェーンテーブル構造問題、バイナリの&、|、<>などの問題を考察することができる.だからHashMapは一人の技術の基礎を試すことができます.
一、データ構造
HashMapは配列+チェーンテーブル+レッドブラックツリー(JDK 1.8がレッドブラックツリー部分を増やした)で実現されており、以下に示すように
二、メンバー属性
1、loadFactorパラメータ
メモリに余裕がある場合はloadFactorの設定を小さくすることをお勧めしますが、初期sizeの設定に注意し、適切でない場合は頻繁なresizeが挿入の効率に深刻な影響を及ぼすことに注意してください.メモリがきつい場合はloadFactor設定を大きくすることができますが、loadFactor設定が大きいとキー値がチェーンテーブルとして格納される確率が高くなり、平均的なクエリー時間が遅くなりますが、挿入には直接的な影響はありませんが、loadFactorが高くなり、
三、構造方法
四、put方法
HashMapにput要素を入力すると、keyのhashCodeに基づいてhash値を再計算し、hash値に基づいてこの要素の配列内の位置(すなわち下付き)に値し、配列の位置に他の要素が格納されている場合、この位置の要素はチェーンテーブルの形で格納され、新しく追加された要素はチェーンヘッドに配置され、最初に追加された要素はチェーンテールに配置され、配列には、最後に挿入された要素が格納されます.配列の位置に要素がない場合は、その要素を配列の位置に直接配置します.
①.キー値が配列table[i]に対して空またはnullであるか否かを判断し、そうでなければresize()を実行して拡張する.②.キー値keyからhash値を挿入する配列インデックスiに計算し、table[i]=nullの場合、直接ノードを新規作成して追加し、⑥に転向し、table[i]が空でない場合、③に転向する.③. table[i]の最初の要素がkeyと同じかどうかを判断し、同じ値でvalueを直接上書きしないと④に転向し、ここで同じはhashCodeおよびequalsを指す.④. table[i]がtreeNodeであるか否か、すなわちtable[i]が赤黒ツリーであるか否かを判断し、赤黒ツリーであれば直接ツリーにキー値ペアを挿入し、そうでなければ⑤;⑤. table[i]を遍歴し、チェーンテーブルの長さが8より大きいかどうかを判断し、8より大きい場合はチェーンテーブルを赤黒ツリーに変換し、赤黒ツリーで挿入操作を実行し、そうでない場合はチェーンテーブルの挿入操作を行う.遍歴中にkeyが直接valueを上書きしていることを発見すればよい.⑥挿入に成功した後、実際に存在するキー値対数sizeが最大容量thresholdを超えているか否かを判断し、超えていれば拡張する.
五、resize方法
六、treeifyBin方法
詳細については、微信公衆番号:it_haha
質問:「HashMapを使ったことがありますが、私に話してもらえますか?」
「もちろん使ったことがありますが、HashMapはキーのデータput方式を素早く記憶し、getですぐに取り出すことができるストレージ構造です」と言い、「HashMapはスレッドセキュリティではありません.答え:HashTableはスレッドセキュリティで、synchronizedで実現されています.HashMapの値は非常に速いです」などと言います.この時、彼はすでにHashMapの道具を使いこなしていることを示しています.
質問:「HashMapがputやgetでどのように働いているか知っていますか?」
答え:「HashMapはkeyでHash値を算出し、このHash値をオブジェクトの参照にマッピングし、getするときにkeyのhash値を算出してからオブジェクトを見つけます」.この時はもう自信がないように見えます.
質問:「HashMapのkeyはなぜ文字列が多いのか、他のオブジェクトやカスタムオブジェクトが使えるのか.なぜ?」
これは研究したことがなくて、普通はStringを使うことに慣れます.
質問:「HashMapはスレッドセキュリティではないと言いましたが、スレッドセキュリティをどのように理解していますか.原理は何ですか.スレッドセキュリティの問題を回避する方法はいくつかあります.」
答え:「スレッドセキュリティとは、複数のスレッドがアクセスする場合、対象に対して予想外の結果をもたらすことであり、一般的にはロックをかけてこそスレッドが安全になる」HashMapの面接問題は、面接者のスレッド問題、Javaメモリモデル問題、スレッド可視と可変の問題、Hash計算問題、チェーンテーブル構造問題、バイナリの&、|、<>などの問題を考察することができる.だからHashMapは一人の技術の基礎を試すことができます.
一、データ構造
HashMapは配列+チェーンテーブル+レッドブラックツリー(JDK 1.8がレッドブラックツリー部分を増やした)で実現されており、以下に示すように
// Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // hash
final K key; // key
V value; // value
Node next; // next ， TreeNode
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() { }
public final V getValue() { }
public final String toString() { }
public final int hashCode() { }
public final V setValue(V newValue) { }
public final boolean equals(Object o) { }
}
public class LinkedHashMap<K,V> {
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry before, after;
Entry(int hash, K key, V value, Node next) {
super(hash, key, value, next);
}
}
}
// TreeNode LinkedHashMap.Entry，
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode parent; //
TreeNode left; //
TreeNode right; //
TreeNode prev; //
boolean red; // （ 、 ）
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
final TreeNode root() { }
static void moveRootToFront(Node[] tab, TreeNode root) { }
final TreeNode find(int h, Object k, Class> kc) { }
final void treeify(Node[] tab) { }
final Node untreeify(HashMap map) { }
final TreeNode putTreeVal(HashMap map, Node[] tab,int h, K k, V v) { }
final void removeTreeNode(HashMap map, Node[] tab, boolean movable) { }
final void split(HashMap map, Node[] tab, int index, int bit) { }
/* ------------------------------------------------------------ */
// Red-black tree methods, all adapted from CLR
//
static TreeNode rotateLeft(TreeNode root,TreeNode p) {}
static TreeNode rotateRight(TreeNode root,TreeNode p) { }
static TreeNode balanceInsertion(TreeNode root, TreeNode x) {}
static TreeNode balanceDeletion(TreeNode root,TreeNode x) {}
static boolean checkInvariants(TreeNode t) {}
}
二、メンバー属性
// HashMap
static final int DEFAULT_INITIAL_CAPACITY = 1 <4;
//HashMap
static final int MAXIMUM_CAPACITY = 1 <30;
//HashMap , HashMap * ， resize()
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// hash
static final int TREEIFY_THRESHOLD = 8;
// hash
static final int UNTREEIFY_THRESHOLD = 6;
/* hash ， ， （ MIN_TREEIFY_CAPACITY ） hash ， ， resize() hashMap */
static final int MIN_TREEIFY_CAPACITY = 64;
// Node
transient Node[] table;
// hashMap Node set
transient Set> entrySet;
// hashMap
transient int size;
// hashMap （ value ）
transient int modCount;
//threshold table.length * loadFactor, size resize()
int threshold;
// hashMap
final float loadFactor;
1、loadFactorパラメータ
メモリに余裕がある場合はloadFactorの設定を小さくすることをお勧めしますが、初期sizeの設定に注意し、適切でない場合は頻繁なresizeが挿入の効率に深刻な影響を及ぼすことに注意してください.メモリがきつい場合はloadFactor設定を大きくすることができますが、loadFactor設定が大きいとキー値がチェーンテーブルとして格納される確率が高くなり、平均的なクエリー時間が遅くなりますが、挿入には直接的な影響はありませんが、loadFactorが高くなり、
三、構造方法
// １，
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;
/* tableSizeFor(initialCapacity) initialCapacity 2 ， ９， hashMap 16*/
// hashMap threshold
this.threshold = tableSizeFor(initialCapacity);
}
//tableSizeFor(initialCapacity) initialCapacity 2
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);
}
// ３，
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
四、put方法
HashMapにput要素を入力すると、keyのhashCodeに基づいてhash値を再計算し、hash値に基づいてこの要素の配列内の位置(すなわち下付き)に値し、配列の位置に他の要素が格納されている場合、この位置の要素はチェーンテーブルの形で格納され、新しく追加された要素はチェーンヘッドに配置され、最初に追加された要素はチェーンテールに配置され、配列には、最後に挿入された要素が格納されます.配列の位置に要素がない場合は、その要素を配列の位置に直接配置します.
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, // onlyIfAbsent key value null ， value ， put 。
boolean evict) { //evict LinkedHashMap ， 。
Node[] tab; Node p; int n, i; // tab Node ，p tab Node ，n tab ，i tab 。
if ((tab = table) == null || (n = tab.length) == 0) // table null tab 0 ， table ， resize() table。
n = (tab = resize()).length; // ，HashMap ：The table, initialized on first use, and resized as necessary。
if ((p = tab[i = (n - 1) & hash]) == null) // （n - 1） & hash tab i， p tab[i]， 。 p null。
tab[i] = newNode(hash, key, value, null); // p null ， tab[i] ， new Node ， newNode tab[i]。
else { // p null ， ：p ；p ；p TREEIFY_THRESHOLD， 。
Node e; K k; // e Node ， k = p.key。
if (p.hash == hash && //HashMap key key hash ， equals 。 p.key key ， ， p e。
((k = p.key) == key || (key != null && key.equals(k)))) // ， HashMap key， ， value 。
e = p; // p e， ？ ， ， key ， 。
else if (p instanceof TreeNode) // ，p ， ， p TreeNode.putTreeVal ， e。
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // ， tree key ？ ，putTreeVal ， hash TreeNode， null。
else { // p ， ： / 。 ， TreeNode Node 。
for (int binCount = 0; ; ++binCount) { // ， ，binCount 。
if ((e = p.next) == null) { // p.next null ， ， p ， p.next， 。 e p。
p.next = newNode(hash, key, value, null); // next， null， 。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // ， ， 1， binCount ， 1。
treeifyBin(tab, hash); // ， treeifyBin ， 。
break; // ， ， ，break 。
}
if (e.hash == hash && // ， ， key ， e， e value 。
((k = e.key) == key || (key != null && key.equals(k)))) // key 。
break; // key ， ， break value 。
p = e; // 21 ，e p ，p = e 。 p node 。
}
}
if (e != null) { // existing mapping for key // jdk ， ， key 。
V oldValue = e.value; // oldValue， e value 。
if (!onlyIfAbsent || oldValue == null) // ，onlyIfAbsent key ， ， onlyIfAbsent false oldValue null ， 。
e.value = value; // ， e value value。
afterNodeAccess(e); // hashmap ， ， linkedHashMap 。
return oldValue; // ， oldValue。 put ， ， ， oldValue。
}
}
++modCount; // ， ， key oldValue ， return， ， ， modCount 。
if (++size > threshold) // ， oldValue ， ， ++size threshold 。
resize(); // HashMap node threshold ，hashmap 。
afterNodeInsertion(evict); // afterNodeAccess ， linkedHashMap ，HashMap 。1
return null; // ， ，put null。
}
①.キー値が配列table[i]に対して空またはnullであるか否かを判断し、そうでなければresize()を実行して拡張する.②.キー値keyからhash値を挿入する配列インデックスiに計算し、table[i]=nullの場合、直接ノードを新規作成して追加し、⑥に転向し、table[i]が空でない場合、③に転向する.③. table[i]の最初の要素がkeyと同じかどうかを判断し、同じ値でvalueを直接上書きしないと④に転向し、ここで同じはhashCodeおよびequalsを指す.④. table[i]がtreeNodeであるか否か、すなわちtable[i]が赤黒ツリーであるか否かを判断し、赤黒ツリーであれば直接ツリーにキー値ペアを挿入し、そうでなければ⑤;⑤. table[i]を遍歴し、チェーンテーブルの長さが8より大きいかどうかを判断し、8より大きい場合はチェーンテーブルを赤黒ツリーに変換し、赤黒ツリーで挿入操作を実行し、そうでない場合はチェーンテーブルの挿入操作を行う.遍歴中にkeyが直接valueを上書きしていることを発見すればよい.⑥挿入に成功した後、実際に存在するキー値対数sizeが最大容量thresholdを超えているか否かを判断し、超えていれば拡張する.
五、resize方法
// Initializes or doubles table size， table
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) {
threshold = Integer.MAX_VALUE;
return oldTab; // ，
}
else if((newCap = oldCap <1) oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr <1; // double threshold
}
// oldCap=0 ,oldThr>0，threshold( resize )
else if (oldThr > 0)
newCap = oldThr; // = （ ）
else { // oldCap=0 ,oldThr=0，
newCap = DEFAULT_INITIAL_CAPACITY;
newThr=(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr== 0) { // 0，
float ft = (float)newCap * loadFactor;
newThr = (newCap float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap]; //
table = newTab;
// table ,bucket copy bucket，
if (oldTab != null) { // copy， ！！！
for (int j = 0; j Node e;
if ((e = oldTab[j]) != null) { //
oldTab[j] = null; // null， GC
// ， ，
if (e.next == null)
//1.6 indexFor， key;tableSizeFor
newTab[e.hash &(newCap - 1)]= e; //hash&(length-1)
else if (e instanceof TreeNode) //
((TreeNode)e).split(this, newTab, j, oldCap);
else { // ，preserve order
// ， bucket bucket
Node loHead = null,loTail = null;//lo bucket
Node hiHead = null, hiTail = null;//hi bucket
Node next;
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) { // bucket ( node)
loTail.next = null; // null
newTab[j] = loHead;// (j)
}
if (hiTail != null) { // j+oldCap
hiTail.next = null;
newTab[j + oldCap] = hiHead;//j+oldCap
}
}
}
}
}
return newTab;
}
六、treeifyBin方法
//
final void treeifyBin(Node[] tab, int hash) {
/*int n, index; Node e;
// hash ， ，
if (tab == null || (n = tab.length) resize();
// node
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode hd = null, tl = null;
// ，
do {
//
TreeNode p = replacementTreeNode(e, null);
//
if (tl == null)
// hd
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
//
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}*/
}
詳細については、微信公衆番号:it_haha