一、散列表結構
散列表結構就是陣列+連結串列的結構
二、什麼是雜湊？Hash也稱雜湊、雜湊，對應的英文單詞Hash，基本原理就是把任意長度的輸入，透過Hash演算法變成固定長度的輸出
這個對映的規則就是對應的雜湊演算法，而原始資料對映後的二進位制就是雜湊值
不同的資料它對應的雜湊碼值是不一樣的
雜湊演算法的效率非常高
三、HashMap原理講解3.1、繼承體系圖
3.2、Node資料結構分析
static class Node<K,V> implements Map.Entry<K,V> { final int hash;計算得到雜湊值 final K key; V value; Node<K,V> next;}interface Entry<K, V> { K getKey(); V getValue(); V setValue(V value);12345678910113.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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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;}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677784.4、resize()方法分析
//為了解決雜湊衝突，影響雜湊效率，所以會有擴容機制----------------------------------------------------------final Node<K,V>[] resize() { //oldTab：引用擴容前的雜湊表 //oldCap：表示擴容前table的陣列長度 //oldThr：表示擴容之前閾值 //newCap，newThr：擴容後的陣列長度大小，以及擴容後下次的閾值 Node<K,V>[] 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //說明，hashmap本次擴容之前，table不為null if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap); //第三種情況：桶位已經形成連結串列 else { // preserve order //地位連結串列--存放在擴容之後的陣列的下標位置，與當前陣列的下標位置一致 Node<K,V> loHead = null, loTail=null; //高位連結串列--存放在擴容之後的陣列的下標位置為當前陣列下標位置+擴容之前陣列的長度 Node<K,V> hiHead = null, hiTail=null;---------------------------------------------------------- Node<K,V> 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;}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111124.5、get方法
public V get(Object key) { Node<K,V> e; return (e = getNode(key)) == null ? null : e.value;}----------------------------------------------------------final Node<K,V> getNode(Object key) { Node<K,V>[] tab; //tab：引用當前hashmap的散列表 Node<K,V> 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<K,V>)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;}123456789101112131415161718192021222324252627282930314.6、remove方法分析
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;}----------------------------------------------------------final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) { //tab：引用當前HashMap的散列表 //p：表示當前散列表的元素 //n：表示散列表陣列的長度 //index：表示路由定址的結果 Node<K,V>[] tab; Node<K,V> p; int n, index;---------------------------------------------------------- if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) { //說明路由的桶位是有資料的，需要進行查詢操作，且刪除 ---------------------------------------------------------- //node:查詢到的結果， e：當前node的下一個元素 Node<K,V> 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<K,V>)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<K,V>)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; } 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455564.7、replace方法分析
@Overridepublic boolean replace(K key, V oldValue, V newValue) { Node<K,V> 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<K,V> 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<K,V> 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
最新評論