閱讀優(yōu)秀的源碼是提升編程技巧的重要手段之一。
如有不對(duì)的地方，歡迎指正~
轉(zhuǎn)載請(qǐng)注明出處https://blog.lzoro.com。

前言

基于JDK1.8。

基本說(shuō)明

常量

以下常量皆為HashMap類中定義

節(jié)點(diǎn)(靜態(tài)內(nèi)部類)

HashMap的實(shí)際負(fù)責(zé)K,V存儲(chǔ)的是transient Node<K,V>[] table，而這里的Node<K,V>則是HashMap的一個(gè)靜態(tài)內(nèi)部類，如下

/**
 * 基本Hash節(jié)點(diǎn)，用于大多數(shù)Entries
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; //Hahs
    final K key;    //鍵    
    V value;        //值
    Node<K,V> next; //下一個(gè)節(jié)點(diǎn)

    /**
     * 構(gòu)造函數(shù)
     */
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    /**
     * 獲取Key
     */
    public final K getKey()        { return key; }
    
    /**
     * 獲取Value
     */
    public final V getValue()      { return value; }
    
    /**
     * ToString
     */
    public final String toString() { return key + "=" + value; }

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

    /**
     * Value設(shè)置
     */
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    /**
     * Equal方法
     */
    public final boolean equals(Object o) {
        //地址比較
        if (o == this)
            return true;
        //是否是Map.Entry實(shí)例
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            //只有當(dāng)Key和value都相等時(shí)，才返回true
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

靜態(tài)工具集

在正式了解HashMap的初始化/存取之前，還有一個(gè)應(yīng)該熟悉的是HashMap提供的靜態(tài)工具集

/**
 * 計(jì)算關(guān)鍵字key的hashCode()并將Hash高位和地位進(jìn)行異或(XORs)
 * 這個(gè)與HashMap中的Table下標(biāo)計(jì)算有關(guān)
 * 哈希桶(table)的長(zhǎng)度都是2的n次冪，So,index僅和hash的低n位有關(guān)
 * 將高16位和低16進(jìn)行異或，讓高16位參與運(yùn)算，防止頻繁碰撞。
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
 * 如果x的類是C且C實(shí)現(xiàn)了Comparable，則返回x的class,否則返回null
 * 如：`class C implements Comparable<C>`的形式 
 *
 */
static Class<?> comparableClassFor(Object x) {
    //判斷x是否是Comparable實(shí)例
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}

/**
 * 如果x不為null且x的Class為1`kc`,則返回k.compareTo(x)
 * 否則返回0
 */
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

/**
 * 返回大于等于cap的最小的2的n次冪
 * 超過(guò)MAXIMUM_CAPACITY，則返回MAXIMUM_CAPACITY
 *
 * 有點(diǎn)抽象，舉個(gè)例子，如這里的cap為11
 * n = 11-1=10
 * 10的二進(jìn)制    -> 0000 1010
 * n |= n >>> 1 -> 0000 1010 
 *                 0000 0101
 *                 0000 1111
 *
 * n |= n >>> 2 -> 0000 1111
 *                 0000 0011
 *                 0000 1111
 *
 * n |= n >>> 4 -> 0000 1111
 *                 0000 0000
 *                 0000 1111
 *
 * n |= n >>> 8 -> 0000 1111
 *                 0000 0000
 *                 0000 1111
 * n |= n >>> 16   0000 1111
 *                 0000 0000
 *                 0000 1111
 *
 * 此時(shí)n的二級(jí)制為0000 1111，即15
 * 既不小于0，也不大于MAXIMUN_CAPACITY，所以返回n+1
 * 
 * 結(jié)果是16，即大于11的且是最小的2的n次冪
 *
 * 具體的原理可以google哈~
 *
 * 膜拜Java大神，膝蓋奉上。
 */
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;
}

初始化過(guò)程

了解了HashMap的常量和靜態(tài)工具集之后，在運(yùn)用方法之前，還需了解下HashMap是怎么被初始化的。

先看下成員變量

/**
 * 負(fù)責(zé)存儲(chǔ)的哈希桶(table), 首次使用的時(shí)候進(jìn)行初始化，在必要的時(shí)候進(jìn)行擴(kuò)容.
 * 分配時(shí)，長(zhǎng)度總是2的n次冪
 * (在某些操作中可以容忍長(zhǎng)度為零，以允許當(dāng)前不需要的引導(dǎo)機(jī)制)
 */
