前面我們已經(jīng)分析了ArrayList和LinkedList這兩個(gè)集合，我們知道ArrayList是基于數(shù)組實(shí)現(xiàn)的，LinkedList是基于鏈表實(shí)現(xiàn)的。它們各自有自己的優(yōu)劣勢(shì)，例如ArrayList在定位查找元素時(shí)會(huì)優(yōu)于LinkedList，而LinkedList在添加刪除元素時(shí)會(huì)優(yōu)于ArrayList。而本篇介紹的HashMap綜合了二者的優(yōu)勢(shì)，它的底層是基于哈希表實(shí)現(xiàn)的，如果不考慮哈希沖突的話，HashMap在增刪改查操作上的時(shí)間復(fù)雜度都能夠達(dá)到驚人的O(1)。我們先看看它所基于的哈希表的結(jié)構(gòu)。

從上圖中可以看到，哈希表是由數(shù)組和鏈表共同構(gòu)成的一種結(jié)構(gòu)，當(dāng)然上圖是一個(gè)不好的示例，一個(gè)好的哈希函數(shù)應(yīng)該要盡量平均元素在數(shù)組中的分布，減少哈希沖突從而減小鏈表的長(zhǎng)度。鏈表的長(zhǎng)度越長(zhǎng)，意味著在查找時(shí)需要遍歷的結(jié)點(diǎn)越多，哈希表的性能也就越差。接下來我們來看下HashMap的部分成員變量。

//默認(rèn)初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//默認(rèn)最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//默認(rèn)加載因子, 指哈希表可以達(dá)到多滿的尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//空的哈希表
static final Entry<?,?>[] EMPTY_TABLE = {};

//實(shí)際使用的哈希表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//HashMap大小, 即HashMap存儲(chǔ)的鍵值對(duì)數(shù)量
transient int size;

//鍵值對(duì)的閾值, 用于判斷是否需要擴(kuò)增哈希表容量
int threshold;

//加載因子
final float loadFactor;

//修改次數(shù), 用于fail-fast機(jī)制
transient int modCount;

//使用替代哈希的默認(rèn)閥值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

//隨機(jī)的哈希種子, 有助于減少哈希碰撞的次數(shù)
transient int hashSeed = 0;

由成員變量中看到，HashMap默認(rèn)的初始容量為16，默認(rèn)的加載因子是0.75。而threshold是集合能夠存儲(chǔ)的鍵值對(duì)的閥值，默認(rèn)是初始容量*加載因子，也就是16*0.75=12，當(dāng)鍵值對(duì)要超過閥值時(shí)，意味著這時(shí)候的哈希表已處于飽和狀態(tài)，再繼續(xù)添加元素就會(huì)增加哈希沖突，從而使HashMap的性能下降。這時(shí)會(huì)觸發(fā)自動(dòng)擴(kuò)容機(jī)制，以保證HashMap的性能。我們還可以看到哈希表其實(shí)就是一個(gè)Entry數(shù)組，數(shù)組存放的每個(gè)Entry都是單向鏈表的頭結(jié)點(diǎn)。這個(gè)Entry是HashMap的靜態(tài)內(nèi)部類，來看看Entry的成員變量。

static class Entry<K,V> implements Map.Entry<K,V> {
  final K key;   //鍵
  V value;     //值
  Entry<K,V> next; //下一個(gè)Entry的引用
  int hash;     //哈希碼
  
  ...        //省略下面代碼
}

一個(gè)Entry實(shí)例就是一個(gè)鍵值對(duì)，里面包含了key和value，同時(shí)每個(gè)Entry實(shí)例還有一個(gè)指向下一個(gè)Entry實(shí)例的引用。為了避免重復(fù)計(jì)算，每個(gè)Entry實(shí)例還存放了對(duì)應(yīng)的Hash碼?？梢哉fEntry數(shù)組就是HashMap的核心，所有的操作都是針對(duì)這個(gè)數(shù)組來完成的。由于HashMap源碼比較長(zhǎng)，不可能面面俱到的介紹它的所有方法，因此我們只抓住重點(diǎn)來進(jìn)行介紹。接下來我們將以問題為導(dǎo)向，針對(duì)下面幾個(gè)問題深入探究HashMap的內(nèi)部機(jī)制。

