1.概述

HashMap可以說是在java中應用最頻繁Map類型了。HashMap 是基于哈希表的 Map 接口的非同步實現(xiàn)====>這里可以說明，它不能保證映射的順序，特別是它不能保證該順序亙古不變，因為加入的元素是根據(jù)哈希值來存儲的。HashMap允許存儲null的key值和null的value值。

專注于為中小企業(yè)提供成都網(wǎng)站設計、做網(wǎng)站服務,電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)夷陵免費做網(wǎng)站提供優(yōu)質(zhì)的服務。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了1000+企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。

由于HashMap是基于哈希表來實現(xiàn)的，所以此實現(xiàn)假定哈希函數(shù)將元素適當?shù)胤植荚诟魍爸g，可為基本操作（get 和 put）提供穩(wěn)定的性能。迭代 collection 視圖所需的時間與 HashMap 實例的“容量”（桶的數(shù)量）及其大小（鍵-值映射關系數(shù)）成比例。所以，如果迭代性能很重要，則不要將初始容量設置得太高或?qū)⒓虞d因子設置得太低。

需要注意的是：HashMap 不是同步的，如果多個線程同時訪問一個 HashMap，而其中至少一個線程從結(jié)構(gòu)上（指添加或者刪除一個或多個映射關系的任何操作）修改了，則必須保持外部同步，以防止對映射進行意外的非同步訪問。

2.實現(xiàn)原理

HashMap中的存儲方式是數(shù)組+鏈表+紅黑樹。其中數(shù)組的類型是Entry類型的數(shù)組，當我們往HashMap內(nèi)填充元素時，首先會計算其key的hashcode來重新計算key的hash值，并找到數(shù)組中對應的下標，如果該位置目前并沒有元素，則直接將該元素放入數(shù)組中；如果該位置目前已經(jīng)有了元素，則把新的元素加入到鏈表中。當元素的長度超過閾值（JDK1.8中該值為8）時，鏈表則會轉(zhuǎn)換為紅黑樹（轉(zhuǎn)換為紅黑樹還需要滿足其他的條件，鏈表長度達到閾值只是其中的一個條件），這樣會大大提高我們查找的效率。

HashMap的存儲結(jié)構(gòu)圖。當鏈表過長時（>=8），會轉(zhuǎn)換成紅黑樹來存儲，以便提高查找效率：

使用這種存儲方式是為了解決哈希碰撞的問題，換言之，鏈表中的每個key，都具有相同的哈希值。最極端的情況就是，當所有的元素都具有相同的哈希值，那么HashMap會退化為一個鏈表，查找時間也從O(1)上升到O(N)。當N越來越大時，get(key)方法的開銷也越來越大。因此，在JDK1.8里面加入了一個紅黑樹：當某個桶內(nèi)的記錄過大的話（>=8），HashMap會動態(tài)的使用一個專門的treemap實現(xiàn)來替換掉它。這樣做的結(jié)果會更好，是O(logn)，而不是糟糕的O(n)。它是如何去工作的呢：

前面產(chǎn)生沖突的那些key對應的記錄只是簡單的追加到一個鏈表后面，這些記錄只能通過遍歷來進行查找。但是超過這個閾值后HashMap開始將列表升級成一個二叉樹，使用哈希值作為樹的分支變量，如果兩個哈希值不等，但指向同一個桶的話，較大的那個會插入到右子樹里。如果哈希值相等，HashMap希望key值最好是實現(xiàn)了Comparable接口的，這樣它可以按照順序來進行插入。

3.源碼及分析

首先看一下HashMap的定義以及一些屬性

 
 
 
 

  
  
  
  
