国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

秒殺Java面試官——集合篇（二）

三、HashMap底層實(shí)現(xiàn)原理（基于JDK1.8）

        面試中，你是否也曾被問過以下問題呢：

    你知道HashMap的數(shù)據(jù)結(jié)構(gòu)嗎？HashMap是如何實(shí)現(xiàn)存儲的？底層采用了什么算法？為什么采用這種算法？如何對HashMap進(jìn)行優(yōu)化？如果HashMap的大小超過了負(fù)載因子定義的容量，怎么辦？等等。

    有覺得很難嗎？別怕!下面博主就帶著大家深度剖析，以源代碼為依據(jù)，逐一分析，看看HashMap到底是怎么玩的：

       ① HashMap源碼片段 —— 總體介紹：  

/* Hash table based implementation of the<tt>Map</tt> interface（HashMap實(shí)現(xiàn)了Map接口）. This implementation provides all of the optional map operations, and permits <tt>null</tt> values and the<tt>null</tt> key（允許儲存null值和null鍵）.  (The <tt>HashMap</tt> class is roughly equivalent to<tt>Hashtable</tt>, except that it is unsynchronized and permits nulls.(HashTable和HashMap很相似，除了HashTable的方法是同步的，并且不允許儲存null值和null鍵))  This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time(HashMap不保證映射的順序,特別是它不保證該順序不隨時間變化).*/

       ② HashMap源碼片段 —— 六大初始化參數(shù)：

[java] view plain copy

1. /** 
2.  * 初始容量1 << 4 = 16 
3.  */  
4. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
5. /** 
6.  * 最大容量1 << 30 = 1073741824 
7.  */  
8. static final int MAXIMUM_CAPACITY = 1 << 30;  
9. /** 
10.  * 默認(rèn)負(fù)載因子0.75f 
11.  */  
12. static final float DEFAULT_LOAD_FACTOR = 0.75f;  
13. /** 
14.  * 由鏈表轉(zhuǎn)換成樹的閾值：即當(dāng)bucket(桶)中bin（箱子）的數(shù)量超過 
15.  * TREEIFY_THRESHOLD時使用樹來代替鏈表。默認(rèn)值是8  
16.  */  
17. static final int TREEIFY_THRESHOLD = 8;  
18. /** 
19.  * 由樹轉(zhuǎn)換成鏈表的閾值：當(dāng)執(zhí)行resize操作時，當(dāng)bucket中bin的數(shù)量少于此值， 
20.  * 時使用鏈表來代替樹。默認(rèn)值是6  
21.  */  
22. static final int UNTREEIFY_THRESHOLD = 6;  
23. /** 
24.  * 樹的最小容量 
25.  */  
26. static final int MIN_TREEIFY_CAPACITY = 64;  

        ③ HashMap源碼片段 —— 內(nèi)部結(jié)構(gòu)：

[java] view plain copy

