分享HashMap的實作原理

本文分析了HashMap的實作原理，以及resize可能造成死迴圈和Fast-fail等執行緒不安全行為。同時結合原始碼從資料結構，尋址方式，同步方式，計算size等角度分析了JDK 1.7和JDK 1.8中ConcurrentHashMap的實作原理。

線程不安全的HashMap

眾所周知，HashMap是非線程安全的。而HashMap的執行緒不安全主要體現在resize時的死迴圈及使用迭代器時的fast-fail。

附註：本章的程式碼皆基於JDK 1.7.0_67

HashMap工作原理

HashMap資料結構

##常用的底層資料結構主要有陣列和鍊錶。數組儲存區間連續，佔用記憶體較多，尋址容易，插入和刪除困難。鍊錶儲存區間離散，佔用記憶體較少，尋址困難，插入和刪除容易。

HashMap要實現的是哈希表的效果，盡量實現O(1)等級的增刪改查。它的具體實作則是同時使用了陣列和鍊錶，可以認為最外層是一個數組，數組的每個元素是一個鍊錶的表頭。

HashMap尋址方式

對於新插入的數據或待讀取的數據，HashMap將Key的雜湊值對數組長度取模，結果作為該Entry在數組中的index 。在計算機中，取模的代價遠高於位元操作的代價，因此HashMap要求數組的長度必須為2的N次方。此時將Key的雜湊值對2^N-1進行與運算，其效果即與取模等效。 HashMap並非要求使用者在指定HashMap容量時必須傳入一個2的N次方的整數，而是會透過Integer.highestOneBit算出比指定整數小的最大的2^N值，其實作方法如下。

public static int highestOneBit(int i) {
  i |= (i >>  1);
  i |= (i >>  2);
  i |= (i >>  4);
  i |= (i >>  8);
  i |= (i >> 16);  return i - (i >>> 1);
}

由於Key的雜湊值的分佈直接決定了所有資料在雜湊表上的分佈或說決定了雜湊衝突的可能性，因此為防止糟糕的Key的hashCode實現（例如低位都相同，只有高位不相同，與2^N-1取與後的結果都相同），JDK 1.7的HashMap通過如下方法使得最終的哈希值的二進制形式中的1盡量均勻分佈從而盡可能減少哈希衝突。

int h = hashSeed;
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);

resize死循環

transfer方法

當HashMap的size超過Capacity*loadFactor時，就需要對HashMap進行擴容。具體方法是，建立一個新的，長度為原來Capacity兩倍的數組，確保新的Capacity仍為2的N次方，從而保證上述尋址方式仍適用。同時需要透過如下transfer方法將原來的所有資料全部重新插入（rehash）到新的陣列中。

void transfer(Entry[] newTable, boolean rehash) { 
int newCapacity = newTable.length;  
for (Entry<K,V> e : table) {
while(null != e) {
      Entry<K,V> next = e.next;      if (rehash) {
        e.hash = null == e.key ? 0 : hash(e.key);
      }      int i = indexFor(e.hash, newCapacity);
      e.next = newTable[i];
      newTable[i] = e;
      e = next;
    }
  }
}

此方法不保證執行緒安全，而且在多執行緒並發呼叫時，可能會出現死循環。其執行流程如下。從步驟2可見，轉移時鍊錶順序反轉。

1. 遍歷原數組中的元素

2. #對鍊錶上的每一個節點遍歷：用next取得要轉移那個元素的下一個，將e轉移到新數組的頭部，使用頭插法插入節點

3. 循環2，直到鍊錶節點全部轉移

4. 循環1 ，直到所有元素全部轉移

單執行緒rehash

單執行緒情況下，rehash無問題。下圖示範了單執行緒條件下的rehash過程

多執行緒並發下的rehash

這裡假設有兩個執行緒同時執行了put操作並引發了rehash ，執行了transfer方法，並假設線程一進入transfer方法並執行完next = e.next後，因為線程調度所分配時間片用完而“暫停”，此時線程二完成了transfer方法的執行。此時狀態如下。

接著執行緒1被喚醒，繼續執行第一輪迴圈的剩餘部分

e.next = newTable[1] = nullnewTable[1] = e = key(5)
e = next = key(9)

結果如下圖所示

#接著執行下一輪循環，結果狀態圖如下所示

繼續下一輪循環，結果狀態圖如下所示

##此時循環鍊錶形成，且key(11)無法加入到執行緒1的新陣列。在下一次存取該鍊錶時會出現死循環。

Fast-fail

產生原因

在使用迭代器的過程中如果HashMap被修改，那麼

