1,前述

很早之前就想寫博客，一直想找個平臺，github的自定義博客不賴，有些難度自己也沒時間來研究，既然簡書很好那就從簡書開始吧

還有一直想研究個東西，jdk源碼，雖然是java出身，對前景一直有迷惑，不知道該干嘛，想想數(shù)據(jù)結(jié)構(gòu)和算法是重要的，并發(fā)又是很重要的一塊，那就從研究ConcurrentHashMap開始吧

public void main(){
    System.out.print("hello word !");
}

2,map接口

public interface Map<K,V> {
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
    interface Entry<K,V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
    }
    boolean equals(Object o);
    int hashCode();
}

上面列出的是jdk6中的interface內(nèi)容，jdk8新增了一些方法，jdk8開始加入了default修飾符，可以在interface中寫入具體的實現(xiàn)方法，在實現(xiàn)類中可以選擇性決定方法的實現(xiàn)，本文還是以jdk8 中的內(nèi)容來講解，重點方法put () resize()，其他方法都是圍繞此來展開

3,hashmap

3-1,屬性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
{
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認初始化大小16
    static final int MAXIMUM_CAPACITY = 1 << 30;  //默認最大容量
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  //默認擴容因子
    transient Entry[] table;//真正的存儲結(jié)構(gòu)
    transient int size;//當前已經(jīng)存儲元素的個數(shù)
    int threshold; //判斷size是否需要擴容的閾值。也是當前的容量，可以在后面的resize方法分析出來
    final float loadFactor;  //擴容因子，擴容后的容量為 loadFactor * threshold
    transient volatile int modCount;  //map 修改的次數(shù)，包括put 和 delete
}

transient 修飾符表示序列化時不序列化此部分， HashMap 中的存儲數(shù)據(jù)的是數(shù)組，其中沒有被使用到的空間被序列化沒有意義。所以需要手動使用 writeObject() 方法，只序列化實際存儲元素的數(shù)組
默認的參數(shù)表示如果用戶不在構(gòu)造器中設(shè)置則以默認為準

3-2構(gòu)造

public HashMap(int initialCapacity, float loadFactor) {}
public HashMap(int initialCapacity){}
public HashMap(){}
public HashMap(Map<? extends K, ? extends V> m){}

/*
     列舉兩個范例
*/
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);
}
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

所有的構(gòu)造器都只是對屬性進行了賦值，但構(gòu)造器并沒有初始化 table ，這一操作在resize 方法中
loadFactor 擴容比例，如果用戶不指定則以默認為準
threshold 是擴容的閥值，有時候和當前數(shù)組的容量一樣，具體細節(jié)會在resize方法中分析出來，現(xiàn)在只是簡單介紹下，分為幾個情況：
如果構(gòu)造中輸入了initialCapacity參數(shù)，會在構(gòu)造中通過tableSizeFor()計算得出，在resize方法執(zhí)行時，這個值就是數(shù)組的容量，所以要保證2的次冪特性；
如果構(gòu)造器中沒有輸入initialCapacity參數(shù)，會在resize第一次執(zhí)行擴容時容量初始化為16，threshold 初始化為 12，

其中構(gòu)造中的計算方法如下

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;
}

tableSizeFor方法是保證函數(shù)返回值是大于等于參數(shù) initialCapacity 最小的2的冪次方的數(shù)值，比如initialCapacity是20，返回值32(2的5次冪)

/*
    | 或運算
    |= 等價于 n = n | a
    >>> 無符號位的左移

    int n = cap - 1; 
    當前cap本身就是2的次冪時，如果不減一，最終結(jié)果會變成 cap * 2，不符合我們預期
    n |= n >>> 1;
    右移一位，即n的二進制最高位右移1位，再與n本身或操作，最終n的高1-2位都為1
    n |= n >>> 2;
    右移2位，即n的二進制最高1-2位右移2位，與n本身或操作，最終n的高1-4位都是1
    n |= n >>> 4;
    。。。最終n的高位1-8都是1
    n |= n >>> 8;
    。。。最終n的高位1-16都是1
    n |= n >>> 16;
    。。。最終n的高位1-32都是1

    這里可以舉個栗子，假設(shè)給定的cap的值為20
    二進制表示：0001 0011，最終執(zhí)行完的結(jié)果為 0001 1111，再加1 為 0010 0000 = 32
*/