1. /** 
2.  * Basic hash bin node, used for most entries.  
3.  */  
4. // Node是單向鏈表，它實(shí)現(xiàn)了Map.Entry接口  
5. static class Node<K,V> implements Map.Entry<K,V> {  
6.     final int hash;   // 鍵對應(yīng)的Hash值  
7.     final K key;       // 鍵  
8.     V value;            // 值  
9.     Node<K,V> next;    // 下一個節(jié)點(diǎn)  
10.     // 構(gòu)造函數(shù)  
11.     Node(int hash, K key, V value, Node<K,V> next) {  
12.         this.hash = hash;    
13.         this.key = key;  
14.         this.value = value;  
15.         this.next = next;  
16.     }  
17. // 存儲（位桶）的數(shù)組</k,v>  
18. sient Node<K,V>[] table;  
19. // 紅黑樹  
20. static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {  
21.     TreeNode<K,V> parent; // 父節(jié)點(diǎn)  
22.     TreeNode<K,V> left;    // 左節(jié)點(diǎn)  
23.     TreeNode<K,V> right;   // 右節(jié)點(diǎn)  
24.     TreeNode<K,V> prev;    // needed to unlink next upon deletion  
25.     boolean red;             // 顏色屬性  
26.     TreeNode(int hash, K key, V val, Node<K,V> next) {  
27.         super(hash, key, val, next);  
28.     }  

      簡單看：在JDK1.8中，HashMap采用位桶+鏈表+紅黑樹實(shí)現(xiàn)。具體實(shí)現(xiàn)原理，我們繼續(xù)看源碼。關(guān)于紅黑樹，我將在后期《算法篇》詳細(xì)介紹。

      ④ HashMap源碼片段 —— 數(shù)組Node[]位置：

[java] view plain copy

1.     // 第一步：先計算key對應(yīng)的Hash值  
2.     static final int hash(Object key) {  
3.         int h;  
4.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
5. }  

[java] view plain copy

1.     // 第二步：保證哈希表散列均勻  
2.     static final int tableSizeFor(int cap) {  
3.         int n = cap - 1;  
4.         n |= n >>> 1;  
5.         n |= n >>> 2;  
6.         n |= n >>> 4;  
7.         n |= n >>> 8;  
8.         n |= n >>> 16;  
9.         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY :    
10.               n + 1;  
11. }  

★對第二步的作用，進(jìn)行簡要說明（很高級?。?/span>

{ 可以從源碼看出，在HashMap的構(gòu)造函數(shù)中，都直接或間接的調(diào)用了tableSizeFor函數(shù)。下面分析原因：length為2的整數(shù)冪保證了length-1最后一位（當(dāng)然是二進(jìn)制表示）為1，從而保證了取索引操作h&（length-1）的最后一位同時有為0和為1的可能性，保證了散列的均勻性。反過來講，當(dāng)length為奇數(shù)時，length-1最后一位為0，這樣與h按位與的最后一位肯定為0，即索引位置肯定是偶數(shù)，這樣數(shù)組的奇數(shù)位置全部沒有放置元素，浪費(fèi)了大量空間。簡而言之：length為2的冪保證了按位與最后一位的有效性，使哈希表散列更均勻。}

[java] view plain copy

1. // 第三步：計算索引：index = (tab.length - 1) & hash  
2.     if (tab == null || (n = tab.length) == 0) return;  
3. int index = (n - 1) & hash;  

  （區(qū)別于HashTable ：index = (hash &0x7FFFFFFF) % tab.length;

取模中的除法運(yùn)算效率很低，但是HashMap的位運(yùn)算效率很高）

       ⑤ HashMap源碼片段 —— 常用get（）/put（）操作：

[java] view plain copy

1. /** 
2.  * Implements Map.get and related methods 
3.  * 
4.  * @param hash hash for key 
5.  * @param key the key 
6.  * @return the node, or null if none 
7.  */  
8. final Node<K,V> getNode(int hash, Object key) {  
9.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;  
10.     if ((tab = table) != null && (n = tab.length) > 0 &&  
11.          //tab[(n - 1) & hash]得到對象的保存位  
12.         (first = tab[(n - 1) & hash]) != null) {  
13.         if (first.hash == hash && // always check first node  
14.             ((k = first.key) == key || (key != null && key.equals(k))))  
15.             return first;  
16.         if ((e = first.next) != null) {  
17.             //判斷：如果第一個節(jié)點(diǎn)是TreeNode,則采用紅黑樹處理沖突  
18.             if (first instanceof TreeNode)  
19.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);  
20.             do {  
21.                 //反之，采用鏈表處理沖突  
22.                 if (e.hash == hash &&  
23.                     ((k = e.key) == key || (key != null && key.equals(k))))  
24.                     return e;  
25.             } while ((e = e.next) != null);  
26.         }  
27.     }  
28.     return null;  
29. }  
30. /** 
31.  * Implements Map.put and related methods 
32.  * 
33.  * @param hash hash for key 
34.  * @param key the key 
35.  * @param value the value to put 
36.  * @param onlyIfAbsent if true, don't change existing value 
37.  * @param evict if false, the table is in creation mode. 
38.  * @return previous value, or null if none 
39.  */  
40. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
41.                boolean evict) {  
42.     Node<K,V>[] tab; Node<K,V> p; int n, i;  
43.     if ((tab = table) == null || (n = tab.length) == 0)  
44.         //如果tab為空或長度為0，則分配內(nèi)存resize()  
45.         n = (tab = resize()).length;  
46.     if ((p = tab[i = (n - 1) & hash]) == null)  
47.         //tab[i = (n - 1) & hash]找到put位置，如果為空,則直接put  
48.         tab[i] = newNode(hash, key, value, null);  
49.     else {  
50.         Node<K,V> e; K k;  
51.          //先判斷key的hash()方法判斷，再調(diào)用equals()方法判斷  
52.         if (p.hash == hash &&  ((k = p.key) == key || (key != null && key.equals(k))))  
53.             e = p;  
54.         else if (p instanceof TreeNode)  
55.            //屬于紅黑樹處理沖突  
56.            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  
57.         else {  
58.             //鏈表處理沖突  
59.             for (int binCount = 0; ; ++binCount) {  
60.                 //p第一次指向表頭,之后依次后移  
61.                 if ((e = p.next) == null) {  
62.                     //e為空，表示已到表尾也沒有找到key值相同節(jié)點(diǎn)，則新建節(jié)點(diǎn)  
63.                     p.next = newNode(hash, key, value, null);  
64.                     //新增節(jié)點(diǎn)后如果節(jié)點(diǎn)個數(shù)到達(dá)閾值，則將鏈表轉(zhuǎn)換為紅黑樹  
65.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
66.                         treeifyBin(tab, hash);  
67.                     break;  
68.                 }  
69.                 //允許存儲null鍵null值  
70.                 if (e.hash == hash &&  
71.                     ((k = e.key) == key || (key != null && key.equals(k))))  
72.                     break;  
73.                 //指針下移一位  
74.                 p = e;  
75.             }  
76.         }  
77.         //更新hash值和key值均相同的節(jié)點(diǎn)Value值  
78.         if (e != null) { // existing mapping for key  
79.             V oldValue = e.value;  
80.             if (!onlyIfAbsent || oldValue == null)  
81.                 e.value = value;  
82.             afterNodeAccess(e);  
83.             return oldValue;  
84.         }  
85.     }  
86.     ++modCount;  
87.     if (++size > threshold)  
88.         resize();  
89.     afterNodeInsertion(evict);  
90.     return null;  
91. }  

        ⑥ HashMap源碼片段 —— 擴(kuò)容resize（）：