transient Node<K,V>[] table;

/**
 * 緩存entrySet
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * map的size
 */
transient int size;

/**
 * HashMap在結(jié)構(gòu)上的修改次數(shù)
 * 該字段用于fail-fast策略
 * 就是當(dāng)使用迭代器時(shí)，如果發(fā)現(xiàn)預(yù)期的modCount與實(shí)際不合時(shí)拋出ConcurrentModificationException
 */
transient int modCount;

/**
 * 下次resize時(shí)的哈希桶大小(capacity * load factor).
 *
 * @serial
 */
int threshold;

/**
 * hash table的負(fù)載因子
 *
 * @serial
 */
final float loadFactor;

接下來(lái)是HashMap提供的4個(gè)構(gòu)造方法

/**
 * 利用指定的容量和負(fù)載因子構(gòu)造一個(gè)空的HashMap
 *
 * @param  initialCapacity 初始化容量
 * @param  loadFactor      負(fù)載因子
 * @throws 初始容量為負(fù)數(shù)/負(fù)載因子為<=0時(shí)會(huì)拋出IllegalArgumentException
 */
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;
    //這里實(shí)際上并初始化數(shù)組，只是利用上面講到的tableSizeFor計(jì)算了長(zhǎng)度
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 利用指定的容量和默認(rèn)負(fù)載因子(0.75).構(gòu)造一個(gè)空的HashMap
 *
 * @param  initialCapacity 初始化容量
 * @throws 初始容量為負(fù)數(shù)時(shí)會(huì)拋出IllegalArgumentException
 */