為什么cap要保持為2的冪次方？

存儲數(shù)據(jù)的數(shù)組table的下標是由key的Hash值決定的。在HashMap存儲數(shù)據(jù)的時候，我們期望數(shù)據(jù)能夠均勻分布，以避免哈希沖突。自然而然我們就會想到去用%取余的操作來實現(xiàn)我們這一構(gòu)想。

這里要了解到一個知識：取余(%)操作中如果除數(shù)是2的冪次方則等同于與其除數(shù)減一的與(&)操作。(這樣做比直接取余操作效率要好)

如果newCap是2的次冪時，下面成立：
 index = e.hash & (newCap - 1) 
 等同于：
 index = e.hash % newCap

3-3 node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Node<K,V> 類是HashMap中的靜態(tài)內(nèi)部類，實現(xiàn)Map.Entry<K,V>接口。 是map中value值的載體，除了key鍵、value值之外，還有next節(jié)點，元素之間可以構(gòu)成單向鏈表。

/*
    table 是map的數(shù)組，是所有數(shù)據(jù)的載體，如果key 的hash值有沖突時，就以鏈表存在，node提供了這種支持
*/
transient Entry[] table;

HashMap存儲的數(shù)據(jù)結(jié)構(gòu)：維護了一個數(shù)組，每個數(shù)組又維護了一個單向鏈表。之所以這么設(shè)計，考慮到遇到哈希沖突的時候，同index的value值就用單向鏈表來維護。

3-4 hash方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/*
     index = e.hash & (newCap - 1) 
     ^ 異或操作，一樣則為0
*/

因為hash 的值最終要和 newCap-1 的值進行與操作，而 newCap 是2的次冪，減一后高位全為0，與操作時 hash 的高位就沒有參與進來，index 沖突的幾率會上升，h >>> 16 是將高位也參與到hash 中來能夠降低 index 沖突的幾率。（這是參考其他人的說法，個人不知道為何會降低）

3-5 put方法

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        // tab 為空,調(diào)用resize()初始化tab。
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 通過hash和key確定要存儲在table中的下標，如果沒有被占用,將value封裝為Node存儲
        tab[i] = newNode(hash, key, value, null);
    else {
        //當前key獲取的下標位置已經(jīng)被占用，可能需要用鏈表形式存儲
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // p為數(shù)組的第一個元素，如果key相同，value值應該直接被覆蓋，此時e = p為了在后面的方法中對e進行操作
            e = p;
        else if (p instanceof TreeNode)
            // 如果p是紅黑樹類型，調(diào)用putTreeVal方式賦值
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // index 相同的情況下，但key不同，可能繼續(xù)以鏈表形式存放或者轉(zhuǎn)為紅黑樹存放
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 如果p的next為空，將新的value值添加至鏈表后面
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 如果鏈表長度大于8，鏈表轉(zhuǎn)化為紅黑樹，執(zhí)行插入
                        treeifyBin(tab, hash);
                    break;
                }
                // key相同則跳出循環(huán)，key相同時，會繼續(xù)判斷是否將老的值進行替換
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //根據(jù)規(guī)則選擇是否覆蓋value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); //看源碼注釋好像是為LinkedHashMap準備的
            return oldValue;
        }
    }
    ++modCount; //map被修改的次數(shù)
    if (++size > threshold)
        // size大于加載因子,擴容
        resize();
    afterNodeInsertion(evict);  //看源碼注釋好像是為LinkedHashMap準備的
    return null;
}

注釋寫的已經(jīng)很好了，不需要再解釋

