1. 簡介
HashMap是Java編程中常用的資料結構類，屬于JDK自帶的非常好用的類，使用它可以解決Java編程中的很多問題，今天來聊一下其原始碼，了解一下好的哈希映射是如何實作的，
哈希映射需要解決的主要有2個問題，哈希函式和解決沖突，哈希函式就是將一個映射的鍵值（key）通過某種計算，使其對應到陣列的一個位置，解決沖突則是在多個key都被對應到同一個陣列位置的時候，如何存盤這些映射，
2. HashMap實作概述
JDK自帶的HashMap主要使用陣列，每個陣列元素中，使用鏈表存盤沖突的映射，并且陣列大小可以根據加入的映射數量動態擴展大小，并且陣列大小都是2的冪函式，當然，采用鏈表存放沖突的映射，當鏈表太長了之后，就會在查找key的程序消耗過多時間，JDK1.8開始引入紅黑樹來解決鏈表過長的問題，當鏈表長度達到設定閾值時，將線性的鏈表轉換為紅黑樹，提升其查找性能，在JDK1.8中，這個閾值被設定為8，并且，當洗掉映射時，一顆紅黑樹元素少于6，就會將樹結構重建為線性鏈表，不過需要注意的是，要轉換為紅黑樹，不僅僅需要鏈表長度達到8，還需要陣列的長度大于64，否則，HashMap會認為，總共最多64*8=512個元素不足以達到需要建立樹結構的需要，這時候只做一下擴容操作即可，至于陣列大小，如果創建HashMap的時候沒有指定，默認大小是16，并且每次擴容都在原來基礎上乘以2，所以，如果以初始狀態算起，擴容2次之后，達到64長度的陣列，如果這時候再出現鏈表長度達到8，就需要進行轉紅黑樹的操作了，
2.1 哈希函式
HashMap在計算hash值的時候，首先呼叫了key物件的hashCode()獲取其hash1值，再對hash1做二進制無符號向右移16位操作（hash1 >>> 16）得到h（將hash1高位的16位移到低位，高位補0），再將移位后的值和hash1做按位與操作（hash1 & h），得到此映射的hash值hash2，在計算對應陣列索引的時候，再用陣列table的長度length減去1，和hash2做按位與操作（(table.length - 1) & hash2）得到陣列索引p，table[p]就是對應存放該映射的陣列元素，
2.2 解決沖突
在沖突的映射還不多的時候，采用拉鏈法解決沖突，具體是一個單鏈表，新加入的映射采用尾插法插入鏈表尾部，
當沖突元素也就是鏈表長度達到8，并且陣列長度不小于64時，將當前這個沖突元素的鏈表轉換為紅黑樹，關于紅黑樹的具體實作細節過于復雜，在這篇文章就不展開了，以免影響對HashMap的整體理解，
2.3 擴容程序
對于HashMap的擴容程序，也很簡單，創建一個新的陣列newTable，其大小（newCap）為之前的2倍，之前的陣列大小稱為oldCap，（newCap = oldCap * 2），
如果陣列元素為普通鏈表，則將鏈表分為兩個鏈表，第一個鏈表是hash值與原陣列長度按位與操作結果為0（(hash & oldCap) == 0），第一個鏈表在新陣列中的索引和原陣列相同（j），第二個鏈表是不符合第一個鏈表條件的元素組成的（(hash & oldCap) != 0），第二個鏈表在新陣列中的索引是原陣列中索引加上原陣列大小（j + oldCap），
如果陣列元素為紅黑樹，則遍歷所有節點將（(hash & oldCap) == 0）的節點分到第一個鏈表，其余分到第二個鏈表，然后根據鏈表長度，如果鏈表長度小于等于6，將紅黑樹退化為普通鏈表；否則重建紅黑樹，
將所有原來陣列中的鏈表都分開并存入新的陣列，擴容程序就算完成了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/55352.html
標籤：其他
上一篇：Codeforces Round #636 (Div. 3) A~D
下一篇：快速沃爾什變換小記