1、常量
（1）預設table大小，1左移四位變為8
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
（2）table最大長度
static final int MAXIMUM_CAPACITY = 1 << 30;
（3）預設負載因子大小：
static final float DEFAULT_LOAD_FACTOR = 0.75f;
（4）樹化閾值
static final int TREEIFY_THRESHOLD = 8;
（5）樹降級成為鏈表閾值
static final int UNTREEIFY_THRESHOLD = 6;
（6）哈希表的元素達到64個之后就升級為樹
static final int MIN_TREEIFY_CAPACITY = 64;
（7）散串列（哈希表）
transient Node<K,V>[] table;
（8）當前哈希表元素個數：
transient int size;
（9）當前哈希表修改次數
transient int modCount;
（10）擴容閾值：當哈希表的元素超過閾值的時候，觸發擴容
int threshold;
（11）負載因子
final float loadFactor;
2、構造方法
（1）構造方法：
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
initialCapacity必須是大于零的，最大值是MAXIMUM_CAPACITY，loadFactor也必須是大于零的，這些代碼就是一些校驗
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; }
回傳一個大于或等于當前值cap的一個數字，并且這個數字一定是2的次方數，
cap=10
n=10-1=9（如果不減一的話會變成它的二倍）
1001 | 0100(右移一位) = 1101
1101 | 0011（右移兩位）=1111
1111 | 0000（右移四位）=1111
.... ...
... ...
return 15+1=16（加1后，進一位，后面的幾位都變成零）
3、put方法
（1）是一個套娃的方法：呼叫putVal方法：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
hash方法：hashCode經過擾動之后得到一個哈希值，哈希值與表的長度進行運算得到在哈希表中的位置，這個擾動函式就是hash函式，
擾動函式：讓key的哈希值的高十六位也參與路由運算
（2）hash方法
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
首先呼叫hashCode方法獲取鍵的哈希值，然后對其進行高位運算，將h右移16位與原來的h的低16位異或運算
如果key為空，哈希值就為零，不為空的話，就讓h和h右移16位相異或，目的是讓key的哈希值的高十六位也參與運算：
異或之后相當于將h的高十六位與低十六位相與，如果hashtable不是很大的情況下（16），可以讓高十六位參與進來
哈希沖突不可避免，只能盡量減少哈希沖突 ，如果鍵是自定義型別的話要重寫hash演算法，但是一般都用字串來做鍵
好的哈希演算法：
- 效率高，長文本也能高效地計算出hash值
- hash值不能逆推原文
- 兩次輸入只要有一點不同就要保證hash值是不同的
- 要盡可能保證分散，在table的slot大部分都處于空閑狀態的時候要盡可能降低哈希沖突
（3）putVal方法
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;
//延遲初始化邏輯，第一次呼叫putValue的時候會初始化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 value一致的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的元素，需要進行替換操作 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } }
//e不等于null，條件成立說明找到了一個與你插入的key完全一致的資料，需要進行替換 if (e != null) { // existing mapping for key V oldValue =https://www.cnblogs.com/zhai1997/p/ e.value; if (!onlyIfAbsent || oldValue =https://www.cnblogs.com/zhai1997/p/= null) e.value = value; afterNodeAccess(e); return oldValue; } }
//表示散串列結構被修改的次數，替換node元素的value不計數 ++modCount;
//插入新元素，如果自增后的值大于擴容閾值，則觸發擴容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
如果存在key和當前key相同的話，就不再插入了
寫資料分為四種情況（但是計算哈希的方式是一樣的）
- slot==null
直接使用slot即可：將put方法傳遞進來的key和value包裝成一個node物件放到slot中即可
- slot！=null并且他參考的node還沒有鏈化
對比一下當前的key與node物件的key是否相等，相等的話就會進行replace操作，否則的話就是哈希沖突在slot的node后面追加node就可以了，采用的是尾插法（1.8，1.7是頭插法）
- slot內的node已經鏈化
迭代查詢node，對比當前key是否與鏈表上的key一致，相等的話就會進行replace操作，否則的話就繼續迭代到尾結點也沒有匹配到完全一致的node就把資料包裝成node追加到鏈表尾部，再檢查當前鏈表的長度有沒有達到樹化的閾值，達到的話就呼叫樹化方法，
- 沖突很嚴重的情況下，已經鏈化為紅黑樹
找到他的父節點的流程：
一直向下探測，直到查詢到左子樹或右子樹為null的情況，說明沒有查找到node的key與當前的key一致的TreeNode，此時就是插入父節點所在，然后將當前結點插入到父節點的左子樹或右子樹
探測的程序中TreeNode與當前結點的key完全一致，要進行一次replace操作（直接替換TreeNode的value欄位）
4、resize方法
如果元素較多且陣列較小的話就會造成鏈表的鏈化嚴重，查找的效率較低
（1）原始碼
final Node<K,V>[] resize() {
//oldTab,參考擴容前的哈希表 Node<K,V>[] oldTab = table;
//oldCap表示擴容前table陣列的長度 int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr表示擴容之前的擴容閾值，觸發本次擴容的閾值 int oldThr = threshold;
//newCap：擴容之后Table陣列的大小
//newThr:擴容之后，下次再次觸發擴容的條件 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 }//說明哈希表中的散串列是null else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY;//16 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不為空 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) {
//當前Node結點 Node<K,V> e;
//說明當前桶位中有資料，但是資料具體是單個資料還是鏈表、紅黑樹并不知道 if ((e = oldTab[j]) != null) {
//方便jvm GC的時候回收記憶體 oldTab[j] = null;
//第一種情況，當前桶位只有一個元素，從未發生過碰撞，這種情況直接根據當前元素的hash值計算出當前元素應該存放在新陣列中的位置，然后扔進去就可以了 if (e.next == null) newTab[e.hash & (newCap - 1)] = e;
//第二種情況，當前節點已經樹化，存盤的是一個紅黑樹的根結點TreeNode物件 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; 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; }
資料量欄位已經達到擴容閾值，會判斷當前需要插入的欄位位置是否為null，不為null才會擴容
采用右移一位增加二倍的方式，并且位運算對CPU來說比較簡潔，效率高
老陣列的資料遷移：
slot存盤的是null，不用處理
存盤的是node，node無鏈化，當slot中存盤的node結點next是null的時候，沒有發生哈希沖突直接遷移就好了，根據新表的TableSize計算出它在新表的位置
存盤的是鏈化的node，node節點的next不為null，說明發生了哈希沖突，需要將當前slot中保存的鏈表拆成兩個鏈表（低位鏈和高位鏈）
存盤的是一個紅黑樹的根結點TreeNode物件
5、get方法
（1）get方法：
public V get(Object key) { Node<K,V> e;
//存進去的時候哈希一下，取出來的時候也要hash return (e = getNode(hash(key), key)) == null ? null : e.value; }
（2）getNode方法：
final Node<K,V> getNode(int hash, Object key) {
//tab:參考當前hashMap的散串列
//first：桶位中的頭元素
//e：臨時node元素
//n：table陣列長度 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != 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; }
6、remove方法
（1）remove方法：
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }
（2）removeNode方法：
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
//tab：參考當前hashMap中的散串列
//p:當前node元素
//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)))) {
//第一種情況，node是樹節點，說明需要進行樹節點的移除操作 if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//第二種情況，桶位元素即為查找結果，即將該元素的下一個元素移動到桶位中 else if (node == p) tab[index] = node.next; else
//第三種情況：將當前元素p的下一個元素設定成要洗掉元素的下一個元素
p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }
7、repalce方法
public V replace(K key, V value) { Node<K,V> e; if ((e = getNode(hash(key), key)) != null) { V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/227056.html
標籤：Java