public HashMap(int initialCapacity) {
    //實(shí)際調(diào)用的是上面的構(gòu)造函數(shù)
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 利用默認(rèn)初始容量(16)和默認(rèn)負(fù)載因子(0.75).構(gòu)造一個(gè)空的HashMap
 */
public HashMap() {
    //其他成員變量都是默認(rèn)值
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * 根據(jù)給定的Map和默認(rèn)的初始容量以及默認(rèn)負(fù)載因子構(gòu)造一個(gè)HashMap
 *
 * @param   m 
 * @throws  NullPointerException if the specified map is null
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    //這個(gè)方法放在后面說(shuō)明
    putMapEntries(m, false);
}

看了上面四個(gè)構(gòu)造方面，除了利用給定的Map來(lái)進(jìn)行構(gòu)造（第四個(gè)），其他三個(gè)都只是進(jìn)行成員變量的賦值，并未真正進(jìn)行空間的分配。

第四個(gè)構(gòu)造函數(shù)，內(nèi)部其實(shí)是調(diào)用了putMapEntries進(jìn)行初始化并且存放元素，方法內(nèi)部調(diào)用了另外幾個(gè)關(guān)鍵方法，如tableSizeFor(前面已提到)，resize初始化/擴(kuò)容和putVal存放元素(后續(xù)會(huì)分析)。

/**
 * 實(shí)現(xiàn) Map.putAll 和 構(gòu)造函數(shù)
 *
 * @param m the map
 * @param evict false when initially constructing this map, else
 * true (relayed to method afterNodeInsertion).
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    //如果給定的map是空的話，則不進(jìn)行其他操作
    if (s > 0) {
        //map不為空
        //如果哈希桶還未初始化
        if (table == null) { // pre-size
            //計(jì)算相關(guān)閾值
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                //這里的計(jì)算后，不立即進(jìn)行初始化/擴(kuò)容
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            //初始化/擴(kuò)容
            resize();
        //存放元素
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

關(guān)鍵方法

put

用過(guò)HashMap的小伙伴肯定都知道這個(gè)方法，哈？沒(méi)用過(guò)的話。那還是先去用用吧。

可以看到put方法，先是對(duì)key進(jìn)行hash（上面的靜態(tài)工具集有提到）,然后調(diào)用putVal進(jìn)行實(shí)際存儲(chǔ)，另外還有putIfAbsent方法，該方法只在map不存在相應(yīng)的鍵值對(duì)時(shí)進(jìn)行放入。

/**
 * 將給定的key和value存儲(chǔ)到map當(dāng)中
 * 若容器中已存在該key的話，舊的value會(huì)被新的value替代
 */
public V put(K key, V value) {
    //可以看到這里
    return putVal(hash(key), key, value, false, true);
}

/**
 * 如果存在，就不覆蓋舊值
 */
@Override
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

putVal具體實(shí)現(xiàn)

  /**
     * 實(shí)現(xiàn)Map.put和相關(guān)方法
     *
     * @param hash key的hash
     * @param key  key
     * @param value value
     * @param onlyIfAbsent 如果為true，不改變舊值
     * @param evict 如果為false，則表將采取creation模式.
     * @return 前一個(gè)值，如果沒(méi)有則返回null
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //定義相關(guān)變量
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果table未被初始化的話，則調(diào)用resize進(jìn)行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //哈希桶下標(biāo)計(jì)算i=(n-1)&hash，并判斷桶中該位置有沒(méi)有元素
        if ((p = tab[i = (n - 1) & hash]) == null)
            //沒(méi)有元素，則創(chuàng)建新節(jié)點(diǎn)放到該位置
            tab[i] = newNode(hash, key, value, null);
        else {
            //桶中該位置存在元素
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //如果給點(diǎn)節(jié)點(diǎn)的hash和key跟桶上找到的節(jié)點(diǎn)相等，則將舊的p節(jié)點(diǎn)賦值給e
                e = p;
            else if (p instanceof TreeNode)
                //如果p節(jié)點(diǎn)是樹(shù)節(jié)點(diǎn)(紅黑樹(shù))
                //插入一個(gè)樹(shù)節(jié)點(diǎn)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //如果以上兩者皆不是，則證明當(dāng)前鏈表還未樹(shù)化
                //根據(jù)定位的p節(jié)點(diǎn)，進(jìn)行操作
                for (int binCount = 0; ; ++binCount) {
                    //判斷p節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)是否存在
                    if ((e = p.next) == null) {
                        //不存在則創(chuàng)建一個(gè)新節(jié)點(diǎn)進(jìn)行插入
                        p.next = newNode(hash, key, value, null);
                        //鏈表長(zhǎng)度超過(guò)樹(shù)化閾值，則執(zhí)行樹(shù)化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //樹(shù)化
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果p的下一個(gè)節(jié)點(diǎn)e跟給定節(jié)點(diǎn)一致，則跳出循環(huán)
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //把e賦值給p，進(jìn)行鏈表遍歷
                    p = e;
                }
            }
            //如果e不為null
            if (e != null) { // existing mapping for key
                //獲取舊值
                V oldValue = e.value;
                //判斷入?yún)l件onlyIfAbsent/舊值是否為null
                if (!onlyIfAbsent || oldValue == null)
                    //將新值賦值給e節(jié)點(diǎn)
                    e.value = value;
                //空實(shí)現(xiàn) - 主要是為了linkedHashMap的一些后續(xù)處理工作
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //增加modCount - 在上面有給出這個(gè)變量的含義
        ++modCount;
        //若達(dá)到擴(kuò)容閾值，則進(jìn)行擴(kuò)容
        if (++size > threshold)
            //擴(kuò)容
            resize();
        //空實(shí)現(xiàn) 與 afterNodeAccess同理
        afterNodeInsertion(evict);
        return null;
    }

再跟蹤下上面的幾個(gè)方法newNode、putTreeVal、treeifyBin、resize。

newNode是創(chuàng)建一個(gè)新節(jié)點(diǎn)，其實(shí)就是內(nèi)部類Node的一個(gè)實(shí)例，比較簡(jiǎn)單

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

putTreeVal是樹(shù)化后插入節(jié)點(diǎn)的實(shí)現(xiàn)，treeifyBin是對(duì)鏈表進(jìn)行樹(shù)化。
這里的操作涉及到紅黑樹(shù)的操作，如果對(duì)紅黑樹(shù)不了解的話，建議可以先了解下相關(guān)概念和算法，由于篇幅關(guān)系，關(guān)于紅黑樹(shù)后面另開(kāi)章節(jié)分析。

這里簡(jiǎn)單介紹一下基礎(chǔ)概念。

紅黑樹(shù)（Red Black Tree） 是一種自平衡二叉查找樹(shù)，性質(zhì)如下：

• 1.節(jié)點(diǎn)非黑即紅
• 2.根節(jié)點(diǎn)是黑色
• 3.每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的
• 4.每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
• 5.從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)

resize是擴(kuò)容的方法，下面看下具體實(shí)現(xiàn)

/**
 * 初始化或者是將哈希桶(table)大小加倍。
 * 如果為空，則按threshold分配空間
 * 否則，由于采取2的n次冪擴(kuò)展，容器中的元素在新table中要么呆在原索引處, 要么有一個(gè)2的n次冪的位移
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    //舊的哈希桶
    Node<K,V>[] oldTab = table;
    //舊的容量/長(zhǎng)度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //舊的threshold
    int oldThr = threshold;
    //新的相關(guān)標(biāo)量
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            //舊的容量大于等于MAXIMUM_CAPACITY
            //則將threshod賦值為Integer.MAX_VALUE
            threshold = Integer.MAX_VALUE;
            //此時(shí)不再進(jìn)行擴(kuò)容，返回舊的哈希桶
            return oldTab;
        }
        //新的容量為舊容量的的2倍
        //判斷新容量是否小于最大值且舊容量大于默認(rèn)值
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //對(duì)新的threshold賦值(2倍于舊的)
            newThr = oldThr << 1; // double threshold
    }
    //判斷舊的threshold
    //這種情況下，初始容量為threshold的
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //threshold初始化為0，則表明是使用默認(rèn)值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //判斷新的threshold是否為0
    if (newThr == 0) {
        //計(jì)算新的threshold，為新的容量*負(fù)載因子
        float ft = (float)newCap * loadFactor;
        //進(jìn)行最大值判斷
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //將計(jì)算出來(lái)的threshold賦值到成員變量threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //根據(jù)計(jì)算的容量新建一個(gè)哈希桶
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //成員變量table指向新的哈希桶
    table = newTab;
    //判斷舊的哈希桶是否為null
    if (oldTab != null) {
        //下面通過(guò)循環(huán)來(lái)移動(dòng)將舊哈希桶移動(dòng)到新的哈希桶
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //沒(méi)有后續(xù)節(jié)點(diǎn)
                if (e.next == null)
                    //將該節(jié)點(diǎn)存放到新的哈希桶
                    //使用的是2的n次冪的擴(kuò)展(指長(zhǎng)度擴(kuò)為原來(lái)2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置。
                    
                    //eg.1
                    //擴(kuò)容前
                    //e.hash   = 8    -> 0000 1000
                    //oldCap-1 = 15   -> 0000 1111
                                 &    -> 0000 1000
                    //    結(jié)果 = 8             
                    //擴(kuò)容后
                    //e.hash   = 8    -> 0000 1000
                    //newCap-1 = 31   -> 0001 1111
                    //           &    -> 0000 1000
                    //    結(jié)果 = 8 所以位置不變
                
                    //eg.2
                    //擴(kuò)容前
                    //e.hash   = 16   -> 0001 0000
                    //oldCap-1 = 15   -> 0000 1111
                                 &    -> 0000 0000
                    //    結(jié)果 = 0
                    //擴(kuò)容后
                    //e.hash   = 16   -> 0001 0000
                    //newCap-1 = 31   -> 0001 1111
                    //           &    -> 0001 1000
                    //    結(jié)果 = 16
                    //位置移動(dòng)了0 + 16(2的4次冪，也是原來(lái)的容量oldCap)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //如果是樹(shù)化后的節(jié)點(diǎn)，則進(jìn)行split
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                //如果還未樹(shù)化/沒(méi)有后續(xù)節(jié)點(diǎn)
                //維護(hù)順序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //舊鏈表遷移新鏈表
                    do {
                        //取出后續(xù)節(jié)點(diǎn)
                        next = e.next;
                        //這里的e.hash & oldCap 目的是取出高位的1bit來(lái)判斷是否為0，跟上面的 & (oldCap - 1)不同，這里是取出高位1bit來(lái)判斷是否需要移動(dòng)
                        //eg.1
                        // e.hash = 8  -> 0000 1000
                        // oldCap = 16 -> 0001 0000
                                     & -> 0000 0000
                            結(jié)果  =  0 
                        //如果為0，不需要移動(dòng)
                        
                        // e.hash = 16 -> 0001 0000
                        // oldCap = 16 -> 0001 0000
                                     & -> 0001 0000
                            結(jié)果  =  16 
                        //如果不為0
                        
                        //不需要移動(dòng)
                        if ((e.hash & oldCap) == 0) {
                            //不需要移動(dòng)時(shí)，以loHead為首節(jié)點(diǎn)，維護(hù)鏈表順序
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            //需要移動(dòng)時(shí)，以hiHead為首節(jié)點(diǎn)，維護(hù)鏈表順序
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;//最后一個(gè)節(jié)點(diǎn)的next指向的是自己，所以置為null
                        newTab[j] = loHead;//在新的哈希桶中存放鏈表
                    }
                    if (hiTail != null) {
                        hiTail.next = null;//同上面
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    //返回新的哈希桶
    return newTab;
}

這里先拋開(kāi)紅黑樹(shù)，單看哈希桶和鏈表，大致可以將擴(kuò)容總結(jié)如下：

1、計(jì)算新的容量和閾值  
2、根據(jù)新的容量創(chuàng)建新的哈希桶  
3、將舊桶中的元素節(jié)點(diǎn)存放到新的哈希桶  
    3.1、判斷桶中的節(jié)點(diǎn)是否有后續(xù)節(jié)點(diǎn)，沒(méi)有的話，確認(rèn)下標(biāo)后存放元素
    3.2、判斷是否樹(shù)化，如果是，則進(jìn)行紅黑樹(shù)操作(后續(xù)分析)
    3.3、桶中節(jié)點(diǎn)存在后續(xù)節(jié)點(diǎn)(鏈表)，則進(jìn)行鏈表的順序維護(hù)后，存放到新的哈希桶
4、返回?cái)U(kuò)容后的哈希桶

get

現(xiàn)在出門都是成雙成對(duì)了(單身狗出門隨時(shí)一嘴狗糧)，所以HashMap里面既然有put來(lái)存放元素，肯定也有獲取元素的方法，就是現(xiàn)在要分析的get，另外還有jdk1.8新增的getOrDefault。

內(nèi)部主要還是調(diào)用了hash方法對(duì)key進(jìn)行哈希運(yùn)算，然后調(diào)用getNode取得節(jié)點(diǎn)。

/**
 * 如果存在對(duì)應(yīng)的鍵值對(duì)，則根據(jù)對(duì)應(yīng)的key，返回value，否則返回null
 *
 * 更精確點(diǎn)說(shuō)，如果在該map中，存在一個(gè)key跟給定的key相同
 * (同為null，或者調(diào)用equal為true)，則返回該key對(duì)應(yīng)的value,否則返回null
 *
 * null返回值不一定表示map沒(méi)有包含此key的映射
 * 也有可能是映射的value的確是null
 * 可以使用containsKey操作來(lái)區(qū)分這兩種情況（指定的key不存在/key存在但value為null）
 *
 * @see #put(Object, Object)
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * 給定key如果不存在的話，就返回默認(rèn)值
 */
@Override
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

/**
 * 實(shí)現(xiàn) Map.get 和其他相關(guān)方法
 *
 * @param hash key的哈希
 * @param key key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
    //相關(guān)變量
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //檢查哈希桶是否為null，長(zhǎng)度是否大于0，計(jì)算下標(biāo)取出元素判斷是否為null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //對(duì)應(yīng)的下標(biāo)存在元素，則證明該key存在映射
        //每次都對(duì)元素(鏈表首節(jié)點(diǎn))進(jìn)行檢查判斷
        //如果是要找的節(jié)點(diǎn)，則返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果鏈表首節(jié)點(diǎn)不是要找的，則判斷后續(xù)節(jié)點(diǎn)是否存在
        if ((e = first.next) != null) {
            //后續(xù)節(jié)點(diǎn)存在的話，判斷該鏈表是否樹(shù)化過(guò)
            if (first instanceof TreeNode)
                //樹(shù)化過(guò)，則通過(guò)紅黑樹(shù)查找節(jié)點(diǎn)返回(后續(xù)分析)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //未進(jìn)行樹(shù)化，則從鏈表中搜索對(duì)應(yīng)節(jié)點(diǎn)
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //如果未搜索到節(jié)點(diǎn)，則返回null
    return null;
}

remove

成雙成對(duì)，不存在的。這里還有一個(gè)remove方法，用來(lái)移除鍵值對(duì)。

/**
 * 根據(jù)給定的key從map中移除指定鍵值對(duì)
 */
public V remove(Object key) {
    Node<K,V> e;
    //調(diào)用下方的removeNode來(lái)實(shí)現(xiàn)移除
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

/**
 * 根據(jù)給定的key和value從map中移除指定鍵值對(duì)
 */
public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true, true) != null;
    }

