盤點(diǎn) HashMap 源碼中的那些優(yōu)雅的設(shè)計

HashMap總共給我們提供了三個構(gòu)造器來創(chuàng)建HashMap對象。

1.無參構(gòu)造函數(shù)public HashMap()：使用無參構(gòu)造函數(shù)創(chuàng)建的hashmap對象，其默認(rèn)容量為16，默認(rèn)的負(fù)載因子為0.75。

2.有參構(gòu)造函數(shù)public HashMap(int initialCapacity，float loadFactor)：使用該構(gòu)造函數(shù)，我們可以指定hashmap的初始化容量和負(fù)載因子，但是在hashmap底層不一定會初始化成我們傳入的容量，而是會初始化成大于等于傳入值的最小的2的冪次方，比如我們傳入的是17，那么hashmap會初始化成32（2^5）。那么hashmap是如何高效計算大于等于一個數(shù)的最小2的冪次方數(shù)的呢，源碼如下：

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

它的設(shè)計可以說很巧妙，其基本思想是如果一個二進(jìn)制數(shù)低位全是1，那么這個數(shù)+1則肯定是一個2的冪次方數(shù)。舉個例子看一下：

可以看到，它的計算過程是：首先將我們指定的那個數(shù)cap減1（減1的原因是，如果cap正好是一個2的冪次方數(shù)，也可以正確計算），然后對cap-1分別無符號右移1位、2位，4位、8位、16位(加起來正好是31位)，并且每次移位后都與上一個數(shù)做按位或運(yùn)算，通過這樣的運(yùn)算，會使得最終的結(jié)果低位都是1。那么最終對結(jié)果加1，就會得到一個2的冪次方數(shù)。

3.另一個有參構(gòu)造函數(shù)就是有參構(gòu)造函數(shù)public HashMap(int initialCapacity),該構(gòu)造函數(shù)和上一個構(gòu)造函數(shù)唯一不同之處就是不能指定負(fù)載因子。

二、HashMap插入機(jī)制

1.插入方法源碼

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;
        // 初始化桶數(shù)組 table， table 被延遲到插入新數(shù)據(jù)時再進(jìn)行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果桶中不包含鍵值對節(jié)點(diǎn)引用，說明當(dāng)前數(shù)組下標(biāo)下不存在任何數(shù)據(jù)，則將新鍵值對節(jié)點(diǎn)的引用存入桶中即可
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //如果hash相等，并且equals方法返回true，這說明key相同，此時直接替換value即可，并且返回原值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
             //如果第一個節(jié)點(diǎn)是樹節(jié)點(diǎn)，則調(diào)用putTreeVal方法，將當(dāng)前值放入紅黑樹中
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
               //如果第一個節(jié)點(diǎn)不是樹節(jié)點(diǎn)，則說明還是鏈表節(jié)點(diǎn)，則開始遍歷鏈表，將值存儲到鏈表合適的位置
                for (int binCount = 0; ; ++binCount) {
                     //如果遍歷到了鏈接末尾，則創(chuàng)建鏈表節(jié)點(diǎn)，將數(shù)據(jù)存儲到鏈表結(jié)尾
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //判斷鏈表中節(jié)點(diǎn)樹是否超多了閾值8，如果超過了則將鏈表轉(zhuǎn)換為紅黑樹（當(dāng)然不一定會轉(zhuǎn)換，treeifyBin方法中還有判斷）
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果在鏈表中找到，完全相同的key，則直接替換value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //e!=null說明只是遍歷到中間就break了，該種情況就是在鏈表中找到了完全相等的key,該if塊中就是對value的替換操作
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //加入value之后，更新size，如果超過閾值，則進(jìn)行擴(kuò)容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

2.插入流程圖

（1）在put一個k-v時，首先調(diào)用hash()方法來計算key的hashcode,而在hashmap中并不是簡單的調(diào)用key的hashcode求出一個哈希碼，還用到了擾動函數(shù)來降低哈希沖突。源碼如下：

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

從源碼中可以看到，最終的哈希值是將原哈希碼和原哈希碼右移16位得到的值進(jìn)行異或運(yùn)算的結(jié)果。16正好是32的一半，因此hashmap是將hashcode的高位移動到了低位，再通過異或運(yùn)算將高位散播的低位，從而降低哈希沖突。

至于為什么能夠降低沖突呢，我們可以看看作者對hash方法的注釋：

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide.(Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed,utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

從注釋中我們可以得出，作者進(jìn)行高位向低位散播的原因是：由于hashmap在計算bucket下標(biāo)時，計算方法為hash&n-1,n是一個2的冪次方數(shù)，因此hash&n-1正好取出了hash的低位，比如n是16，那么hash&n-1取出的是hash的低四位，那么如果多個hash的低四位正好完全相等，這就導(dǎo)致了always collide（沖突），即使hash不同。因此將高位向低位散播，讓高位也參與到計算中，從而降低沖突，讓數(shù)據(jù)存儲的更加散列。

（2）在計算出hash之后之后，調(diào)用putVal方法進(jìn)行key-value的存儲操作。在putVal方法中首先需要判斷table是否被初始化了（因?yàn)閔ashmap是延遲初始化的，并不會在創(chuàng)建對象的時候初始化table），如果table還沒有初始化，則通過resize方法進(jìn)行擴(kuò)容。

if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

（3）通過(n-1)&hash計算出當(dāng)前key所在的bucket下標(biāo)，如果當(dāng)前table中當(dāng)前下標(biāo)中還沒有存儲數(shù)據(jù)，則創(chuàng)建一個鏈表節(jié)點(diǎn)直接將當(dāng)前k-v存儲在該下標(biāo)的位置。

if ((p = tab[i = (n - 1) & hash]) == null)
     tab[i] = newNode(hash, key, value, null);

（4）如果table下標(biāo)處已經(jīng)存在數(shù)據(jù)，則首先判斷當(dāng)前key是否和下標(biāo)處存儲的key完全相等，如果相等則直接替換value，并將原有value返回，否則繼續(xù)遍歷鏈表或者存儲到紅黑樹。

if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
      e = p;

（5）當(dāng)前下標(biāo)處的節(jié)點(diǎn)是樹節(jié)點(diǎn)，則直接存儲到紅黑樹中

else if (p instanceof TreeNode)
         e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

（6）如果不是紅黑樹，則遍歷鏈表，如果在遍歷鏈表的過程中，找到相等的key，則替換value，如果沒有相等的key，就將節(jié)點(diǎn)存儲到鏈表尾部（jdk8中采用的是尾插法），并檢查當(dāng)前鏈表中的節(jié)點(diǎn)樹是否超過了閾值8，如果超過了8，則通過調(diào)用treeifyBin方法將鏈表轉(zhuǎn)化為紅黑樹。

for (int binCount = 0; ; ++binCount) {
      if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
              treeifyBin(tab, hash);
          break;
      }
      if (e.hash == hash &&
          ((k = e.key) == key || (key != null && key.equals(k))))
          break;
      p = e;
  }