[java] view plain copy

1. //可用來初始化HashMap大小 或重新調(diào)整HashMap大小 變?yōu)樵瓉?倍大小  
2. final Node<K,V>[] resize() {  
3.     Node<K,V>[] oldTab = table;  
4.     int oldCap = (oldTab == null) ? 0 : oldTab.length;  
5.     int oldThr = threshold;  
6.     int newCap, newThr = 0;  
7.     if (oldCap > 0) {  
8.         if (oldCap >= MAXIMUM_CAPACITY) {  
9.             threshold = Integer.MAX_VALUE;  
10.             return oldTab;  
11.         }  
12.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
13.                  oldCap >= DEFAULT_INITIAL_CAPACITY)  
14.             newThr = oldThr << 1; // 擴(kuò)容閾值加倍  
15.     }  
16.     else if (oldThr > 0)  // oldCap=0 ,oldThr>0此時newThr=0   
17.         newCap = oldThr;  
18.     else {   // oldCap=0,oldThr=0 相當(dāng)于使用默認(rèn)填充比和初始容量 初始化  
19.         newCap = DEFAULT_INITIAL_CAPACITY;  
20.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
21.     }  
22.     if (newThr == 0) {  
23.         float ft = (float)newCap * loadFactor;  
24.         newThr = (newCap < MAXIMUM_CAPACITY && ft <  (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);  
25.     }  
26.     threshold = newThr;  
27.     @SuppressWarnings({"rawtypes","unchecked"})  
28.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  
29.     // 數(shù)組輔助到新的數(shù)組中，分紅黑樹和鏈表討論  
30.     table = newTab;  
31.     if (oldTab != null) {  
32.         for (int j = 0; j < oldCap; ++j) {  
33.             Node<K,V> e;  
34.             if ((e = oldTab[j]) != null) {  
35.                 oldTab[j] = null;  
36.                 if (e.next == null)  
37.                     newTab[e.hash & (newCap - 1)] = e;  
38.                 else if (e instanceof TreeNode)  
39.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
40.                 else { // preserve order  
41.                     Node<K,V> loHead = null, loTail = null;  
42.                     Node<K,V> hiHead = null, hiTail = null;  
43.                     Node<K,V> next;  
44.                     do {  
45.                         next = e.next;  
46.                         if ((e.hash & oldCap) == 0) {  
47.                             if (loTail == null)  
48.                                 loHead = e;  
49.                             else  
50.                                 loTail.next = e;  
51.                             loTail = e;  
52.                         }  
53.                         else {  
54.                             if (hiTail == null)  
55.                                 hiHead = e;  
56.                             else  
57.                                 hiTail.next = e;  
58.                             hiTail = e;  
59.                         }  
60.                     } while ((e = next) != null);  
61.                     if (loTail != null) {  
62.                         loTail.next = null;  
63.                         newTab[j] = loHead;  
64.                     }  
65.                     if (hiTail != null) {  
66.                         hiTail.next = null;  
67.                         newTab[j + oldCap] = hiHead;  
68.                     }  
69.                 }  
70.             }  
71.         }  
72.     }  
73.     return newTab;  
74. }  

         看完以上源碼，是否感覺身體被掏空了？別慌，博主現(xiàn)在以一個簡單的小例子為主導(dǎo)，帶領(lǐng)大家重新梳理一下。

 簡析底層實(shí)現(xiàn)過程：

        ①創(chuàng)建HashMap，初始容量為16，實(shí)際容量 = 初始容量*負(fù)載因子（默認(rèn)0.75） = 12；

        ②調(diào)用put方法，會先計算key的hash值：hash = key.hashCode()。

        ③調(diào)用tableSizeFor()方法，保證哈希表散列均勻。

        ④計算Nodes[index]的索引：先進(jìn)行index = (tab.length - 1) & hash。

        ⑤如果索引位為null,直接創(chuàng)建新節(jié)點(diǎn),如果不為null,再判斷所因?yàn)樯鲜欠裼性?/p>

        ⑥如果有：則先調(diào)用hash()方法判斷，再調(diào)用equals()方法進(jìn)行判斷，如果都相同則直接用新的Value覆蓋舊的；

        ⑦如果不同，再判斷第一個節(jié)點(diǎn)類型是否為樹節(jié)點(diǎn)（涉及到：鏈表轉(zhuǎn)換成樹的閾值，默認(rèn)8），如果是，則按照紅黑樹的算法進(jìn)行存儲；如果不是，則按照鏈表存儲；

       ⑧當(dāng)存儲元素過多時，需要進(jìn)行擴(kuò)容：

   默認(rèn)的負(fù)載因子是0.75，如果實(shí)際元素所占容量占分配容量的75%時就要擴(kuò)容了。大約變?yōu)?strong>原來的2倍（newThr =oldThr << 1）;