ConcurrentModificationException

將被拋出，也即Fast-fail策略。 當HashMap的iterator()方法被呼叫時，會建構並傳回一個新的EntryIterator對象，並將EntryIterator的expectedModCount設定為HashMap的modCount（該變數記錄了HashMap被修改的次數）。

HashIterator() {
  expectedModCount = modCount;  if (size > 0) { // advance to first entry
  Entry[] t = table;  while (index < t.length && (next = t[index++]) == null)
    ;
  }
}

在通过该Iterator的next方法访问下一个Entry时，它会先检查自己的expectedModCount与HashMap的modCount是否相等，如果不相等，说明HashMap被修改，直接抛出ConcurrentModificationException。该Iterator的remove方法也会做类似的检查。该异常的抛出意在提醒用户及早意识到线程安全问题。

线程安全解决方案

单线程条件下，为避免出现ConcurrentModificationException，需要保证只通过HashMap本身或者只通过Iterator去修改数据，不能在Iterator使用结束之前使用HashMap本身的方法修改数据。因为通过Iterator删除数据时，HashMap的modCount和Iterator的expectedModCount都会自增，不影响二者的相等性。如果是增加数据，只能通过HashMap本身的方法完成，此时如果要继续遍历数据，需要重新调用iterator()方法从而重新构造出一个新的Iterator，使得新Iterator的expectedModCount与更新后的HashMap的modCount相等。

多线程条件下，可使用Collections.synchronizedMap方法构造出一个同步Map，或者直接使用线程安全的ConcurrentHashMap。

Java 7基于分段锁的ConcurrentHashMap

注：本章的代码均基于JDK 1.7.0_67

数据结构

Java 7中的ConcurrentHashMap的底层数据结构仍然是数组和链表。与HashMap不同的是，ConcurrentHashMap最外层不是一个大的数组，而是一个Segment的数组。每个Segment包含一个与HashMap数据结构差不多的链表数组。整体数据结构如下图所示。

寻址方式

在读写某个Key时，先取该Key的哈希值。并将哈希值的高N位对Segment个数取模从而得到该Key应该属于哪个Segment，接着如同操作HashMap一样操作这个Segment。为了保证不同的值均匀分布到不同的Segment，需要通过如下方法计算哈希值。

private int hash(Object k) {  
int h = hashSeed;  
if ((0 != h) && (k instanceof String)) {
return sun.misc.Hashing.stringHash32((String) k);
  }
  h ^= k.hashCode();
  h += (h <<  15) ^ 0xffffcd7d;
  h ^= (h >>> 10);
  h += (h <<   3);
  h ^= (h >>>  6);
  h += (h <<   2) + (h << 14);  return h ^ (h >>> 16);
}

同样为了提高取模运算效率，通过如下计算，ssize即为大于concurrencyLevel的最小的2的N次方，同时segmentMask为2^N-1。这一点跟上文中计算数组长度的方法一致。对于某一个Key的哈希值，只需要向右移segmentShift位以取高sshift位，再与segmentMask取与操作即可得到它在Segment数组上的索引。

int sshift = 0;int ssize = 1;while (ssize < concurrencyLevel) {
  ++sshift;
  ssize <<= 1;
}this.segmentShift = 32 - sshift;this.segmentMask = ssize - 1;
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];

同步方式

Segment继承自ReentrantLock，所以我们可以很方便的对每一个Segment上锁。

对于读操作，获取Key所在的Segment时，需要保证可见性(请参考如何保证多线程条件下的可见性)。具体实现上可以使用volatile关键字，也可使用锁。但使用锁开销太大，而使用volatile时每次写操作都会让所有CPU内缓存无效，也有一定开销。ConcurrentHashMap使用如下方法保证可见性，取得最新的Segment。

Segment<K,V> s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)

获取Segment中的HashEntry时也使用了类似方法

HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
  (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE)

对于写操作，并不要求同时获取所有Segment的锁，因为那样相当于锁住了整个Map。它会先获取该Key-Value对所在的Segment的锁，获取成功后就可以像操作一个普通的HashMap一样操作该Segment，并保证该Segment的安全性。
同时由于其它Segment的锁并未被获取，因此理论上可支持concurrencyLevel（等于Segment的个数）个线程安全的并发读写。

获取锁时，并不直接使用lock来获取，因为该方法获取锁失败时会挂起（参考可重入锁）。事实上，它使用了自旋锁，如果tryLock获取锁失败，说明锁被其它线程占用，此时通过循环再次以tryLock的方式申请锁。如果在循环过程中该Key所对应的链表头被修改，则重置retry次数。如果retry次数超过一定值，则使用lock方法申请锁。