1. HashMap在構(gòu)造時(shí)做了哪些操作？

//構(gòu)造器, 傳入初始化容量和加載因子
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0) {
    throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  }
  //如果初始化容量大于最大容量, 就把它設(shè)為最大容量
  if (initialCapacity > MAXIMUM_CAPACITY) {
    initialCapacity = MAXIMUM_CAPACITY;
  }
  //如果加載因子小于0或者加載因子不是浮點(diǎn)數(shù), 則拋出異常
  if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
    throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  }
  //設(shè)置加載因子
  this.loadFactor = loadFactor;
  //閾值為初始化容量
  threshold = initialCapacity;
  init();
}

void init() {}

所有的構(gòu)造器都會(huì)調(diào)用到這個(gè)構(gòu)造器，在這個(gè)構(gòu)造器中我們看到除了對(duì)參數(shù)做一些校驗(yàn)之外，它就做了兩件事，設(shè)置加載因子為傳入的加載因子，設(shè)置閥值為傳入的初始化大小。而init方法是空的，啥也沒做。注意，這時(shí)候并沒有根據(jù)傳入的初始化大小去新建一個(gè)Entry數(shù)組哦。那在什么時(shí)候再去新建數(shù)組呢？繼續(xù)往下看。

2. HashMap添加鍵值對(duì)時(shí)會(huì)進(jìn)行什么操作？

//放置key-value鍵值對(duì)到HashMap中
public V put(K key, V value) {
  //如果哈希表沒有初始化就進(jìn)行初始化
  if (table == EMPTY_TABLE) {
    //初始化哈希表
    inflateTable(threshold);
  }
  if (key == null) {
    return putForNullKey(value);
  }
  //計(jì)算key的hash碼
  int hash = hash(key);
  //根據(jù)hash碼定位在哈希表的位置
  int i = indexFor(hash, table.length);
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    //如果對(duì)應(yīng)的key已經(jīng)存在, 就替換它的value值, 并返回原先的value值
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
      V oldValue = e.value;
      e.value = value;
      e.recordAccess(this);
      return oldValue;
    }
  }
  modCount++;
  //如果沒有對(duì)應(yīng)的key就添加Entry到HashMap中
  addEntry(hash, key, value, i);
  //添加成功返回null
  return null;
}

看到，在添加鍵值對(duì)時(shí)會(huì)先檢查哈希表是否是個(gè)空表，如果是空表就進(jìn)行初始化。之后再進(jìn)行后續(xù)操作，調(diào)用哈希函數(shù)計(jì)算傳入的key的Hash碼。根據(jù)hash碼定位到Entry數(shù)組的指定槽位，然后對(duì)該槽位的單向鏈表進(jìn)行遍歷，如果傳入的已經(jīng)存在了就進(jìn)行替換操作，否則就新建一個(gè)Entry添加到哈希表中。

3. 哈希表是怎樣初始化的？

//初始化哈希表, 會(huì)對(duì)哈希表容量進(jìn)行膨脹, 因?yàn)橛锌赡軅魅氲娜萘坎皇?的冪
private void inflateTable(int toSize) {
  //哈希表容量必須是2的次冪
  int capacity = roundUpToPowerOf2(toSize);
  //設(shè)置閥值, 這里一般是取capacity*loadFactor
  threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  //新建指定容量的哈希表
  table = new Entry[capacity];
  //初始化哈希種子
  initHashSeedAsNeeded(capacity);
}