public class HashMap extends AbstractMap 
  
  
  
  
    implements Map, Cloneable, Serializable { 
  
  
  
  
    private static final long serialVersionUID = 362498820763181265L; 
  
  
  
  
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
  
  
  
  
    static final int MAXIMUM_CAPACITY = 1 << 30; 
  
  
  
  
    static final float DEFAULT_LOAD_FACTOR = 0.75f; 
  
  
  
  
    static final int TREEIFY_THRESHOLD = 8; 
  
  
  
  
    transient Node[] table; 
  
  
  
  
    transient Set> entrySet; 
  
  
  
  
    transient int size; 
  
  
  
  
    transient int modCount; 
  
  
  
  
    int threshold; 
  
  
  
  
    final float loadFactor; 
 
 
 
 

在這里我們可以看到，HashMap是繼承于AbstractMap，并且實現(xiàn)了Map, Cloneable, Serializable接口。其默認的初始容量為16（DEFAULT_INITIAL_CAPACITY = 1 << 4），最大容量為2的30次冪（MAXIMUM_CAPACITY = 1 << 30），默認的加載因子為0.75（即當HashMap目前存儲的元素超過其初始值加載因子，即160.75=12時，HashMap會進行擴容）。其他的我們可以看到TREEIFY_THRESHOLD = 8;表明當鏈表長度超過8時，會轉(zhuǎn)化為紅黑樹。

HashMap中涉及的數(shù)據(jù)結(jié)構(gòu)：

 
 
 
 

  
  
  
  
static class Node implements Map.Entry { 
  
  
  
  
      //以下4行即為一個Entry  
  
  
  
  
       final int hash; 
  
  
  
  
        final K key;        V value;        Node next; 
  
  
  
  
        Node(int hash, K key, V value, Node next) { 
  
  
  
  
            this.hash = hash;            this.key = key;            this.value = value;            this.next = next; 
  
  
  
  
        } 
 
 
 
 

HashMap的構(gòu)造函數(shù)：

 
 
 
 

  
  
  
  
//構(gòu)造函數(shù)1：指定初始容量和加載因子 
  
  
  
  
    public HashMap(int initialCapacity, float loadFactor) { 
  
  
  
  
        if (initialCapacity < 0) 
  
  
  
  
            throw new IllegalArgumentException("Illegal initial capacity: " + 
  
  
  
  
                                               initialCapacity); 
  
  
  
  
        /*指定的初始容量如果大于最大容量，則默認以最大容量座作為初始容  
  
  
  
  
         *量，則2的30次冪 
  
  
  
  
          */    
  
  
  
  
        if (initialCapacity > MAXIMUM_CAPACITY) 
  
  
  
  
            initialCapacity = MAXIMUM_CAPACITY; 
  
  
  
  
        //加載因子必須為正數(shù) 
  
  
  
  
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
  
  
  
  
            throw new IllegalArgumentException("Illegal load factor: " + 
  
  
  
  
                                               loadFactor); 
  
  
  
  
        this.loadFactor = loadFactor; 
  
  
  
  
        //新的擴容閾值 
  
  
  
  
        this.threshold = tableSizeFor(initialCapacity); 
  
  
  
  
    } 
  
  
  
  
//構(gòu)造函數(shù)2：指定初始容量 
  
  
  
  
    public HashMap(int initialCapacity) { 
  
  
  
  
        this(initialCapacity, DEFAULT_LOAD_FACTOR); 
  
  
  
  
    } 
  
  
  
  
//構(gòu)造函數(shù)3：無參數(shù) 
  
  
  
  
   /** 
  
  
  
  
     * Constructs an empty HashMap with the default initial capacity 
  
  
  
  
     * (16) and the default load factor (0.75). 
  
  
  
  
     */ 
  
  
  
  
//可以通過注釋看到默認的初始值和加載因子 
  
  
  
  
    public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 
  
  
  
  
    }//構(gòu)造函數(shù)4： 
  
  
  
  
    public HashMap(Map m) { 
  
  
  
  
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
  
  
  
  
        putMapEntries(m, false); 
  
  
  
  
    } 
 
 
 
 

我們可以看到，即便我們指定了初始容量，初始容量也未必就是我們指定的大小，因為HashMap的容量始終都是2的次冪，所以當我們傳入一個指定的容量時，還會調(diào)用一個tableSizeFor(int cap)方法來計算容量的大小：

 
 
 
 

  
  
  
  
/** 
  
  
  
  
     * Returns a power of two size for the given target capacity. 
  
  
  
  
     */ 
  
  
  
  
    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; 
  
  
  
  
    } 
 
 
 
 

