簡(jiǎn)書 加薪貓
轉(zhuǎn)載請(qǐng)注明原創(chuàng)出處，謝謝！
這一系列主要介紹HashMap(1.8)，記錄也是分享，歡迎討論

0.HashMap 結(jié)構(gòu)

HashMap 的數(shù)據(jù)存在哪里？數(shù)據(jù)結(jié)構(gòu)是什么？

1.HashMap所有的key-value,存在一個(gè)全局變量Node<K,V>[] table里面。

2.Node<K,V> 這個(gè)的結(jié)構(gòu)具體看代碼

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

hash用來(lái)存儲(chǔ)這個(gè)Node中key經(jīng)過HashMap的hash(K key)方法計(jì)算后得出的，key、value不說(shuō)了，next存儲(chǔ)一下個(gè)Node節(jié)點(diǎn)。HashMap是數(shù)組+鏈表的形式存儲(chǔ)的，當(dāng)然這個(gè)Node的子類還有TreeNode，這個(gè)我們之后再說(shuō)

哈希值是否有重復(fù)？為什么要用鏈表存儲(chǔ)？

按理說(shuō)哈希值是不會(huì)有重復(fù)的，java Object類中的hashCode方法使用類的地址轉(zhuǎn)int，保證了hash值的唯一性，雖說(shuō)哈希值不會(huì)重復(fù)，但是在存儲(chǔ)時(shí)我們還是會(huì)發(fā)生沖突的，具體我們可以看下面的介紹，用鏈表存儲(chǔ)就是為了解決沖突問題的，具體可以仔細(xì)研究1.1.2節(jié)。其次1.8不僅用鏈表，當(dāng)鏈表長(zhǎng)度超過默認(rèn)值（8）時(shí)，HashMap還會(huì)把這個(gè)鏈表轉(zhuǎn)為紅黑樹，這也是為了提升查找效率。

正文

HashMap源碼中最有用，最值得看的就是resize()擴(kuò)容方法，直接去看resize()方法肯定是一頭霧水。

所以這里是從我們最常用的方法一步步去分享。

1. get(Object key)

直接上代碼

public V get(Object key) {
            Node e;
            return(e = getNode(hash(key),key)) ==null?null: e.value;
}

get方法里面主要就是hash 和 getNode

1.1 hash(Object key)

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

1.1.1 hashCode

所有對(duì)象都會(huì)有也是必須有hashCode()方法的，這也就是為什么HashMap的Key要求必須是對(duì)象的原因（不可用基本類型，int,long,等等）。當(dāng)然Value也是要求必須是對(duì)象的，為什么就待日后再說(shuō)。

這是Object類里面hashCode()方法。

 public native int hashCode();

一個(gè)不常見的關(guān)鍵詞 native，使用native關(guān)鍵字說(shuō)明這個(gè)方法是原生函數(shù)，也就是這個(gè)方法是用C/C++語(yǔ)言實(shí)現(xiàn)的。。。后面的不想說(shuō)啦，既然是C系列那么就不在在下的關(guān)注之中了，我們回到源碼Object對(duì)這個(gè)函數(shù)的描寫

 * Returns a hash code value for the object. This method is
 * supported for the benefit of hash tables such as those provided by
 * {@link java.util.HashMap}.
 * 返回對(duì)象的哈希值，這個(gè)方法是為了給哈希表提供幫助的（也就是這次講的HashMap）
 * <p>
 * The general contract of {@code hashCode} is:
 * 約束是
 * <ul>
 * <li>Whenever it is invoked on the same object more than once during
 *     an execution of a Java application, the {@code hashCode} method
 *     must consistently return the same integer, provided no information
 *     used in {@code equals} comparisons on the object is modified.
 *     This integer need not remain consistent from one execution of an
 *     application to another execution of the same application.
 *     在一個(gè)java應(yīng)用執(zhí)行中，對(duì)同一個(gè)對(duì)象多次調(diào)用 hashCode()方法，必須返回相同的整形，
 *     這個(gè)前提是在對(duì)象的比較中，沒有任何信息被修改.相同程序在多次分別執(zhí)行時(shí)，是不需要相同的
 * <li>If two objects are equal according to the {@code equals(Object)}
 *     method, then calling the {@code hashCode} method on each of
 *     the two objects must produce the same integer result.
 *     如果兩個(gè)對(duì)象調(diào)用equals()方法是相等的，那么調(diào)用hashCode方法的返回也是相同的
 * <li>It is <em>not</em> required that if two objects are unequal
 *     according to the {@link java.lang.Object#equals(java.lang.Object)}
 *     method, then calling the {@code hashCode} method on each of the
 *     two objects must produce distinct integer results.  However, the
 *     programmer should be aware that producing distinct integer results
 *     for unequal objects may improve the performance of hash tables.
 *     兩個(gè)不相等的對(duì)象，（不）要求hashCode相同，但是程序猿需要知道，給不相等對(duì)象提供不同的
 *     hash值有利于hash表的查詢
 * </ul>
 * <p>
 * As much as is reasonably practical, the hashCode method defined by
 * class {@code Object} does return distinct integers for distinct
 * objects. (This is typically implemented by converting the internal
 * address of the object into an integer, but this implementation
 * technique is not required by the
 * Java? programming language.)
 * 呵呵，Object自己的hashCode方法在不同的對(duì)象上返回不同的整形
 *（這是依賴內(nèi)部地址轉(zhuǎn)換為整形來(lái)實(shí)現(xiàn)，但是我們重寫這個(gè)方法的時(shí)候不要求這樣~）
 * 
 * @return  a hash code value for this object.
 * @see     java.lang.Object#equals(java.lang.Object)
 * @see     java.lang.System#identityHashCode

1.1.2 >>>

Object.hashCode()已經(jīng)返回了這個(gè)對(duì)象的hash值，那么為什么HashMap里面還有有個(gè)hash方法呢？

(h = key.hashCode()) ^ (h >>> 16)

這個(gè)操作的高度概括就是讓Key的哈希值高位參與運(yùn)算。

為什么要高位參與運(yùn)算呢？

我們算出來(lái)的哈希值是一個(gè)int型，2進(jìn)制32位帶符號(hào)的int是-2147483648~2147483648，其實(shí)很難會(huì)發(fā)生碰撞(上面也說(shuō)到了，Object提供的hashCode方法算出來(lái)不同對(duì)象的哈希值是不會(huì)有重復(fù)的)，如果我們直接使用哈希值作為數(shù)組下標(biāo)訪問的話，內(nèi)存是吃不消的，所以這個(gè)算出來(lái)的哈希值之后會(huì)和 當(dāng)前HashMap的大小做取模運(yùn)算得到的余數(shù) 當(dāng)前HashMap的大小-1 做與運(yùn)算作為下標(biāo)

p = tab[index = (n - 1) & hash]

這一段是之后put方法中使用獲得下標(biāo)的語(yǔ)句，這個(gè)我們之后再講，根據(jù)上面的代碼，我們?cè)倏?。HashMap的默認(rèn)大小是2^4=16,換算成32位的樣式就是