上面我們知道，在構(gòu)造HashMap時(shí)不會(huì)新建Entry數(shù)組，而是在put操作時(shí)檢查當(dāng)前哈希表是否是個(gè)空表，如果是空表就調(diào)用inflateTable方法進(jìn)行初始化。上面貼出了這個(gè)方法的代碼，可以看到方法內(nèi)部會(huì)重新計(jì)算Entry數(shù)組的容量，因?yàn)樵跇?gòu)造HashMap時(shí)傳入的初始化大小可能不是2的冪，因此要將這個(gè)數(shù)轉(zhuǎn)換成2的冪再去根據(jù)新的容量新建Entry數(shù)組。初始化哈希表時(shí)再次重新設(shè)置閥值，閥值一般是capacity*loadFactor。此外，在初始化哈希表時(shí)還會(huì)去初始化哈希種子(hashSeed)，這個(gè)hashSeed用于優(yōu)化哈希函數(shù)，默認(rèn)為0是不使用替代哈希算法，但是也可以自己去設(shè)置hashSeed的值，以達(dá)到優(yōu)化效果。具體下面會(huì)講到。

4. HashMap在什么時(shí)候判斷是否要擴(kuò)容，以及它是怎樣擴(kuò)容的？

//添加Entry方法, 先判斷是否要擴(kuò)容
void addEntry(int hash, K key, V value, int bucketIndex) {
  //如果HashMap的大小大于閥值并且哈希表對(duì)應(yīng)槽位的值不為空
  if ((size >= threshold) && (null != table[bucketIndex])) {
    //因?yàn)镠ashMap的大小大于閥值, 表明即將發(fā)生哈希沖突, 所以進(jìn)行擴(kuò)容
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
  }
  //在這里表明HashMap的大小沒有超過閥值, 所以不需要擴(kuò)容
  createEntry(hash, key, value, bucketIndex);
}