HashMap的存?。?/p>

1）首先來看存儲：

 
 
 
 

  
  
  
  
public V put(K key, V value) { 
  
  
  
  
        return putVal(hash(key), key, value, false, true); 
  
  
  
  
    } 
  
  
  
  
    /** 
  
  
  
  
     * Implements Map.put and related methods. 
  
  
  
  
     * 
  
  
  
  
     * @param hash hash for key 
  
  
  
  
     * @param key the key 
  
  
  
  
     * @param value the value to put 
  
  
  
  
     * @param onlyIfAbsent if true, don't change existing value 
  
  
  
  
     * @param evict if false, the table is in creation mode. 
  
  
  
  
     * @return previous value, or null if none 
  
  
  
  
     */ 
  
  
  
  
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
  
  
  
  
                   boolean evict) { 
  
  
  
  
        Node[] tab; Node p; int n, i; 
  
  
  
  
        //當當前數(shù)組為空時，先進行擴容 
  
  
  
  
        //可以看出，在我們第一次調(diào)用put方法往HashMap添加元素之和，HashMap的size才開始是初始容量 
  
  
  
  
        if ((tab = table) == null || (n = tab.length) == 0) 
  
  
  
  
            n = (tab = resize()).length; 
  
  
  
  
        //當數(shù)組的當前位置為空時，直接創(chuàng)建一個新的節(jié)點并放進去 
  
  
  
  
        if ((p = tab[i = (n - 1) & hash]) == null) 
  
  
  
  
            tab[i] = newNode(hash, key, value, null); 
  
  
  
  
        //當前位置非空，產(chǎn)生哈希沖突 
  
  
  
  
        else { 
  
  
  
  
            Node e; K k; 
  
  
  
  
            if (p.hash == hash && 
  
  
  
  
                ((k = p.key) == key || (key != null && key.equals(k)))) 
  
  
  
  
                e = p; 
  
  
  
  
            //判斷當前是否已經(jīng)是以紅黑樹為存儲結(jié)構(gòu) 
  
  
  
  
            else if (p instanceof TreeNode) 
  
  
  
  
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); 
  
  
  
  
            else { 
  
  
  
  
                for (int binCount = 0; ; ++binCount) { 
  
  
  
  
                    //當遍歷到鏈表的尾端時，則把需要put的元素加進去 
  
  
  
  
                    if ((e = p.next) == null) { 
  
  
  
  
                        p.next = newNode(hash, key, value, null); 
  
  
  
  
                        //判斷沖突的節(jié)點數(shù)是否已經(jīng)達到閾值8 
  
  
  
  
                        //如果達到8，則判斷HashMap的size是否已經(jīng)>=64，如果沒有則只進行擴容 
  
  
  
  
                        //當HashMap的size >= 64并且沖突的節(jié)點數(shù)達到8時，用紅黑樹去存儲產(chǎn)生沖突的節(jié)點 
  
  
  
  
                        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; 
  
  
  
  
                } 
  
  
  
  
            } 
  
  
  
  
            //如果有相同的key，則用新的value覆蓋舊的value，并把舊的value返回 
  
  
  
  
            if (e != null) { // existing mapping for key 
  
  
  
  
                V oldValue = e.value; 
  
  
  
  
                if (!onlyIfAbsent || oldValue == null) 
  
  
  
  
                    e.value = value; 
  
  
  
  
                afterNodeAccess(e); 
  
  
  
  
                return oldValue; 
  
  
  
  
            } 
  
  
  
  
        } 
  
  
  
  
        ++modCount; 
  
  
  
  
        if (++size > threshold) 
  
  
  
  
            resize(); 
  
  
  
  
        afterNodeInsertion(evict); 
  
  
  
  
        return null; 
  
  
  
  
    } 
 
 
 
 

通過源碼可以看到，put(key, value)的過程為：

①檢查tab[]是否為空或null，如果是，則進行擴容

②根據(jù)鍵值計算其在數(shù)組中的下標i，如果tab[i] == null，則直接插入新建的節(jié)點