这里使用自旋锁是因为自旋锁的效率比较高，但是它消耗CPU资源比较多，因此在自旋次数超过阈值时切换为互斥锁。

size操作

put、remove和get操作只需要关心一个Segment，而size操作需要遍历所有的Segment才能算出整个Map的大小。一个简单的方案是，先锁住所有Sgment，计算完后再解锁。但这样做，在做size操作时，不仅无法对Map进行写操作，同时也无法进行读操作，不利于对Map的并行操作。

为更好支持并发操作，ConcurrentHashMap会在不上锁的前提逐个Segment计算3次size，如果某相邻两次计算获取的所有Segment的更新次数（每个Segment都与HashMap一样通过modCount跟踪自己的修改次数，Segment每修改一次其modCount加一）相等，说明这两次计算过程中无更新操作，则这两次计算出的总size相等，可直接作为最终结果返回。如果这三次计算过程中Map有更新，则对所有Segment加锁重新计算Size。该计算方法代码如下

public int size() {  
final Segment<K,V>[] segments = this.segments;  int size;  
boolean overflow; // true if size overflows 32 bits
  long sum;         // sum of modCounts
  long last = 0L;   // previous sum
  int retries = -1; // first iteration isn&#39;t retry
  try {for (;;) {      if (retries++ == RETRIES_BEFORE_LOCK) {
  for (int j = 0; j < segments.length; ++j)          
  ensureSegment(j).lock(); // force creation  
  }
      sum = 0L;
      size = 0;
      overflow = false;      for (int j = 0; j < segments.length; ++j) {
        Segment<K,V> seg = segmentAt(segments, j);if (seg != null) {
          sum += seg.modCount;          int c = seg.count;          if (c < 0 || (size += c) < 0)
            overflow = true;
        }
      }      if (sum == last)break;
      last = sum;
    }
  } finally {if (retries > RETRIES_BEFORE_LOCK) {      
  for (int j = 0; j < segments.length; ++j)segmentAt(segments, j).unlock();
    }
  }  return overflow ? Integer.MAX_VALUE : size;
}

不同之处

ConcurrentHashMap与HashMap相比，有以下不同点

• ConcurrentHashMap线程安全，而HashMap非线程安全

• HashMap允许Key和Value为null，而ConcurrentHashMap不允许

• HashMap不允许通过Iterator遍历的同时通过HashMap修改，而ConcurrentHashMap允许该行为，并且该更新对后续的遍历可见

Java 8基于CAS的ConcurrentHashMap

注：本章的代码均基于JDK 1.8.0_111

数据结构

Java 7为实现并行访问，引入了Segment这一结构，实现了分段锁，理论上最大并发度与Segment个数相等。Java 8为进一步提高并发性，摒弃了分段锁的方案，而是直接使用一个大的数组。同时为了提高哈希碰撞下的寻址性能，Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(long(N))）。其数据结构如下图所示

寻址方式

Java 8的ConcurrentHashMap同样是通过Key的哈希值与数组长度取模确定该Key在数组中的索引。同样为了避免不太好的Key的hashCode设计，它通过如下方法计算得到Key的最终哈希值。不同的是，Java 8的ConcurrentHashMap作者认为引入红黑树后，即使哈希冲突比较严重，寻址效率也足够高，所以作者并未在哈希值的计算上做过多设计，只是将Key的hashCode值与其高16位作异或并保证最高位为0（从而保证最终结果为正整数）。

static final int spread(int h) {  
return (h ^ (h >>> 16)) & HASH_BITS;
}

同步方式

对于put操作，如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用synchronized关键字申请锁，然后进行操作。如果该put操作使得当前链表长度超过一定阈值，则将该链表转换为树，从而提高寻址效率。

对于读操作，由于数组被volatile关键字修饰，因此不用担心数组的可见性问题。同时每个元素是一个Node实例（Java 7中每个元素是一个HashEntry），它的Key值和hash值都由final修饰，不可变更，无须关心它们被修改后的可见性问题。而其Value及对下一个元素的引用由volatile修饰，可见性也有保障。

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

对于Key对应的数组元素的可见性，由Unsafe的getObjectVolatile方法保证。

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {  
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

size操作

put方法和remove方法都会通过addCount方法维护Map的size。size方法通过sumCount获取由addCount方法维护的Map的size。

以上是分享HashMap的實作原理的詳細內容。更多資訊請關注PHP中文網其他相關文章！