1.概述

HashMap可以說是在java中應(yīng)用最頻繁Map類型了。HashMap 是基于哈希表的 Map 接口的非同步實(shí)現(xiàn)====>這里可以說明，它不能保證映射的順序，特別是它不能保證該順序亙古不變，因?yàn)榧尤氲脑厥歉鶕?jù)哈希值來存儲(chǔ)的。HashMap允許存儲(chǔ)null的key值和null的value值。

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

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

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

2.實(shí)現(xiàn)原理

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

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

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

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

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，并且實(shí)現(xiàn)了Map, Cloneable, Serializable接口。其默認(rèn)的初始容量為16（DEFAULT_INITIAL_CAPACITY = 1 << 4），最大容量為2的30次冪（MAXIMUM_CAPACITY = 1 << 30），默認(rèn)的加載因子為0.75（即當(dāng)HashMap目前存儲(chǔ)的元素超過其初始值加載因子，即160.75=12時(shí)，HashMap會(huì)進(jìn)行擴(kuò)容）。其他的我們可以看到TREEIFY_THRESHOLD = 8;表明當(dāng)鏈表長度超過8時(shí)，會(huì)轉(zhuǎn)化為紅黑樹。

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

 
 
 
 

  
  
  
  
static class Node implements Map.Entry { 
  
  
  
  
      //以下4行即為一個(gè)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); 
  
  
  
  
        /*指定的初始容量如果大于最大容量，則默認(rèn)以最大容量座作為初始容  
  
  
  
  
         *量，則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; 
  
  
  
  
        //新的擴(kuò)容閾值 
  
  
  
  
        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). 
  
  
  
  
     */ 
  
  
  
  
//可以通過注釋看到默認(rèn)的初始值和加載因子 
  
  
  
  
    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); 
  
  
  
  
    } 
 
 
 
 

我們可以看到，即便我們指定了初始容量，初始容量也未必就是我們指定的大小，因?yàn)镠ashMap的容量始終都是2的次冪，所以當(dāng)我們傳入一個(gè)指定的容量時(shí)，還會(huì)調(diào)用一個(gè)tableSizeFor(int cap)方法來計(jì)算容量的大?。?/p>

 
 
 
 

  
  
  
  
/** 
  
  
  
  
     * 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的存取：

1）首先來看存儲(chǔ)：

 
 
 
 

  
  
  
  
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; 
  
  
  
  
        //當(dāng)當(dāng)前數(shù)組為空時(shí)，先進(jìn)行擴(kuò)容 
  
  
  
  
        //可以看出，在我們第一次調(diào)用put方法往HashMap添加元素之和，HashMap的size才開始是初始容量 
  
  
  
  
        if ((tab = table) == null || (n = tab.length) == 0) 
  
  
  
  
            n = (tab = resize()).length; 
  
  
  
  
        //當(dāng)數(shù)組的當(dāng)前位置為空時(shí)，直接創(chuàng)建一個(gè)新的節(jié)點(diǎn)并放進(jìn)去 
  
  
  
  
        if ((p = tab[i = (n - 1) & hash]) == null) 
  
  
  
  
            tab[i] = newNode(hash, key, value, null); 
  
  
  
  
        //當(dāng)前位置非空，產(chǎn)生哈希沖突 
  
  
  
  
        else { 
  
  
  
  
            Node e; K k; 
  
  
  
  
            if (p.hash == hash && 
  
  
  
  
                ((k = p.key) == key || (key != null && key.equals(k)))) 
  
  
  
  
                e = p; 
  
  
  
  
            //判斷當(dāng)前是否已經(jīng)是以紅黑樹為存儲(chǔ)結(jié)構(gòu) 
  
  
  
  
            else if (p instanceof TreeNode) 
  
  
  
  
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); 
  
  
  
  
            else { 
  
  
  
  
                for (int binCount = 0; ; ++binCount) { 
  
  
  
  
                    //當(dāng)遍歷到鏈表的尾端時(shí)，則把需要put的元素加進(jìn)去 
  
  
  
  
                    if ((e = p.next) == null) { 
  
  
  
  
                        p.next = newNode(hash, key, value, null); 
  
  
  
  
                        //判斷沖突的節(jié)點(diǎn)數(shù)是否已經(jīng)達(dá)到閾值8 
  
  
  
  
                        //如果達(dá)到8，則判斷HashMap的size是否已經(jīng)>=64，如果沒有則只進(jìn)行擴(kuò)容 
  
  
  
  
                        //當(dāng)HashMap的size >= 64并且沖突的節(jié)點(diǎn)數(shù)達(dá)到8時(shí)，用紅黑樹去存儲(chǔ)產(chǎn)生沖突的節(jié)點(diǎn) 
  
  
  
  
                        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ìn)行擴(kuò)容

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

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

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

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

舉個(gè)例子說明：

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

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; 
  
  
  
  
        //找到第一個(gè)插入的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; 
  
  
  
  
            //當(dāng)first節(jié)點(diǎn)不是所查找的節(jié)點(diǎn)時(shí) 
  
  
  
  
            if ((e = first.next) != null) { 
  
  
  
  
                //判斷是否當(dāng)前是否用紅黑樹來存儲(chǔ) 
  
  
  
  
                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)方法時(shí)，會(huì)先獲取可以的hash值，并計(jì)算得到此key在數(shù)組中的位置：first = tab[(n - 1) & hash]，如果first節(jié)點(diǎn)不是需要獲取的key，則往下遍歷，直到找到需要獲取的鍵值，并返回對(duì)應(yīng)的value即可。

HashMap的擴(kuò)容機(jī)制

 
 
 
 

  
  
  
  
/** 
  
  
  
  
     * 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，則把新表的容量設(shè)置為舊表容量的兩倍 
  
  
  
  
            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;  //重新計(jì)算該元素在新表中的位置并插入 
  
  
  
  
                    //判斷是否為紅黑樹存儲(chǔ)方式 
  
  
  
  
                    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é)點(diǎn)拆分為兩隊(duì)，e.hash&oldCap結(jié)果為0的一隊(duì)，結(jié)果為1的為另一隊(duì) 
  
  
  
  
                            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; 
  
  
  
  
    } 
 
 
 
 

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

Fail-Fast機(jī)制

原理

fail-fast 機(jī)制是 java 集合(Collection)中的一種錯(cuò)誤機(jī)制。 當(dāng)多個(gè)線程對(duì)同一個(gè)集合的內(nèi)容進(jìn)行操作時(shí)，就可能會(huì)產(chǎn)生 fail-fast 事件。

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

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

這個(gè)策略在源碼中的實(shí)現(xiàn)則是通過modCount，每一次修改map中的內(nèi)容，modCount的值都會(huì)增加，在迭代器開始的過程中，會(huì)把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ā)修改時(shí)，不可能作出任何堅(jiān)決的保證?？焖偈〉鞅M最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的做法是錯(cuò)誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯(cuò)誤。

解決方案

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

與Hashtable的比較

相同點(diǎn)：

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

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

③內(nèi)部容量不足時(shí)，都會(huì)自動(dòng)進(jìn)行擴(kuò)容

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

區(qū)別：

①繼承的父類不同

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

②線程安全性不同

<
網(wǎng)頁題目：詳解HashMap的使用及其實(shí)現(xiàn)
文章網(wǎng)址：http://m.5511xx.com/article/codspjc.html