③若tab[i]已經(jīng)有元素存儲了，則判斷當前處理節(jié)點的方式為鏈表還是紅黑樹，分別處理

在存儲的時候，有一個細節(jié)需要注意一下：注意到p = tab[i = (n - 1) & hash]，其中的數(shù)組下標是通過（n-1）&hash的方式來計算出來的，這里處理的非常巧妙：

對于任意給定的對象，只要它的 hashCode() 返回值相同，那么程序得到的 hash 碼值總是相同的。我們首先想到的就是把 hash 值對數(shù)組長度取模運算，這樣一來，元素的分布相對來說是比較均勻的。但是，“模”運算的消耗還是比較大的，而HashMap的底層數(shù)組的大小總是為2的n次冪，此時，h& (length-1)運算等價于對 length 取模，也就是 h%length。

舉個例子說明：

我們可以看到，當數(shù)組長度為15時，8或9與其相遇，都會產(chǎn)生相同的結(jié)果，此時就會發(fā)生哈希沖突，8和9都會放到數(shù)組中的同一個位置，形成鏈表，這樣會降低了查詢的效率。同時，我們可以發(fā)現(xiàn)，當數(shù)組長度不為2的n次冪時，table.length-1永遠會有0存在，而0無論是和1還是0相與，結(jié)果都為0。比如說，長度為15，那么15-1=14，其二進制為1110，此時，無論什么數(shù)與1110相與，末尾都為0，這時候，0001，0011，0101，1001，1011，0111，1101 這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數(shù)組可以使用的位置比數(shù)組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！而當數(shù)組的長度為2的n次冪時，table.length-1得到的二進制數(shù)的每個位上的值都為 1，這使得在低位上&時，得到的和原 hash 的低位相同，就使得只有相同的 hash 值的兩個值才會被放到數(shù)組中的同一個位置上形成鏈表。所以說，當數(shù)組長度為 2 的 n 次冪的時候，不同的 key 算得得 index 相同的幾率較小，那么數(shù)據(jù)在數(shù)組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了

2）HashMap的讀?。?/p>

 
 
 
 

  
  
  
  