3-6 resize方法

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;//舊table 大小
    int oldThr = threshold;
    int newCap, newThr = 0;
    //分為2種情況，1是table已經(jīng)存在，2是table 不存在需要初始化
    //初始化分為兩種：1threshold > 0 即初始化為自定義的長度，2反之則初始化為默認大小 （這里和構(gòu)造中有關(guān)）
    if (oldCap > 0) {
        // table已存在
        if (oldCap >= MAXIMUM_CAPACITY) {
            // oldCap大于MAXIMUM_CAPACITY,threshold設(shè)置為int的最大值，并且不再繼續(xù)擴容，新的元素放到鏈表或樹
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //newCap設(shè)置為oldCap的2倍并小于MAXIMUM_CAPACITY，且大于默認值, 新的threshold增加為原來的2倍
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        // threshold>0, 將threshold設(shè)置為newCap,所以要用tableSizeFor方法保證threshold是2的冪次方
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 默認初始化，cap為16，threshold為12。除此之外 threshold 等于 數(shù)組的容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // newThr為0，newThr = newCap * 0.75
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //當擴容后，則在現(xiàn)在將容器容量重新賦值給擴容閥值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        // 新生成一個table數(shù)組
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // oldTab 復制到 newTab
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                   // 鏈表只有一個節(jié)點，直接賦值
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // e為紅黑樹的情況
                    ((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;
}

擴容閥值和數(shù)組容量的關(guān)系

擴容分為兩種情況：1是數(shù)組還不存在時需要對數(shù)組進行初始化，2是數(shù)組已經(jīng)存在進行初始化

數(shù)組不存在時：
1，threshold>0, 將threshold設(shè)置為newCap也就是數(shù)組的大小,所以要用tableSizeFor方法保證threshold是2的冪次方
2，threshold = 0，將執(zhí)行默認初始化數(shù)組長度為16，擴容閥值為12
數(shù)組已經(jīng)存在時：
1，長度已經(jīng)超過最大值，不再進行擴容，擴容閥值設(shè)置為integer的最大值，新增的元素只能以鏈表或tree的方式存放
2，長度沒有超過最大值，則將長度設(shè)置為原有的2倍，如果擴大2倍后還沒有超過數(shù)組最大值，則擴容閥值也擴大2倍

這里有個細節(jié)：如果構(gòu)造器中對threshold進行了賦值，那么數(shù)組的容量和閥值一樣，如果沒有賦值，閥值默認為12之后擴容時閥值也會變?yōu)橹暗?倍，但和數(shù)組容量并不一致

3-7remove(key) 方法 & remove(key, value) 方法

default boolean remove(Object key, Object value) {
    Object curValue = get(key);
    if (!Objects.equals(curValue, value) ||
        (curValue == null && !containsKey(key))) {
        return false;
    }
    remove(key);
    return true;
}
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

這兩個方法最終都調(diào)用了removeNode方法

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //判斷tab不為null，長度大于0，hash 對應的數(shù)組元素 也不為null 才可以進行刪除
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // index 元素只有一個元素，node 是需要刪除的節(jié)點，先找到再后面進行刪除
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                // index處是一個紅黑樹，則在紅黑樹中找到需要刪除的node
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // index處是一個鏈表，遍歷鏈表尋找 node
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    //此處p的值已經(jīng)不是鏈表的第一個元素，是需要刪除node 的上一個元素
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 分不同情形刪除節(jié)點
        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)
                //如果是第一個元素直接用next替換掉第一個
                tab[index] = node.next;
            else
                //如果不是第一個，則把上一個的next 直接指向下一個元素，p的元素在執(zhí)行到這一行時，已經(jīng)不是第一個元素
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

注釋寫的很清楚，不需要再進行解釋，這里紅黑樹的加入增加了處理的難度，但在目前的分析中有關(guān)treenode的部分，都有特定的方法，可以暫時不用分析也能看懂大概的邏輯，有關(guān)treenode部分，再下一節(jié)中介紹