一、散列表結構
散列表結構就是陣列+連結串列的結構
二、什麼是雜湊？
Hash也稱雜湊、雜湊，對應的英文單詞Hash，基本原理就是把任意長度的輸入，透過Hash演算法變成固定長度的輸出
這個對映的規則就是對應的雜湊演算法，而原始資料對映後的二進位制就是雜湊值
不同的資料它對應的雜湊碼值是不一樣的
雜湊演算法的效率非常高
讀者福利：關注小編+私信回覆【專案】獲取整理好的100+個Java專案影片+原始碼+筆記
三、HashMap原理講解
3.1、繼承體系圖
3.2、Node資料結構分析
static class Node implements Map。Entry { final int hash；計算得到雜湊值 final K key； V value； Node next；}interface Entry { K getKey（）； V getValue（）； V setValue（V value）；1234567891011
3.3、底層儲存結構
當連結串列長度到達8時，升級成紅黑樹結構
3.4、put資料原理分析
首先put進去一個key——value
根據key值會計算出一個hash值
經過擾動使資料更雜湊
構造出一個node物件
最後
在
透過路由演算法得出一個對應的index
3.5、什麼是雜湊碰撞？
當傳入的資料key對應計算出的hash值的後四位和上一個一樣時，這時候計算出的index就會一致，就會發生碰撞，導致資料變成連結串列
例如：
（16-1）————->0000 0000 0000 1111
“張三”————->0100 1101 0001 1011
“李四”————>1011 1010 0010 1011
此時，就會發現，張三和李四計算出的hash值轉化為二進位制的後四位一致，導致計算出index一致
3.6、JDK8為什麼引入紅黑樹？
雜湊碰撞，會帶來
鏈化
，效率會變低
引入紅黑樹會提高查詢效率
3.7、擴容機制
每次擴容為初始容量的2倍
eg：16————->32
為了防止資料過多，導致線性查詢，效率變低，擴容使得桶數變多，每條鏈上資料變少，查詢更快
四、手撕原始碼
4.1、HashMap核心屬性分析
樹化閾值——-8和64
負載因子0。75
threshold擴容閾值，當雜湊表中的元素超過閾值時，觸發擴容
loadFactory負載因子0。75，去計算閾值 eg：16*0。75
size————-當前雜湊表中元素個數
modCount————當前雜湊表結構修改次數
4.2、構造方法分析
public HashMap（int initialCapacity， float loadFactor） { //校驗 小於0報錯 if （initialCapacity < 0） throw new IllegalArgumentException（“Illegal initial capacity： ” + initialCapacity）； //capacity大於最大值取最大值 if （initialCapacity > MAXIMUM_CAPACITY） initialCapacity = MAXIMUM_CAPACITY； //負載因子不能小於等於0 if （loadFactor <= 0 || Float。isNaN（loadFactor）） throw new IllegalArgumentException（“Illegal load factor： ” + loadFactor）； this。loadFactor = loadFactor； //tableSizeFor方法 this。threshold = tableSizeFor（initialCapacity）；}————————————————————————————-//傳入一個初始容量，預設負載因子0。75public HashMap（int initialCapacity） { this（initialCapacity， DEFAULT_LOAD_FACTOR）；}————————————————————————————-//無引數，負載因子預設0。75public HashMap（） { this。loadFactor = DEFAULT_LOAD_FACTOR； // all other fields defaulted}————————————————————————————-//傳入一個map的物件public HashMap（Map<？ extends K， ？ extends V> m） { this。loadFactor = DEFAULT_LOAD_FACTOR； putMapEntries（m， false）；}
4.3、put方法分析
public V put（K key， V value） { //返回putVal方法，給key進行了一次rehash return putVal（hash（key）， key， value， false， true）；}——————————————————————————————static final int hash（Object key） { //讓key對應的hash值的高16位也參與運算 int h； return （key == null） ？ 0 ： （h = key。hashCode（）） ^ （h >>> 16）； }——————————————————————————————final V putVal（int hash， K key， V value， boolean onlyIfAbsent，boolean evict） { //tab：引用當前HashMap的散列表 //p：表示當前散列表的元素 //n：表示散列表陣列的長度 //i：表示路由定址的結果 Node［］ tab； Node p； int n， i；—————————————————————————————— //延遲初始化邏輯，當第一次呼叫putVal的時候，才去初始化HashMap物件的散列表大小 if （（tab = table） == null || （n = tab。length） == 0） n = （tab = resize（））。length；—————————————————————————————— //尋找找到桶位，且剛好為null，則把k-v封裝成node物件放進去 if （（p = tab［i = （n - 1） & hash］） == null） tab［i］ = newNode（hash， key， value， null）；—————————————————————————————— else { //e：不為null時，找到一個與當前要插入的key-val一致的key物件 //k：臨時的一個key Node e； K k； //表示桶位中的該元素，與你當前插入的元素key一致，後續會有替換操作 if （p。hash == hash && （（k = p。key） == key || （key ！= null && key。equals（k）））） e = p；—————————————————————————————— //樹化 else if （p instanceof TreeNode） e = （（TreeNode）p）。putTreeVal（this， tab， hash， key， value）；—————————————————————————————— else { //連結串列的情況，而且連結串列的頭元素與我們要插入的key不一致 for （int binCount = 0； ； ++binCount） { //條件成立，即說明迭代到最後一個連結串列了，也沒找到與你要插入的key一致的node物件 //說明要加入到連結串列的最後 if （（e = p。next） == null） { p。next = newNode（hash， key， value， null）； //說明當前連結串列長度達到樹化標準 if （binCount >= TREEIFY_THRESHOLD - 1） // -1 for 1st treeifyBin（tab， hash）； break； } //說明找到的元素key一樣，進行替換，break跳出迴圈即可 if （e。hash == hash && （（k = e。key） == key || （key ！= null && key。equals（k）））） break； p = e； } }—————————————————————————————— //e不等於null，說明找到了一個與你插入元素完全一致的，進行替換 if （e ！= null） { // existing mapping for key V oldValue = e。value； if （！onlyIfAbsent || oldValue == null） e。value = value； afterNodeAccess（e）； return oldValue； } }—————————————————————————————— //modCount：表示散列表結構被修改次數，替換元素不算次數 ++modCount； //插入新元素，size自增，如果自增大於擴容閾值，則觸發擴容 if （++size > threshold） resize（）； afterNodeInsertion（evict）； return null；}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
4.4、resize()方法分析
//為了解決雜湊衝突，影響雜湊效率，所以會有擴容機制——————————————————————————————final Node［］ resize（） { //oldTab：引用擴容前的雜湊表 //oldCap：表示擴容前table的陣列長度 //oldThr：表示擴容之前閾值 //newCap，newThr：擴容後的陣列長度大小，以及擴容後下次的閾值 Node［］ oldTab = table； int oldCap = （oldTab == null） ？ 0 ： oldTab。length； int oldThr = threshold； int newCap， newThr = 0；—————————————————————————————— //條件成立，說明hashmap散列表已經初始化過了，這是一次正常擴容 if （oldCap > 0） { //擴容之前的table陣列大小，已經達到了最大閾值後，則不擴容 //且設定擴容條件為int最大值 if （oldCap >= MAXIMUM_CAPACITY） { threshold = Integer。MAX_VALUE； return oldTab； }—————————————————————————————— //oldCAP左移一位，實現數值翻倍，且賦值給newcap，newcap小於數值最大值限制 且擴容之前閾值>=16 //這種情況下，則下一次擴容閾值等於當前閾值翻倍 else if （（newCap = oldCap << 1） < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY） newThr = oldThr << 1； // double threshold }—————————————————————————————— //oldCap == 0，說明hashmap散列表為null //1。new HashMap（inttCap，loadFactor）； //2。new HashMap（inttCap）； //3。new HashMap（map）； map有資料 else if （oldThr > 0） // initial capacity was placed in threshold newCap = oldThr；//一定是2的次方數—————————————————————————————— //oldCap==0，oldThr==0 //new HashMap（）； else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY； newThr = （int）（DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY）； }—————————————————————————————— if （newThr == 0） { float ft = （float）newCap * loadFactor； newThr = （newCap < MAXIMUM_CAPACITY && ft < （float）MAXIMUM_CAPACITY ？ （int）ft ： Integer。MAX_VALUE）； } threshold = newThr；—————————————————————————————————————————————————————————— //建立一個更長更大的陣列 @SuppressWarnings（{“rawtypes”，“unchecked”}） Node［］ newTab = （Node［］）new Node［newCap］； table = newTab； //說明，hashmap本次擴容之前，table不為null if （oldTab ！= null） { for （int j = 0； j < oldCap； ++j） { Node e；//當前node節點 //說明當前桶位中有資料，但是具體是連結串列還是紅黑樹，還是單個數據，不確定 if （（e = oldTab［j］） ！= null） { //方便jvm GC時回收 oldTab［j］ = null； //說明是個單個元素，直接計算當前元素應存放的新陣列的位置即可 if （e。next == null） newTab［e。hash & （newCap - 1）］ = e； //判斷有沒有樹化成紅黑樹 else if （e instanceof TreeNode） （（TreeNode）e）。split（this， newTab， j， oldCap）； //第三種情況：桶位已經形成連結串列 else { // preserve order //地位連結串列——存放在擴容之後的陣列的下標位置，與當前陣列的下標位置一致 Node loHead = null， loTail=null； //高位連結串列——存放在擴容之後的陣列的下標位置為當前陣列下標位置+擴容之前陣列的長度 Node hiHead = null， hiTail=null；—————————————————————————————— Node next； do { next = e。next； //hash——……1 1111 //hash——……0 1111 //0b 10000 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） { loTail。next = null； newTab［j］ = loHead； } // if （hiTail ！= null） { hiTail。next = null； newTab［j + oldCap］ = hiHead； } } } } } return newTab；}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
4.5、get方法
public V get（Object key） { Node e； return （e = getNode（key）） == null ？ null ： e。value；}——————————————————————————————final Node getNode（Object key） { Node［］ tab； //tab：引用當前hashmap的散列表 Node first， e；//first：桶位中的頭元素，e：臨時node元素 int n， hash； //n：table陣列長度 K k； ————————————————————————————- if （（tab = table） ！= null && （n = tab。length） > 0 && （first = tab［（n - 1） & （hash = hash（key））］） ！= null） { //定位出來的桶位元素，就是我們要get的元素 if （first。hash == hash && // always check first node （（k = first。key） == key || （key ！= null && key。equals（k）））） return first；—————————————————————————————— //說明當前桶位不止一個元素，可能是樹或者連結串列 if （（e = first。next） ！= null） { if （first instanceof TreeNode） return （（TreeNode）first）。getTreeNode（hash， key）；—————————————————————————————— //連結串列的情況 do { if （e。hash == hash && （（k = e。key） == key || （key ！= null && key。equals（k）））） return e； } while （（e = e。next） ！= null）； } } return null；}12345678910111213141516171819202122232425262728293031
4.6、remove方法分析
public V remove（Object key） { Node e； return （e = removeNode（hash（key）， key， null， false， true）） == null ？ null ： e。value；}——————————————————————————————final Node removeNode（int hash， Object key， Object value，boolean matchValue， boolean movable） { //tab：引用當前HashMap的散列表 //p：表示當前散列表的元素 //n：表示散列表陣列的長度 //index：表示路由定址的結果 Node［］ tab； Node p； int n， index；—————————————————————————————— if （（tab = table） ！= null && （n = tab。length） > 0 &&（p = tab［index = （n - 1） & hash］） ！= null） { //說明路由的桶位是有資料的，需要進行查詢操作，且刪除 —————————————————————————————— //node：查詢到的結果， e：當前node的下一個元素 Node node = null， e； K k； V v； //當前桶位中的元素即為要刪除的元素 if （p。hash == hash && （（k = p。key） == key || （key ！= null && key。equals（k）））） node = p；—————————————————————————————— //當前桶位的元素為紅黑樹 else if （（e = p。next） ！= null） { if （p instanceof TreeNode） node=（（TreeNode）p）。getTreeNode（hash， key）；—————————————————————————————— //當前桶位為連結串列 else { do { if （e。hash == hash && （（k = e。key） == key || （key ！= null && key。equals（k）））） { node = e； break； } p = e； } while （（e = e。next） ！= null）； } }—————————————————————————————— //判斷node不為空的情況，說明按照key找到了要刪除的資料 if （node ！= null && （！matchValue || （v = node。value） == value ||（value ！= null&&value。equals（v）））） { //結果是紅黑樹 if （node instanceof TreeNode） （（TreeNode）node）。removeTreeNode（this， tab， movable）； //結果為單個元素 else if （node == p） tab［index］ = node。next； //結果為連結串列 else p。next = node。next； ++modCount；//修改次數自增 ——size；//長度減少 afterNodeRemoval（node）； return node； } } return null； } 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
4.7、replace方法分析
@Overridepublic boolean replace（K key， V oldValue， V newValue） { Node e； V v； if （（e = getNode（key）） ！= null && （（v = e。value） == oldValue || （v ！= null && v。equals（oldValue）））） { e。value = newValue； afterNodeAccess（e）； return true； } return false；}——————————————————————————————@Overridepublic V replace（K key， V value） { Node e； if （（e = getNode（key）） ！= null） { V oldValue = e。value； e。value = value； afterNodeAccess（e）； return oldValue； } return null；}ll && v。equals（oldValue）））） { e。value = newValue； afterNodeAccess（e）； return true； } return false；}——————————————————————————————@Overridepublic V replace（K key， V value） { Node e； if （（e = getNode（key）） ！= null） { V oldValue = e。value； e。value = value； afterNodeAccess（e）； return oldValue； } return null；}
作者：zjd真可愛
https：//blog。csdn。net/zjdzka/article/details/112246992