/**
 * 實(shí)現(xiàn) Map.remove 和相關(guān)方法
 */
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;
    //前置判斷，包括哈希桶是否為null，長(zhǎng)度是否為0以及是否存在元素等
    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;
        //以下開(kāi)始查找節(jié)點(diǎn)，跟getNode的類似，不再贅述
        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);
            }
        }
        //存在節(jié)點(diǎn)
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                //紅黑樹(shù)移除節(jié)點(diǎn)(后續(xù)分析)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                //如果是首節(jié)點(diǎn)，就將后續(xù)節(jié)點(diǎn)存放到哈希桶對(duì)應(yīng)下標(biāo)上
                tab[index] = node.next;
            else
                //后續(xù)節(jié)點(diǎn)前移
                p.next = node.next;
            //修改操作計(jì)數(shù)
            ++modCount;
            //size - 1
            --size;
            //空實(shí)現(xiàn)
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

clear

清空hashmap的操作

/**
 * 清空所有鍵值對(duì)映射
 * 調(diào)用結(jié)束后map將會(huì)被置空
 */
public void clear() {
    Node<K,V>[] tab;
    //操作計(jì)數(shù) + 1
    modCount++;
    //判斷哈希桶是否已經(jīng)初始化
    if ((tab = table) != null && size > 0) {
        size = 0;
        //循環(huán)清空
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

containsValue

調(diào)用該方法判斷map中是否存在對(duì)應(yīng)的value

/**
 * 如果map中存在指定value，則返回true
 *
 * @param value value whose presence in this map is to be tested
 * @return <tt>true</tt> if this map maps one or more keys to the
 *         specified value
 */
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    //判斷哈希桶是否被初始化過(guò)
    if ((tab = table) != null && size > 0) {
        //哈希桶循環(huán)查詢
        for (int i = 0; i < tab.length; ++i) {
            //哈希桶上每個(gè)元素，進(jìn)行循環(huán)查詢
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                //存在值則返回
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

其他方法

除了上面羅列的一些關(guān)鍵方法外，Hashmap還提供了以下方法，不再具體分析源碼。

• keySet----------------- 獲取所有的key(Set)
• values----------------- 獲取所有的值(Collection)
• entrySet--------------- 獲取鍵值對(duì)集合(Set)
• computeIfAbsent---- 值不存在則放入
• merge------------------ 給定的key沒(méi)有綁定，則進(jìn)行綁定，否則替換原key的值
• forEach---------------- 循環(huán)
• replace/replaceAll--- 替換

注意

HashMap非線程安全，如果在并發(fā)場(chǎng)景下，使用HashMap要小心。

另外，如果需要線程安全的Map，可以移步ConcurrentHashMap。

當(dāng)然，不care效率的話，HashTable也是OK的。

總結(jié)

1、關(guān)鍵常量，如樹(shù)化閾值等，見(jiàn)文章頭部。

1、關(guān)鍵成員變量

• table 哈希桶
• loadFactor 負(fù)載因子
• threshold 閾值

2、構(gòu)造時(shí)，除了指定map進(jìn)行構(gòu)造外，其他構(gòu)造函數(shù)均未初始化哈希桶。

3、通過(guò)hash來(lái)確認(rèn)元素在桶中的位置，所以hash要足夠分散，否則容易造成碰撞導(dǎo)致性能問(wèn)題。

4、其他的諸如put、get、remove等關(guān)鍵操作的流程已在上訴源碼中分析，之后抽空看能不能畫個(gè)圖更直觀。

5、其他的待補(bǔ)充。

篇幅有點(diǎn)長(zhǎng)，溜了溜了，如果對(duì)你有幫助無(wú)妨給個(gè)贊唄~~3Q