hashmap方法

tableSizeFor：擷取最小2整數幂

作用是查找大于等于傳參容量的最小2的整數幂，指派給threshold門檻值。由于擴容是目前數組下标值加上原數組長度，是以需要擴充到原先兩倍大小，又因為初始是16，是以一定擴容後的大小是2的整數幂。

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的整數幂的數之中最小的數。

首先-1是當cap本身就是2的整數幂的時候，滿足包含自身，也就是擴容後的結果還是cap。

|= ： n=n| （n >>> 1）

|：左右兩個元素位運算，都是0時該位才是0

n>>> 1： n的二進制向右移動1位，左邊高位空出來的補0

代碼目的就是把n的非0最高位的後面全變成1（0000100變成了0000111）

這樣在+1就獲得了最小的2的整數幂并且大于等于n

hash：判斷hash值（隻考慮key）

^是異或方法：左右值相同是0，不同是1
1.8 中用的是key的hashcode，注意這裡和高16位做了一個異或，可以防止hash數組太小時，hash值的高位被忽略，也就是太小左

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

桶定位：用的方法是hash & (table.length -1)，也就是hash方法得到的hash值和table數組的長度-1，取并。（相當于h%length）

hashcode， ==， equals， compareTo()差別

可以參考部落格：1，2

== 比較的是變量的句柄存儲位址，而不是實際存儲内容

equals比較的是實際的存儲内容，是以自定義類需要重寫equals方法，否則繼承Object中的equals方法，還是比較句柄位址和==一樣。（因為Object類中的equals隻是判斷兩個引用變量是否引用同一對象，如果不是引用同一對象，即使兩個對象的内容完全相同，也會傳回false。）

hashcode：hashcode是将實體位址轉換成一個int數進行比較，同一位址才相同。

和equals方法沒有強制關系，也需要重寫。保證結果是hashcode相同equals不一定相同，equals為真兩對象相等hashcode一定相等。

compareTo(): 擷取的字元串（也可以是其他對象）的長度，然後作減法，這裡的減法就是ASCII碼的減法，是以compareTo()會傳回數字，如果兩個字元串内容相同，會傳回0，字元串a大于字元串b，會傳回相差的ASCII碼的正數，字元串a小于字元串b，會傳回相差的ASCII碼的負數。

簡而言之就是從長度不同傳回長度差，長度相同傳回編碼內插補點。

public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);
        char v1[] = value;
        char v2[] = anotherString.value;
 
        int k = 0;
        while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;
    }

hashmap中equals傳回true那麼compareTo函數應該也傳回0？

resize：擴容

擴容條件

作用：初始化和擴容table數組，傳回的是Node數組

主要思路：

先存儲舊（未擴容）數組的長度、門檻值等
如果舊數組長度大于0

如果舊數組長度超過或者等于最大容量限制，不能繼續擴容，隻能把門檻值指派為最大整型，傳回舊數組。

如果擴容後仍然不超過最大容量限制，就擴容一倍，門檻值也翻一倍。
如果舊數組為null或者長度等于0

門檻值大于0，門檻值就是新數組的大小

門檻值也等于0，就用預設參數來構造新數組
新門檻值計算
根據新門檻值和新容量來new一個新的桶數組。
把舊桶數組的元素複制到新桶數組上

（1）如果舊數組桶位上隻有一個節點，直接按照桶定位指派到新數組的索引處

（2）如果舊數組桶位上存在紅黑樹，那就調用split方法

（3）如果是單連結清單，周遊單連結清單，每一個節點根據hash值和舊數組長度的與某位是0還是1.分别劃分到建立的低連結清單/高連結清單當中。劃分結束後把低連結清單放在新數組的同一索引位置；高連結清單在新數組中的索引位置是舊數組長度+ 舊數組索引。