0000 0000 0000 0000 0000 0000 0001 0000 -->16

0000 0000 0000 0000 0000 0000 0000 1111 -->15

當(dāng)我們拿著15去做與運(yùn)算的時(shí)候

從0000 0000 0000 0000 0000 0000 0000 0000

到1111 1111 1111 1111 1111 1111 1111 0000

所有低四位為0的對(duì)象，在這個(gè)HashMap中都會(huì)存到下標(biāo)為0的對(duì)象里面，不考慮擴(kuò)容等問題，這樣的HashMap(1.8之前)他的查找效率就跟鏈表一樣，即使1.8將鏈表大小超過8的鏈表轉(zhuǎn)為紅黑樹，這也不是HashMap的設(shè)計(jì)初衷。

但是我們將算出來(lái)的哈希值右移16位后取異或，那么就當(dāng)前大小16的HashMap來(lái)說(shuō)，參與運(yùn)算的就不只是0 ~ 3位，是0 ~ 3和16 ~ 19位共同的計(jì)算結(jié)果，這個(gè)操作使我們的分布更加均勻。

而我們的HashMap的大小默認(rèn)值是16也就是2^4，而有符號(hào)int標(biāo)志范圍。

順便一提的是這也是為什么我們HashMap的大小必須2的冪次方，因?yàn)檫@樣，大小-1正好是地位掩碼。

1.2 getNode(int hash,Object key)

以上，我們知道了在HashMap中哈希值的計(jì)算方式，下面我們要討論的是取到hash值之后，我們要怎么去取到具體的Value

final Node<K,V> getNode(int hash, Object key) {
        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) {
            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;
    }

我們已經(jīng)知道了，HashMap，最底層的數(shù)據(jù)結(jié)構(gòu)是Node<K,V>[],其實(shí)這段代碼蠻好懂的，就是幾個(gè)條件，唯一值得注意的地方就是，我們?cè)诰唧w判斷的時(shí)候，首先判斷((k = e.key) == key),其次我們還要判斷(key != null && key.equals(k))，==和equals的區(qū)別就不贅述了。

從一個(gè)get方法我們也可以看出，如果我們想用自己新建的一個(gè)類作為HashMap的key,我們一定要正確的重寫這個(gè)類的hashCode()和equals()方法，不然最終的結(jié)果可能并不是我們想要的。

這段代碼里面還有與之前JDK版本相比最大的區(qū)別就是引入了紅黑樹，這段代碼也可以看到，如果我們這個(gè)節(jié)點(diǎn)是TreeNode的話，我們會(huì)使用TreeNode的getTreeNode(hash,key)的方法獲得我們想要的Node節(jié)點(diǎn)，如果不是TreeNode的話，我們會(huì)遍歷鏈表。

今天先到這里~

我是加薪貓
技術(shù)是加薪的前提，生活是加薪的意義
技術(shù)等于生活