背景
今天數據采集項目碰到一個性能問題，3000多個采集點，每一個采集點每秒送一個數據，接收到數據之后首先需要內存中做緩存，之后有一系列的業務分析處理，所以，對系統性能要求比較高。
最近幾天發現服務器cpu大多時間都在100%以上，所以就重點分析了緩存方案，確實是緩存方案有問題，修改之后初步驗證，cpu降低到50%左右，更換了第二個緩存方案之后，cpu降低到了大概30%左右。
所以，不同的緩存方案，對于高并發場景下應用性能的影響還是蠻大的。
java中的緩存，大部分都是通過HashMap實現的，突然想到之前就記錄過HashMap學習筆記，找了半天才找到，差點丟了，重新找回來做個記錄。
搞一個Map學習系列，從HashMap開始。
認識HashMap
HashMap是java中應用最廣的集合類之一，以key/value(鍵值對）的方式保存數據。
你可以把HashMap叫做集合類，也可以把它叫做容器，java中許多容器框架比如Spring，其實好多都是用HashMap來存儲數據的。
當然，java秉承“一切都是對象”，HashMap中存儲的當然也是對象，只不過是以“鍵值”對組成的對象。
HashMap繼承自AbstractMap，并實現了Map接口。所以，想要徹底搞懂HashMap，還是需要先從Map接口、以及AbstractMap入手。
Map接口
其實Map接口沒啥東西，接口而已。定義了size()、isEmpty()、get()、put()、containsKey()、containsValue()…等通用的Map類方法。
相對重要一點的是，Map接口定義了一個Entry<K,V>內部接口，這個Entry其實就是Map包含的對象，不同的Map的實現類會有不同的實現。
Map接口也實現了幾個方法，具體暫時就不詳細分析了，這其實是一個很好的針對“接口是否可以實現方法？”這個問題的很好的答案。
AbstractMap抽象類
AbstractMap抽象類實現了Map接口，具體化了部分Map接口定義的方法。
實現了一個叫SimpleEntry的Entry（就是Map接口中定義的內部接口），還有一個叫SimpleImmutableEntry的Entry。
暫且不表，不影響主題：識別HashMap真面目。
HashMap的數據結構
回過頭來再繼續研究HashMap，首先識別HashMap的數據結構，我們先從簡單的入手，一步一步抽絲剝繭、先易后難，逐步研究。
首先來認識一下Node。
Node是Entry的實現，數據結構非常簡單：
final int hash;final K key;V value;Node<K,V> next;
哈希值、key、vaue以及指向下一節點的簡單的鏈表結構。
HashMap桶內Node鏈表容量增大之后會自動修改簡單鏈表結構為紅黑樹，本篇暫不研究紅黑樹。
table數組
table數組是HashMap真正存儲數據的地方，所以說白了HashMap底層實際上還是數組。
不過HashMap的table是比較特殊的數組，數組內的每一個對象其實就是我們常說的桶，桶內裝的是Node<K,V>對象，也就是我們放置到HashMap中的鍵值對。
HashMap的初始化
HashMap提供了幾個不同的初始化方法，區別無非就是有沒有初始化容量大小、有沒有初始化對象、有沒有初始化的loadFactor和threshold。
這幾個概念需要我們一個個慢慢去了解。
-
容量
就是HashMap中table數組的大小，HashMap的容量是2的n次方，初始化不設置容量的話，默認16，初始化如果設置了
initialCapacity 的話，則HashMap的容量是最接近initialCapacity并且大于initialCapacity的2的整數次冪，比如initialCapacity設置為3,4,5則HaspMap最終容量為8，設置為9,10,11…則HashMap的最終容量為16，以此類推。這個容量計算是通過tableSizeFor方法實現的，我們暫時按下好奇心（這個方法為什么能實現大于輸入參數cap的最近的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;}
- loadFactor
直譯為裝載因子，意譯為擴容因子，初始值設置為0.75。 - threshold
threshold是擴容閾值，HashMap的容量loadFactor=threshold。當HashMap存放對象的數量增長到threshold的時候進行擴容。
比如HashMap初始化容量為16，默認loadFactor為0.75，則threshold=160.75=12。則當HashMap存儲對象的數量（size）大于12的時候，HaspMap調用resize()方法自動擴容。
4.size
可以通過調用size()方法獲取到，HashMap內實際存放的對象數。我們如果要想搞清楚HashMap的真面目，最好能對size和容量Capacity有清楚的認識。size是對應用很有價值的數據，我們開發過程中所說的一個HashMap的大小其實指的就是size。而Capacity對應用來說沒有什么意義，只是HashMap內部使用的概念，只對那些對HashMap內部結構有興趣、想要研究清楚其工作機制的同學有意義。
###HashMap賦值
HashMap的賦值邏輯如下（假設待存放的數據為e<key1,value1>）：
- 檢查table數組為空的話，初始化指定容量或者默認容量的table數組
- 根據key1的哈希值計算得出（算法為（容量 - 1） & hash(key1）)對應的桶。這一步很重要，一般來講優秀的hash算法能夠盡可能確保不同的key值得到不同的hash值，也就可以確保放入不同的桶內。但是不可避免的，可能會存在不同key值得到相同hash值的情況（hash沖突：key1<>key2,hash(key1)=hash(key2)），這種情況下就會放置在相同的桶（比如table[5]）內。
- 得到桶之后，判斷桶內是否已經有數據。
- 沒有數據則直接new一個Node：newNode(hash, key1, value1, null)，放在桶中，結束。
- 否則，桶內有數據，有兩種情況：一是為鍵值key1重復賦值、二是hash沖突。
- 如果是hash沖突，則new一個Node：newNode(hash, key1, value1, null)并將其設置為桶內的最后一個Node。
- 如果是重復賦值（桶內數據的key值=key1），則為key1重新賦值value1，并返回key1的舊值
所以我們可以看到，針對key而言，HashMap不重復，意思是說，相同的key只在HashMap中只保留一份數據。
并且，一般情況下，HashMap的一個桶內只保留一個對象，只有在hash沖突發生了之后，桶內才有可能放置多于一個對象，以鏈表結構保存。
HashMap中的null對象
此處null對象指的是HashMap中的key值為null的Node對象。
大家都知道HashMap允許且僅能存儲key=null的一個對象，比如代碼：
HashMap hm<String,String> = new HashMap();hm.put(null,"it's null");hm.put(null,"i am null");hm.put(null,"null loves null");
最終hm容器中只有一個null對象，并且hm.get(null)得到的應該是 “null loaves null”。
這背后的原因可以從上述HashMap賦值邏輯中找到答案，你只要知道null的hash值是0就可輕易得出以上結論。
從HashMap獲取數據
通過get（key）方法獲取數據的邏輯如下（假設要獲取的數據key=key1）：
- table數組不為空并且數組長度大于0，則采用與put數據相同的算法得到key1值對應的桶。
- 桶內不空則從第一個節點開始檢查，如果節點key值等于key1，則返回該節點的value。如果第一個節點不滿足條件，則依次檢查桶內所有其他節點。
- 桶內空，或者桶內不空但是沒有找到滿足條件的對象（應該不可能）則返回null，表明當前HashMap中不存在key值為key1的對象
需要注意的一點是，檢查節點key值等于key1的邏輯是：
兩個對象相等，或者兩個對象不為null且key1.equals(key)。
好了，以上！相信已經能夠揭開HashMap神秘面紗之一角了。
 --- Linux 鏈表結構)
