hashmap原理_想要彻底搞懂HashMap？你得恶补下HashMap原理
引言
唉！
金九銀十轉眼已過，
面試現場不知所措；
不懂原理是我過錯，
今日彌補只為求過。
======================================================
小學弟呀，小學弟！
平時不努力，
全來學押韻；
近來找工作，
處處不如意；
閑來送你一篇原理文，
讓你對HashMap不再愁。
=======================================================
話不多說，就讓我們開始HashMap的原理講解吧。
正文
Hash表
HashMap其實就是用Hash表這種數據結構來實現的；如果你對Hash表了如指掌，我相信，對于HashMap你已經成功一半了。那我們就先來說說什么是Hash表吧。
先來舉個例子：
在上學時我們都排過隊，當老師沒有做要求的時候，大家都會隨便站，關系好的站在一起等等沒有統一規則，甚至還有插班的行為。當一個老師從這個長長的隊列時找人時，往往都是從第一個開始找，直到找到他想找的人為止。這種方式就可以看做鏈表或者數組，每次都需要逐個遍歷篩選。 這時候教導主任來了，說這樣排隊太亂了，于是制定了排隊規則，必須按照年級+班級+自己的序號順序站隊并記住這個序號。當老師再次找一個陌生的同學時，只要對教導主任說我要找二年級五班006同學，教導主任通過信息就可以直接找到張三同學站的位置，并不需要遍歷了。這種方式就是Hash表的方式進行添加或者查找的。我們來解釋一下上面的例子：
- 例子中所提到的二年級五班006就是Hash值：根據key值(例子中的某個學生)計算得出一個固定長度的目標值，而這個目標值就叫做Hash值；
- 教導主任所制定的排隊規則就是所制定的一個Hash函數：用key怎么計算Hash值的呢？就是通過Hash函數的計算；在項目中每一個hash函數的實現都是不一樣的，而大部分hash函數的具體實現是非公開的，因為可能會造成安全問題。
簡單的來說，哈希表是一種表結構，我們可以直接根據給定的key值計算出目標位置。在工程中這一表結構實現通常采用數組。
那么一個好的Hash函數具備什么樣的特性呢？
- 1，同一性：也可以叫做散列性，即每一個Hash值都要盡可能的均勻；因為存儲在數組時要盡可能的均勻存儲。(也可以說每個數組下標的命中率盡可能相同。)
- 2，遵循雪崩效應：當有微小的key值輸入時，Hash值要發生巨大的變化；有些Hash函數是為了進行加密使用的(如https協議)遵循這條可以保證更高的安全性。
- 3，盡量避免Hash沖突：當我們要把十個蘋果放到九個抽屜里的時候，總會有至少兩個蘋果放到同一個抽屜里(抽屜原理)，存在兩個蘋果的抽屜，我們就可以叫它Hash沖突，或者Hash碰撞；同樣因為我們Hash值的長度是固定的，而key可以是任意值，所以總會造成兩個key值的hash值相同，這種情況叫做Hash沖突，Hash沖突是不可避免的，但我們要盡可能的減少沖突。
現在看看我們例子中教導主任制定的Hash函數是不是可以被我們吐槽一番呢。
所以，Hash表他的查詢速度快，一個良好的Hash表時間復雜度可以達到o(1)，對于龐大的海量數據，這種查找速度還是非常驚人的。
HashMap原理
JDK1.7
了解了Hash表，我們再來看HashMap，我們先來分析JDK1.7中的HashMap的實現：
JDK1.7中的HashMap采用的是數組加鏈表的形式進行存儲的，數組每個下標所對應的位置我們都可以叫做一個hash桶。
put過程：
public V put(K key, V value) { if (key == null) //1 return putForNullKey(value); int hash = hash(key); //2 int i = indexFor(hash, table.length); //3 for (Entry e = table[i]; e != null; e = e.next) {//4 Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); //5 return null; }1，key不能為空：
在存儲元素前，HashMap將判斷元素的key是夠為空，如果為空，直接返回。
2，計算Hash值：
final int hash(Object k) { int h = 0; if (useAltHashing) { if (k instanceof String) { //2.1 return sun.misc.Hashing.stringHash32((String) k); } h = hashSeed; } h ^= k.hashCode(); // 2.2 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }通過hash源碼我們看到：
2.1，這里JDK1.7對String類型的元素進行了重新hash的過程，為什么String要重新hash呢？
要從一篇郵件開始說起...在JDK1.7出現后，Tomcat發布了一篇郵件，里邊寫到了JDK1.7中HashMap的一個潛在安全漏洞。
mail-archives.apache.org/mod_mbox/to…4EFB9800.5010106@apache.org
這篇郵件中，因為Tomcat使用了Hashtable存儲了HTTP請求參數，由于String的hash算法是公開的，可能會導致一些專業人員可以獲取到無數個hashcode都相同的key值，當這些請求參數同時請求后，就會使hash表退化成鏈表，使cpu存在大量的鏈表，由于鏈表查找的時間復雜度O(n)，查找速度會受到很大的影響，所以會遭受DDos攻擊。
當然Tomcat也給出了解決方案，而隨后在JDK1.7的版本后也修復了這個bug。
2.2，我們看在2.2處進行了一堆的>>>和^操作，原因就是為了要增加它的同一性，讓命中每個數組下標的概率相同。
3，獲得數組下標：
static int indexFor(int h, int length) { return h & (length-1); }在步驟2中，我們得到了Hash值，那么怎么通過hash值來決定存在哪個桶里呢？
可能有些人我們會想到取余操作，但是取余操作有兩個缺點：1，相比于java的&運算速度相對慢一點；2，負數取余還是負數，數組下標(桶的位置)不能為負數。
所以Java采用的是按位與，這樣就可以根據數組長度和Hash值計算出該元素桶的具體位置。
采用這種方式計算數組下標也是有損失的，如果length不為2的次冪，那么每次按位與時，為零的那一位永遠為零，導致有些下標永遠無法得到，如下圖。
HashMap為了解決這個問題，如果你的值不為2的冪，那么在構造函數中HashMap將找到大于等于我們賦給HashMap的初始容量的最小2的冪。所以為了減少這次轉換，我們初始化HashMap的容量時一定要為2的冪。
4，我們接著向下看注釋4的地方：這里就是做了一個循環鏈表，去插入元素這么一個操作。
5，我們能看到這里調用了一個addEntry()函數，這個函數是干什么的呢，我們點擊去：
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }我們大致能了解到，這個其實就是擴容機制，知道這些就可以了，接著我們講講具體是怎么擴容的。
threshold：即闊值，當數組的使用大小大于等于這個值時，則將數組擴容。threshold = capacity(數組容量)* load_factor(負載因子)
load_factor(負載因子)：默認為0.75，官方解釋說：在時間和空間成本之間做了權衡后，得出的0.75這個值。
進入到if后，執行了resize()這個函數，這個函數可以說是一切根源的罪魁禍首。
我們點resize()進去看看
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { //MAXIMUM_CAPACITY默認是2的30次冪，所以基本不會到達這一容量 threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; boolean oldAltHashing = useAltHashing; useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = oldAltHashing ^ useAltHashing; transfer(newTable, rehash); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry e : table) { while(null != e) { Entry next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }這兩個方法主要是rehash操作，然后將數組中的鏈表使用頭插法重新插入到了新的數組中，其實這在單線程中是沒有問題的，但是如果多個線程同時操作的時候，將會出現循環鏈表的情況。當再次訪問這個循環鏈表時，就會出現死循環，cpu100%的情況，雖然HashMap中明確表示它并不是線程安全的，但還是有人會用到它，造成這樣的問題。
- 這里給大家分享一篇文章，里邊明確說明了為什么會產生循環鏈表：coolshell.cn/articles/96…
這就是JDK1.7中的HashMap的put過程，接下來我們簡單說一說get過程：
public V get(Object key) { if (key == null) return getForNullKey(); Entry entry = getEntry(key); return null == entry ? null : entry.getValue(); }這是JDK1.7的get方法，當key為空時返回null，否則調用getEntry()函數：
final Entry getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }就是計算key的hash值，然后循環該桶下的鏈表，查找數據。
JDK1.8
上面我們說到，JDK1.7的HashMap存在著安全隱患，如多線程下會可能出現循環鏈表(這完全是用戶自己的鍋，因為Java團隊明確表示HashMap不是線程安全的)。
- 所以JDK1.8的HashMap在結構上使用了數組加鏈表加紅黑樹的數據結構，防止當鏈表過長時導致搜索時間退化到o(n)。
當鏈表的元素達到了8的時候，將會使用紅黑樹代替鏈表，選擇8的原因是因為Java團隊解釋說：
大致上說，他們采用了泊松分布的原理(大學數學我們應該都學過)，當鏈表達到8時只有0.00000006的概率。
- 在hash()函數上也做了改進：
- 另外一個比較明顯的改進是在resize()這個函數中從之前的頭插法改為了尾插法，這樣在多線程的情況下就不會存在循環鏈表，進而導致死循環的情況了。但是值得注意的是，HashMap任然不是線程安全的，這在HashMap注釋中就已經明確說明了。
結束
這就是HashMap的比較重要的部分，也是面試過程中在問到HashMap時比較常見的問題。如果還有什么沒有提到的，大家可以在評論中告訴我，我會盡量補充的。
作者：張子江
鏈接：https://juejin.im/post/6880712401143595021
來源：掘金
總結
以上是生活随笔為你收集整理的hashmap原理_想要彻底搞懂HashMap？你得恶补下HashMap原理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python做的项目管理软件_幽雅的使用
- 下一篇： java实例_图例 | Java混合模式