public V get(Object key) { 
  
  
  
  
        Node e; 
  
  
  
  
        return (e = getNode(hash(key), key)) == null ? null : e.value; 
  
  
  
  
    } 
  
  
  
  
    /** 
  
  
  
  
     * Implements Map.get and related methods. 
  
  
  
  
     * 
  
  
  
  
     * @param hash hash for key 
  
  
  
  
     * @param key the key 
  
  
  
  
     * @return the node, or null if none 
  
  
  
  
     */ 
  
  
  
  
    final Node getNode(int hash, Object key) { 
  
  
  
  
        Node[] tab; Node first, e; int n; K k; 
  
  
  
  
        //找到第一個插入的node 
  
  
  
  
        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; 
  
  
  
  
            //當first節(jié)點不是所查找的節(jié)點時 
  
  
  
  
            if ((e = first.next) != null) { 
  
  
  
  
                //判斷是否當前是否用紅黑樹來存儲 
  
  
  
  
                if (first instanceof TreeNode) 
  
  
  
  
                    return ((TreeNode)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; 
  
  
  
  
    } 
 
 
 
 

在調(diào)用get(key)方法時，會先獲取可以的hash值，并計算得到此key在數(shù)組中的位置：first = tab[(n - 1) & hash]，如果first節(jié)點不是需要獲取的key，則往下遍歷，直到找到需要獲取的鍵值，并返回對應的value即可。

HashMap的擴容機制

 
 
 
 

  
  
  
  
/** 
  
  
  
  
     * Initializes or doubles table size.  If null, allocates in 
  
  
  
  
     * accord with initial capacity target held in field threshold. 
  
  
  
  
     * Otherwise, because we are using power-of-two expansion, the 
  
  
  
  
     * elements from each bin must either stay at same index, or move 
  
  
  
  
     * with a power of two offset in the new table. 
  
  
  
  
     * 
  
  
  
  
     * @return the table 
  
  
  
  
     */ 
  
  
  
  
    final Node[] resize() { 
  
  
  
  
        Node[] oldTab = table; 
  
  
  
  
        int oldCap = (oldTab == null) ? 0 : oldTab.length; 
  
  
  
  
        int oldThr = threshold; 
  
  
  
  
        int newCap, newThr = 0; 
  
  
  
  
        if (oldCap > 0) { 
  
  
  
  
            if (oldCap >= MAXIMUM_CAPACITY) { 
  
  
  
  
                threshold = Integer.MAX_VALUE; 
  
  
  
  
                return oldTab; 
  
  
  
  
            } 
  
  
  
  
            //舊表的長度不為0，則把新表的容量設置為舊表容量的兩倍 
  
  
  
  
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
  
  
  
  
                     oldCap >= DEFAULT_INITIAL_CAPACITY) 
  
  
  
  
                newThr = oldThr << 1; // double threshold 
  
  
  
  
        } 
  
  
  
  
        else if (oldThr > 0) // initial capacity was placed in threshold 
  
  
  
  
            newCap = oldThr; 
  
  
  
  
        //如果舊表的長度為0，則說明是第一次初始化 
  
  
  
  
        else {               // zero initial threshold signifies using defaults 
  
  
  
  
            newCap = DEFAULT_INITIAL_CAPACITY; 
  
  
  
  
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 
  
  
  
  
        } 
  
  
  
  
        if (newThr == 0) { 
  
  
  
  
            float ft = (float)newCap * loadFactor; 
  
  
  
  
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 
  
  
  
  
                      (int)ft : Integer.MAX_VALUE); 
  
  
  
  
        } 
  
  
  
  
        threshold = newThr; 
  
  
  
  
        @SuppressWarnings({"rawtypes","unchecked"}) 
  
  
  
  
        Node[] newTab = (Node[])new Node[newCap]; 
  
  
  
  
        table = newTab; 
  
  
  
  
        if (oldTab != null) { 
  
  
  
  
            for (int j = 0; j < oldCap; ++j) { 
  
  
  
  
                Node e; 
  
  
  
  
                if ((e = oldTab[j]) != null) { 
  
  
  
  
                    oldTab[j] = null; 
  
  
  
  
                    //e.next為null說明此位置沒有形成鏈表 
  
  
  
  
                    if (e.next == null) 
  
  
  
  
                        newTab[e.hash & (newCap - 1)] = e;  //重新計算該元素在新表中的位置并插入 
  
  
  
  
                    //判斷是否為紅黑樹存儲方式 
  
  
  
  
                    else if (e instanceof TreeNode) 
  
  
  
  
                        ((TreeNode)e).split(this, newTab, j, oldCap); 
  
  
  
  
                    else { // preserve order 
  
  
  
  
                        Node loHead = null, loTail = null; 
  
  
  
  
                        Node hiHead = null, hiTail = null; 
  
  
  
  
                        Node next; 
  
  
  
  
                        //遍歷鏈表 
  
  
  
  
                        do { 
  
  
  
  
                            next = e.next; 
  
  
  
  
                            //將鏈表的節(jié)點拆分為兩隊，e.hash&oldCap結(jié)果為0的一隊，結(jié)果為1的為另一隊 
  
  
  
  
                            if ((e.hash & oldCap) == 0) { 
  
  
  
  
                                if (loTail == null) 
  
  
  
  
                                    loHead = e; 
  
  
  
  
                                else 
  
  
  
  
                                    loTail.next = e; 
  
  
  
  
                                loTail = e; 
  
  
  
  
                            } 
  
  
  
  
                            else { 
  
  
  
  
                                if (hiTail == null) 
  
  
  
  
                                    hiHead = e; 
  
  
  
  
                                else 
  
  
  
  
                                    hiTail.next = e; 
  
  
  
  
                                hiTail = e; 
  
  
  
  
                            } 
  
  
  
  
                        } while ((e = next) != null); 
  
  
  
  
                        if (loTail != null) { 
  
  
  
  
                            loTail.next = null; 
  
  
  
  
                            newTab[j] = loHead; 
  
  
  
  
                        } 
  
  
  
  
                        if (hiTail != null) { 
  
  
  
  
                            hiTail.next = null; 
  
  
  
  
                            newTab[j + oldCap] = hiHead; 
  
  
  
  
                        } 
  
  
  
  
                    } 
  
  
  
  
                } 
  
  
  
  
            } 
  
  
  
  
        } 
  
  
  
  
        return newTab; 
  
  
  
  
    } 
 
 
 
 