（7）將數(shù)據(jù)存儲完成之后，需要判斷當(dāng)前hashmap的大小是否超過擴(kuò)容閾值Cap*load_fact,如果大于閾值，則調(diào)用resize()方法進(jìn)行擴(kuò)容。

f (++size > threshold)
       resize();

HashMap在擴(kuò)容后的容量為原容量的2倍，起基本機(jī)制是創(chuàng)建一個2倍容量的table，然后將數(shù)據(jù)轉(zhuǎn)存到新的散列表中，并返回新的散列表。和jdk1.7中不同的是，jdk1.8中多轉(zhuǎn)存進(jìn)行了優(yōu)化，可以不再需要重新計算bucket下標(biāo)，其實(shí)現(xiàn)源碼如下：

從源碼中我們可以看出，如果一個key hash和原容量oldCap按位與運(yùn)算結(jié)果為0，則擴(kuò)容前的bucket下標(biāo)和擴(kuò)容后的bucket下標(biāo)相等，否則擴(kuò)容后的bucket下標(biāo)是原下標(biāo)加上oldCap。

使用的基本原理總結(jié)如下：

1、如果一個數(shù)m和一個2的冪次方數(shù)n進(jìn)行按位與運(yùn)算不等于0，則有：m&(n2-1)=m&(n-1)+n理解：一個2的冪次方數(shù)n，在二進(jìn)制中只有一位為1（假設(shè)第k位是1），其他位均為0，那個如果一個數(shù)m和n進(jìn)行按位與運(yùn)算結(jié)果為0的話，則說明m的二進(jìn)制第k位肯定為0，那么m的前n位和前n-1位所表示的值肯定是相等的。

2、如果一個數(shù)m和一個2的冪次方數(shù)n進(jìn)行按位與運(yùn)算等于0，則有：m&(n2-1)=m&(n-1)理解：一個2的冪次方數(shù)n，在二進(jìn)制中只有一位為1（假設(shè)第k位是1），其他位均為0，那個如果一個數(shù)m和n進(jìn)行按位與運(yùn)算結(jié)果不為0的話，則說明m的二進(jìn)制第k位肯定為1，那么m的前n位和前n-1位所表示的值的差恰好是第k位上的1所表示的數(shù)，二這個數(shù)正好是n。另外，歡迎關(guān)注公眾號Java筆記蝦，后臺回復(fù)“后端面試”，送你一份面試題寶典！

原理圖：

如有文章對你有幫助，
歡迎關(guān)注??、點(diǎn)贊??、轉(zhuǎn)發(fā)??！


推薦， Java面試手冊 
內(nèi)容包括網(wǎng)絡(luò)協(xié)議、Java基礎(chǔ)、進(jìn)階、字符串、集合、并發(fā)、JVM、數(shù)據(jù)結(jié)構(gòu)、算法、MySQL、Redis、Mongo、Spring、SpringBoot、MyBatis、SpringCloud、Linux以及各種中間件（Dubbo、Nginx、Zookeeper、MQ、Kafka、ElasticSearch）等等...

點(diǎn)擊文末“閱讀原文”可直達(dá)