//對(duì)哈希表進(jìn)行擴(kuò)容
void resize(int newCapacity) {
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  //如果當(dāng)前已經(jīng)是最大容量就只能增大閥值了
  if (oldCapacity == MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return;
  }
  //否則就進(jìn)行擴(kuò)容
  Entry[] newTable = new Entry[newCapacity];
  //遷移哈希表的方法
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  //將當(dāng)前哈希表設(shè)置為新的哈希表
  table = newTable;
  //更新哈希表閾值
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

在調(diào)用put方法添加一個(gè)鍵值對(duì)時(shí)，如果集合中沒有存在的key就去調(diào)用addEntry方法新建一個(gè)Entry?？吹缴厦尜N出的addEntry代碼，在新建一個(gè)Entry之前會(huì)先判斷當(dāng)前集合元素的大小是否超過了閥值，如果超過了閥值就調(diào)用resize進(jìn)行擴(kuò)容。傳入的新的容量是原來哈希表的兩倍，在resize方法內(nèi)部會(huì)新建一個(gè)容量為原先的2倍的Entry數(shù)組。然后將舊的哈希表里面的元素全部遷移到新的哈希表，其中可能會(huì)進(jìn)行再哈希，根據(jù)initHashSeedAsNeeded方法計(jì)算的值來確定是否進(jìn)行再哈希。完成哈希表的遷移之后，將當(dāng)前哈希表替換為新的，最后再根據(jù)新的哈希表容量來重新計(jì)算HashMap的閥值。

5. 為什么Entry數(shù)組的大小必須為2的冪？

 //返回哈希碼對(duì)應(yīng)的數(shù)組下標(biāo)
 static int indexFor(int h, int length) {
   return h & (length-1);
 }

indexFor方法是根據(jù)hash碼來計(jì)算出在數(shù)組中對(duì)應(yīng)的下標(biāo)。我們可以看到在這個(gè)方法內(nèi)部使用了與(&)操作符。與操作是對(duì)兩個(gè)操作數(shù)進(jìn)行位運(yùn)算，如果對(duì)應(yīng)的兩個(gè)位都為1，結(jié)果才為1，否則為0。與操作經(jīng)常會(huì)用于去除操作數(shù)的高位值，例如：01011010 & 00001111 = 00001010。我們繼續(xù)回到代碼中，看看h&(length-1)做了些什么。

已知傳入的length是Entry數(shù)組的長(zhǎng)度，我們知道數(shù)組下標(biāo)是從0開始計(jì)算的，所以數(shù)組的最大下標(biāo)為length-1。如果length為2的冪，那么length-1的二進(jìn)制位后面都為1。這時(shí)h&(length-1)的作用就是去掉了h的高位值，只留下h的低位值來作為數(shù)組的下標(biāo)。由此可以看到Entry數(shù)組的大小規(guī)定為2的冪就是為了能夠使用這個(gè)算法來確定數(shù)組的下標(biāo)。

6. 哈希函數(shù)是怎樣計(jì)算Hash碼的？

//生成hash碼的函數(shù)
final int hash(Object k) {
  int h = hashSeed;
  //key是String類型的就使用另外的哈希算法
  if (0 != h && k instanceof String) {
    return sun.misc.Hashing.stringHash32((String) k);
  }
  h ^= k.hashCode();
  //擾動(dòng)函數(shù)
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

hash方法的最后兩行是真正計(jì)算hash值的算法，計(jì)算hash碼的算法被稱為擾動(dòng)函數(shù)，所謂的擾動(dòng)函數(shù)就是把所有東西雜糅到一起，可以看到這里使用了四個(gè)向右移位運(yùn)算。目的就是將h的高位值與低位值混合一下，以此增加低位值的隨機(jī)性。在上面我們知道定位數(shù)組的下標(biāo)是根據(jù)hash碼的低位值來確定的。key的hash碼是通過hashCode方法來生成的，而一個(gè)糟糕的hashCode方法生成的hash碼的低位值可能會(huì)有很大的重復(fù)。為了使得hash碼在數(shù)組上映射的比較均勻，擾動(dòng)函數(shù)就派上用場(chǎng)了，把高位值的特性糅合進(jìn)低位值，增加低位值的隨機(jī)性，從而使散列分布的更加松散，以此提高性能。下圖舉了個(gè)例子幫助理解。

7. 替代哈希是怎么回事？

我們看到hash方法中首先會(huì)將hashSeed賦值給h。這個(gè)hashSeed就是哈希種子，它是一個(gè)隨機(jī)的值，作用就是幫助優(yōu)化哈希函數(shù)。hashSeed默認(rèn)是0，也就是默認(rèn)不使用替代哈希算法。那么什么時(shí)候使用hashSeed呢？首先需要設(shè)置開啟替代哈希，在系統(tǒng)屬性中設(shè)置jdk.map.althashing.threshold的值，在系統(tǒng)屬性中這個(gè)值默認(rèn)是-1，當(dāng)它是-1的時(shí)候使用替代哈希的閥值為Integer.MAX_VALUE。這也意味著可能你永遠(yuǎn)也不會(huì)使用替代哈希了。當(dāng)然你可以把這個(gè)閥值設(shè)小一點(diǎn)，這樣當(dāng)集合元素達(dá)到閥值后就會(huì)生成一個(gè)隨機(jī)的hashSeed。以此增加hash函數(shù)的隨機(jī)性。為什么要使用替代哈希呢？當(dāng)集合元素達(dá)到你設(shè)定的閥值之后，意味著哈希表已經(jīng)比較飽和了，出現(xiàn)哈希沖突的可能性就會(huì)大大增加，這時(shí)對(duì)再添加進(jìn)來的元素使用更加隨機(jī)的散列函數(shù)能夠使后面添加進(jìn)來的元素更加隨機(jī)的分布在散列表中。

注：以上分析全部基于JDK1.7，不同版本之間會(huì)有較大的改動(dòng)，讀者需要注意。

最新評(píng)論