當HashMap中的元素越來越多的時候，產(chǎn)生哈希沖突的幾率也就越來越大，畢竟數(shù)組的長度是固定的。為了減小哈希沖突的幾率，同時也是為了提高查詢效率，我們需要對HashMap適當?shù)倪M行擴容。而擴容也不是產(chǎn)生哈希沖突之后就開始執(zhí)行，而是要滿足一定條件之后才擴容：當HashMap中元素的個數(shù)已經(jīng)達到閾值，則table.length * loadFactory，比如說采用無參數(shù)構(gòu)造器去創(chuàng)建一個HashMap，那么table.length * loadFactory = 16 * 0.75 == 12，即當HashMap中的元素個數(shù)達到12時，HashMap才開始擴容。擴容之后的大小為之前的兩倍。我們在源碼中可以看到，擴容是一項很費時的操作，如果我們能夠預知HashMap中元素的個數(shù)，那么在初始化時指定初始值以及加載因子來規(guī)避擴容，也是提高性能的一種方法。

Fail-Fast機制

原理

fail-fast 機制是 java 集合(Collection)中的一種錯誤機制。 當多個線程對同一個集合的內(nèi)容進行操作時，就可能會產(chǎn)生 fail-fast 事件。

比如說，在線程A通過 iterator去訪問集合時，如果有其他線程修改了該集合，那么A線程這里就會拋出 ConcurrentModificationException 異常，產(chǎn)生 fail-fast 事件。

我們知道，java.util.HashMap不是線程安全的，在多線程的環(huán)境中，如果A線程正在通過iterator去訪問這個map，而其他線程則修改了該map，那么A線程就會拋出一個ConcurrentModificationException異常。

這個策略在源碼中的實現(xiàn)則是通過modCount，每一次修改map中的內(nèi)容，modCount的值都會增加，在迭代器開始的過程中，會把modCount的值賦給迭代器的 expectedModCount：

 
 
 
 

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

在迭代過程中，判斷 modCount 跟 expectedModCount 是否相等，如果不相等就表示已經(jīng)有其他線程修改了 map：

 
 
 
 

  
  
  
  
final Node nextNode() { 
  
  
  
  
            Node[] t;            Node e = next;            if (modCount != expectedModCount) 
  
  
  
  
                throw new ConcurrentModificationException(); 
  
  
  
  
            ...        } 
 
 
 
 

注意，迭代器的快速失敗行為不能得到保證，一般來說，存在非同步的并發(fā)修改時，不可能作出任何堅決的保證?？焖偈〉鞅M最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的做法是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。

解決方案

fail-fast 機制，是一種錯誤檢測機制。它只能被用來檢測錯誤，因為 JDK 并不保證 fail-fast 機制一定會發(fā)生。若在多線程環(huán)境下使用 fail-fast 機制的集合，建議使用“java.util.concurrent 包下的類”去取代“java.util 包下的類”。

與Hashtable的比較

相同點：

①都是基于哈希表實現(xiàn)的，并且里面存儲的元素都是key-value對

②當產(chǎn)生哈希沖突時，內(nèi)部都會通過單鏈表去解決沖突問題（當然JDK1.8中HashMap中加入了紅黑樹）

③內(nèi)部容量不足時，都會自動進行擴容

④都實現(xiàn)了Map、Cloneable、Serializable接口，可以被克隆，支持序列化

區(qū)別：

①繼承的父類不同

HashMap繼承的是AbstractMap，而Hashtable繼承的是Dictionary

②線程安全性不同

<
文章標題：詳解HashMap的使用及其實現(xiàn)
網(wǎng)頁地址：http://www.dlmjj.cn/article/codspjc.html