（目的就是減少一個單連結清單中的節點數目，配置設定到新數組中的兩個地方去。新數組擴充的舊數組兩倍，是以高連結清單的索引是j + oldCap，相當于一碗高高的米飯平分到了兩碗，當然這兩碗要看成一個新碗。。。哈哈哈）

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // 儲存舊（未擴容）的數組
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 儲存舊數組長度
    int oldThr = threshold; // 儲存舊的容量門檻值
    int newCap, newThr = 0;
    // 舊數組長度大于0
    if (oldCap > 0) { 
        // 舊長度達到最大長度限制時，門檻值設為最大整型，不能擴容了，傳回舊數組
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果擴容一倍還在[初始預設長度，最大長度）區間内，就門檻值翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; 
    }
    // 舊數組為null，或長度為0時
    else if (oldThr > 0)  // 舊門檻值大于0，就将舊門檻值作為新的數組大小
        newCap = oldThr;
    else { // 舊門檻值為0，舊容量也為0，就采用預設值（使用無參構造器後，插入一個元素就會執行這裡）
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    /* 新門檻值計算 */
    // 新門檻值為0，新門檻值 = 新的長度 * 負載因子
    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中的所有元素配置設定到新的HashMap
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 周遊處理每一個桶位中的桶，指派給e
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 隻有一個元素的桶，直接指派給新數組
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 桶中不止一個元素時
                else if (e instanceof TreeNode) // 紅黑樹就用split方法分離節點
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 單連結清單就拆分成兩個連結清單
                    Node<K,V> loHead = null, loTail = null; // 原索引處的一個連結清單
                    Node<K,V> hiHead = null, hiTail = null; // 原索引+oldCap的一個連結清單
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 根據hash值的某一位為0還是1将單連結清單拆分成高低兩個連結清單（高低就是指的0/1）
                        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;
}

put和putVal：插入節點（分為單連結清單節點和紅黑樹節點）

put是向hashmap中添加新的鍵值對，或者傳回已有鍵值對中的value值。傳參是key和value。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

主要執行函數是putVal，傳參是待插入鍵值對的key對應的hash方法（hashcode高16位異或）、key、value、後面兩個bool是在linkedhasnmap中需要定義的。傳回值：如果是新加鍵值對，傳回值是null；如果發現存在相同鍵值，直接傳回對應的value值。

主要思路：

先判斷目前桶數組table的大小，要是未初始化就擴容。
如果桶定位得到的索引位置沒有連結清單，就直接建立一個節點（和待插入鍵值對字段相同）插入。
如果目前索引出已經存在連結清單了，在進行判斷

（1）如果連結清單的第一個節點的hash和key和待插入鍵值對一樣，直接取其value值

（2）如果不一樣，并且是紅黑樹結構，直接調用putTreeVal插入紅黑樹節點。

（3）如果hash和key不一樣，是單連結清單結構，就周遊目前連結清單。如果連結清單存在相等key和hash的，就傳回該節點的value，否則在連結清單表尾增加新節點。

（4）根據增加新鍵值對後目前單連結清單的長度，判斷是否要擴容或者紅黑樹化。
如果查到了相同key的鍵值對，就用新的value進行替換，同時傳回舊的value。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 數組未初始化或者長度為0，都要擴容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 桶定位，如果目前索引位置是null，直接建立添加
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 目前索引存在連結清單了
    else {
        Node<K,V> e; K k;
        // 連結清單的頭節點和待插入鍵值對hash、key相同
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 頭節點不相同，且是紅黑樹結構，直接調用putTreeVal方法。
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 目前是單連結清單結構
        else {
            // 周遊單連結清單
            for (int binCount = 0; ; ++binCount) {
                // e = p.next：循環條件 
                if ((e = p.next) == null) {
                    // 表尾新增加鍵值對 ，然後跳出循環
                    p.next = newNode(hash, key, value, null);
                    // 鍵值對數目達到樹化門檻值，判斷是要樹化，還是要擴容
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break; 
                }
                // 周遊中找到相同key的節點，條件中已經指派給了e，是以可以直接跳出循環
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e; // 推動循環
            }
        }
        // 找到了和待插入鍵值對相同key hash 的節點e
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value; // 在這裡用新值替換舊值
            afterNodeAccess(e);  // 空函數
            return oldValue;  // 傳回舊值
        }
    }
    // 此處是新插入了鍵值對，是以hashmap結構變化次數增加
    ++modCount;
    // 鍵值對數量自增，判斷是否擴容
    if (++size > threshold)
        resize(); 
    afterNodeInsertion(evict); // 空函數
    return null;  // 新插入鍵值對，傳回null
}

treeifyBin：樹化

作用是把哈希桶（table數組）中索引位置處的Node單連結清單元素轉化為treeNode雙向連結清單元素，并進行紅黑樹化。這裡調用treeify函數的是hd也就是建立的雙向連結清單。是以該函數分為兩部分：1. 建立雙向連結清單，用原單向連結清單指派 2. 用建好的雙向連結清單調用treeify函數紅黑樹化。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果Table數組容量太小
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //調整擴容
        resize();
    //桶定位 擷取索引位置連結清單 目前連結清單是單向 e是Node類型
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            //函數作用是new一個TreeNode來代替Node
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;  // 指向連結清單的頭結點，該語句隻執行一次
            else {
                // tl相當于目前連結清單的指針
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //更換為TreeNode後的雙向連結清單的頭節點 指派給桶數組 如果不為空（連結清單節點存儲了鍵值對），就把連結清單轉變為紅黑樹。
        if ((tab[index] = hd) != null)
            //執行紅黑樹化，主要語句！！
            hd.treeify(tab);
    }
}

3. HashMap源碼： hashmap方法（增添節點部分）hashmap方法

hashmap方法

tableSizeFor：擷取最小2整數幂

hash：判斷hash值（隻考慮key）

hashcode， ==， equals， compareTo()差別

resize：擴容

put和putVal：插入節點（分為單連結清單節點和紅黑樹節點）

treeifyBin：樹化

繼續閱讀

JAVA基礎之HashMap源碼（JDK 1.8）

Jdk1.8下的HashMap源碼分析

Java集合架構（十八）：HashMap 源碼分析

Jdk1.7下的HashMap源碼分析

HashMap源碼分析及簡單手寫實作一、什麼是HashMap二、源碼分析三、手寫實作四、不足之處（伸縮性角度）

JDK1.8 HashMap putValue源碼解析

HashMap源碼淺析（一）

HashMap源碼重點分析

JDK源碼分析－－HashMap深入了解

容器（十五）：LinkedHashMap容器（十五）：LinkedHashMap

JDK源碼解析集合篇--HashMap無敵全解析

Java中HashMap底層實作原理JDK1.8源碼分析前言一、HashMap的實作原理二、JDK1.8中的涉及到的資料結構三、源碼中的資料域四、HashMap的構造函數五、HashMap的存取機制六、HasMap的擴容機制resize();七、JDK1.8使用紅黑樹的改進

HashMap源碼分析，基于1.8，對比1.7

HashMap源碼（JDK1.8）

HashMap詳解、源碼、擴容、深入了解HashMap、HashMap多線程并發問題

Java集合2-HashMap詳解（含源碼分析）