1.什么是HashMap

• 基于哈希表的Map接口的非同步實現(xiàn)
• 此實現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵
• 此類不保證映射順序
• 此實現(xiàn)假定哈希函數(shù)將元素適當分布在各桶之間趴荸，為讀取操作提供穩(wěn)定性能
• 迭代時間與實例容量(桶的數(shù)量)及其大小(鍵-值映射關(guān)系數(shù))成正比
• 本版本為JDK1.7, 此鏈接為JDK1.8版本(加班趕點中)

2.HashMap的數(shù)據(jù)結(jié)構(gòu)

• 類定義

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

• 重要全局變量 - 鏈表散列的數(shù)據(jù)結(jié)構(gòu)(數(shù)組+鏈表【沖突解決方案-封閉尋址方法】)

備注：建議直接看英文注釋齐遵，更加清晰明了
//The default initial capacity - MUST be a power of two.
static final int DEFAULT_INITIAL_CAPACITY = 16;
//The maximum capacity - MUST be a power of two <= 1<<30.
static final int MAXIMUM_CAPACITY = 1 << 30;
//The load factor used when none specified in constructor.
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//The table, resized as necessary. Length MUST Always be a power of two.
transient Entry<K,V>[] table;
//The number of key-value mappings contained in this map.
transient int size;
//The next size value at which to resize (capacity * load factor).
int threshold;
//The load factor for the hash table.
final float loadFactor;
/**
  * The number of times this HashMap has been structurally modified
  * Structural modifications are those that change the number of mappings in
  * the HashMap or otherwise modify its internal structure (e.g.,
  * rehash).  This field is used to make iterators on Collection-views of
  * the HashMap fail-fast.  (See ConcurrentModificationException).
  */
transient int modCount;

• 構(gòu)造器

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        this.loadFactor = loadFactor;
        //閾值為容量*負載因子和最大容量+1之間的最小值 以此值作為容量翻倍的依據(jù)(不能超過最大容量)
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //初始化一個2次冪的Entry類型數(shù)組 一個桶對應(yīng)一個Entry對象
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() && 
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
}

• 數(shù)組內(nèi)元素的鏈表結(jié)構(gòu)

//靜態(tài)類 默認實現(xiàn)內(nèi)部Entry接口 (接口中可定義內(nèi)部接口-Map.Entry接口為Map的內(nèi)部接口)
//PS:JDK8中引入default歌粥，作用為在接口中定義默認方法實現(xiàn)
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;//key具有引用不可變特性
    V value;
    Entry<K,V> next;//next指向下一個：單向鏈表陨溅，頭插入
    final int hash;
    ……
}

3.HashMap的存儲

• put方法解析
• @return key不存在返回null针余，否則返回舊值

public V put(K key, V value) {
    //其允許存放null的key和null的value
    //當其key為null時脚祟，調(diào)用putForNullKey方法谬以，放入到table[0]的這個位置（null鍵只有一個）
    if (key == null)
        return putForNullKey(value);
    //通過調(diào)用hash方法對key進行哈希，得到哈希之后的數(shù)值
    //其目的是為了盡可能的讓鍵值對可以分不到不同的桶中
    int hash = hash(key);
    //根據(jù)上一步驟中求出的hash得到在數(shù)組中是索引i
    int i = indexFor(hash, table.length);
    //如果i處的Entry不為null由桌，則通過其next指針不斷遍歷e元素的下一個元素为黎。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;//使用臨時變量k主要用于e.key的賦值邮丰，意義有限
        //hash一致 && (key引用相同 或 key字符串比較相同)
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            //值變更
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;//已存在則選擇直接返回舊值
        }
    }
    modCount++;
    addEntry(hash, key, value, i);//新增
    return null;//若key不存在則返回null
}

• hash方法解析

//JDK1.7
final int hash(Object k) {
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h = hashSeed;
    }
    //異或就是兩個數(shù)的二進制形式，按位對比铭乾，相同取0剪廉，不同取一
    //此算法加入了高位計算，防止低位不變炕檩，高位變化時妈经，造成的 hash 沖突
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
//JDK1.8 擾動函數(shù) -> 散列值優(yōu)化函數(shù)
static final int hash(Object key) {
    int h;
    //把一個數(shù)右移16位即丟棄低16為，就是任何小于2^16的數(shù)捧书，右移16后結(jié)果都為0
    //2的16次方再右移剛好就是1 同時int最大值為32位
    //任何一個數(shù)吹泡，與0按位異或的結(jié)果都是這個數(shù)本身
    //為indexFor做準備
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• indexFor方法解析

//@Param h 根據(jù)hash方法得到h
//@Param length 一定是2次冪
//2進制32位帶符號的int表值范圍從-2147483648到2147483648,加起來大概40億空間，內(nèi)存不能直接讀取
//用之前還要先做對數(shù)組的長度取模運算经瓷，得到的余數(shù)才能用來訪問數(shù)組下標
static int indexFor(int h, int length) {
    //2次冪-1 返回的結(jié)果的二進制為永遠是都是1 比如 15 -> 1111 (16 -> 10000)
    //與運算 只有 1 & 1 = 1 正好相當于一個“低位掩碼”
    //如果length-1中某一位為0爆哑，則不論h中對應(yīng)位的數(shù)字為幾，對應(yīng)位結(jié)果都是0舆吮，這樣就讓兩個h取到同一個結(jié)果揭朝，hash沖突
    //同時這個操作可以保證索引不會大于數(shù)組的大小(見開頭的描述)
    return h & (length-1);
}

• addEntry方法解析

//該方法為包訪問 package java.util(本包私有性高于子類)
void addEntry(int hash, K key, V value, int bucketIndex) {
    //當前容量超過閾值 && 當前坐標數(shù)組非空
    //有個優(yōu)雅的設(shè)計在于，若bucketIndex處沒有Entry對象色冀，那么新添加的entry對象指向null潭袱，從而就不會有鏈了
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//容量擴容一倍
        hash = (null != key) ? hash(key) : 0;//hash重新計算
        bucketIndex = indexFor(hash, table.length);//index重新計算
    }
    createEntry(hash, key, value, bucketIndex);//新增Entry元素到數(shù)組的制定下標位置
}
//該方法為包訪問 package java.util
void createEntry(int hash, K key, V value, int bucketIndex) {
    // 獲取指定 bucketIndex 索引處的 Entry
    Entry<K,V> e = table[bucketIndex];
    // 將新創(chuàng)建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry
    // 形成鏈表锋恬，新加入的放入鏈表頭部屯换，最先加入的放入尾部
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

• 關(guān)于indexFor和hash方法的進一步解讀

• hashCode返回的-2147483648到2147483648的int值，加起來大概40億的映射空間与学。只要哈是函數(shù)映射比較均勻松散彤悔，一般很難出現(xiàn)碰撞key.hashCode()
• 但問題是40億長度數(shù)組，內(nèi)存放不小索守，該散列值不能直接拿來用晕窑。用之前必須先對數(shù)組長度取模運算，得到的余數(shù)才能來訪問數(shù)組下標indexFor()
• 長度取2的整次冪卵佛，而length-1時正好相當于一個低位掩碼杨赤。與操作的結(jié)果就是散列的高位全部歸零，只保留低位值截汪，用作下標訪問

     10100101 11000100 00100101
  & 00000000 00000000 00001111
     00000000 00000000 00000101    //高位全部歸零疾牲，只保留末四位

• 但問題是，無論散列值在松散挫鸽，但只取最后幾位说敏，碰撞也很嚴重。更要命的是如果散列本身做的不好丢郊，分布上成等差數(shù)列盔沫，就會出現(xiàn)規(guī)律性重復(fù)
• 擾動函數(shù)生效：
  
  擾動函數(shù)
  
  右位移16位(32位一半)医咨，讓高半?yún)^(qū)和低半?yún)^(qū)做異或，目的是混合原始哈希碼的高位和低位架诞，以此來加大低位的隨機性拟淮。而且混合后的低位包含高位的部分特征，這樣高位的信息也變相保留下來谴忧。
• 當長度非2次冪(最后一位永遠是0)很泊，進行與運算(只有都為1得1，否則為0)沾谓，會造成最后一位永遠是0委造，那最后一位就無法使用，導致(1)空間的巨大浪費均驶。同時可使用的位置比原數(shù)組長度小很多昏兆，(2)進一步增加了碰撞的幾率。

• 歸納

• 存儲時妇穴，根據(jù)hash算法決定其在數(shù)組中的存儲位置爬虱，再根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置;同時HashMap會根據(jù)當前bucket的占用情況自動調(diào)整容量(超過Load Facotr則resize為原來的2倍)
• 讀取時，根據(jù)hash算法找到其在數(shù)組中的存儲位置腾它，再根據(jù)equals方法從該位置上的鏈表中取出該Entry跑筝。
  在產(chǎn)生碰撞的情況下，進行g(shù)et時瞒滴，兩步的時間復(fù)雜度是O(1)+O(n)曲梗。1.8使用紅黑樹(O(1)+O(logn))

4.HashMap的Resize

• 性能參數(shù)

• initialCapacity 初始容量 默認16
• loadFactor(負載因子) : 衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高逛腿，反之愈小稀并。對于使用鏈表法的散列表來說，查找一個元素的平均時間是 O(1+a)单默，因此如果負載因子越大，對空間的利用更充分忘瓦，然而后果是查找效率的降低搁廓；如果負載因子太小，那么散列表的數(shù)據(jù)將過于稀疏耕皮，對空間造成嚴重浪費境蜕。默認的的負載因子 0.75是對空間和時間效率的一個平衡選擇凌停。當容量超出此最大容量時， resize后的HashMap 容量是容量的兩倍

• resize方法解析

/**
  * Rehashes the contents of this map into a new array with a
  * larger capacity.  This method is called automatically when the
  * number of keys in this map reaches its threshold.
  */
//目的：通過增加內(nèi)部數(shù)組的長度的方式罚拟，從而保證鏈表中只保留很少的Entry對象完箩，從而降低put(),remove()和get()方法的執(zhí)行時間
//注意：如果兩個Entry對象的鍵的哈希值不一樣，但它們之前在同一個桶上拉队，那么在調(diào)整以后弊知，并不能保證它們依然在同一個桶上
void resize(int newCapacity) {
    Entry[] oldTable = table;//使用臨時拷貝粱快，保證當前數(shù)據(jù)時效性(參見JAVA的`觀察者`模式實現(xiàn))
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    //實例化一個newCapacity容量的新數(shù)組
    Entry[] newTable = new Entry[newCapacity];
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(newTable, rehash);//遍歷舊數(shù)組對新數(shù)組賦值
    table = newTable;//引用替換
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//重新計算閾值
}

• transfer方法解析

/**
  * Transfers all entries from current table to newTable.
  */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //注意：如果在新表的數(shù)組索引位置相同，則鏈表元素會倒置事哭，也就是先插入最近的
    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);//重新計算hash
            }
            int i = indexFor(e.hash, newCapacity);
            //注意：多線程環(huán)境可能由于執(zhí)行次序非有序造成next引用變更賦值出錯導致環(huán)形鏈接出現(xiàn)漫雷，從而造成死循環(huán)
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

5.Fail-Fast機制

• 錯誤機制

• 當使用迭代器的過程中有其他線程修改了map，將拋出ConcurrentModificationException

• 源碼實現(xiàn)

transient int modCount;//修改計數(shù) put鳍咱、remove或clear時mount++ clear時清空
HashIterator() {
    expectedModCount = modCount;
    if (size > 0) {
    Entry[] t = table;
    while (index < t.length && (next = t[index++]) == null)  
        ;
    }
}
final Entry<K,V> nextEntry() {
    //期望變更數(shù)量不匹配
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();

• HashMap的remove方法實現(xiàn)

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

• HashMap.KeySet的remove方法實現(xiàn)

public boolean remove(Object o) {
    return HashMap.this.removeEntryForKey(o) != null;
}

• HashMap.HashIterator的remove方法實現(xiàn)

public void remove() {
    if (current == null)
        throw new IllegalStateException();
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    Object k = current.key;
    current = null;
    HashMap.this.removeEntryForKey(k);
    //迭代器中刪除時同步了expectedModCount值與modCount相同
    expectedModCount = modCount;
}

• remove方法解析

/**
  * Removes and returns the entry associated with the specified key
  * in the HashMap.  Returns null if the HashMap contains no mapping
  * for this key.
  */
final Entry<K,V> removeEntryForKey(Object key) {
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];//用于記錄該key的前一個元素(默認先從隊首開始)
    Entry<K,V> e = prev;//從隊首開始往隊尾遍歷
    //遍歷key所在鏈表
    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;//remove屬于結(jié)構(gòu)性改造流炕，modCount計數(shù)+1
            size--;//當前Map的有效元素數(shù)量-1
            if (prev == e)
                table[i] = next;//若當前key正好位于隊首澎现，則隊首指向next
            else 
                prev.next = next;//若當前key不位于隊首每辟，則該key之前的元素的next指向該key的下一個元素
            e.recordRemoval(this);//鉤子方法
            return e;
        }
        //繼續(xù)往隊尾找
        prev = e;//指向當前循環(huán)元素的上一個元素
        e = next;//指向下一次循環(huán)元素
    }
    return e;
}

• 迭代推薦方式

Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
　Map.Entry entry = (Map.Entry) iter.next();
　Object key = entry.getKey();
　Object val = entry.getValue();
}

6.常見面試題

1.什么時候會使用HashMap？他有什么特點渠欺？

• 基于Map接口實現(xiàn)的Key-Value容器，允許null值挠将，同時非有序，非同步舔稀。

2.你知道HashMap的工作原理嗎？

• <i class="icon-exclamation-sign">參見歸納 </i>
• 在Java 8中产园，如果一個bucket中碰撞沖突的元素超過某個限制(默認是8)，則使用紅黑樹來替換鏈表什燕，從而提高速度

3.你知道get和put的原理嗎竞端？equals()和hashCode()的都有什么作用屎即？

• 通過對key的hashCode()進行hashing，并計算下標( n-1 & hash)技俐，從而獲得buckets的位置。如果產(chǎn)生碰撞暂刘，則利用key.equals()方法去鏈表或樹中去查找對應(yīng)的節(jié)點

4.你知道hash的實現(xiàn)嗎？為什么要這樣實現(xiàn)谣拣？

• 在Java 1.8的實現(xiàn)中族展，是通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)森缠，主要是從速度、功效仪缸、質(zhì)量來考慮的贵涵，這么做可以在bucket的n比較小的時候，也能保證考慮到高低bit都參與到hash的計算中恰画，同時不會有太大的開銷宾茂。
• 使用hash還有一個好處就是 盡可能確保每個鏈表中的長度一致

5. 如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦拴还？

• 如果超過了負載因子(默認0.75)跨晴，則會重新resize一個原來長度兩倍的HashMap，并且重新調(diào)用hash方法片林；同時此時很可能出現(xiàn)一系列問題:<i class="icon-exclamation-sign">參見問題6 </i>

6. 你了解重新調(diào)整HashMap大小存在什么問題嗎？

• 1.當數(shù)據(jù)過多時焕妙，很可能出現(xiàn)性能瓶頸(包括rehash時間)
  <i class="icon-female"> 使用HashMap時一定保證數(shù)量有限</i>
  2.多線程情況下可能產(chǎn)生條件競競爭從而造成死循環(huán)(具體表現(xiàn)在CPU接近100%)弓摘。多線程同時試著調(diào)整大小焚鹊，可能導致存儲在鏈表中的元素的次序顛倒衣盾，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部蓝撇，這是為了避免尾部遍歷。具體死循環(huán)代碼參見transfer(newTable)
  <i class="icon-female">多線程環(huán)境下推薦使用ConcurrentHashMap </i>

7. 為什么String, Interger這樣的wrapper類適合作為鍵虽抄？

• 1.class具有final屬性，同時重寫equals()和hashCode()
  2.hashCode變動會導致讀取失效
  3.final同時保證線程安全
  <i class="icon-female">對象推薦重寫equals和hashCode方法迈窟，主要用于Map存取時的對比，同時有利于減少碰撞 </i>

8.我們可以使用自定義的對象作為鍵嗎曲稼？

• 這是前一個問題的延伸。當然你可能使用任何對象作為鍵贫悄，只要它遵守了equals()和hashCode()方法的定義規(guī)則娘摔，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的凳寺，那么它已經(jīng)滿足了作為鍵的條件，因為當它創(chuàng)建之后就已經(jīng)不能改變了逆趋。

9.如何對HashMap進行排序怜瞒？

• 轉(zhuǎn)換：Map -> Set -> LinkedList（存key）
• 排序：LinkedList自行sort
• 存儲：存入有序LinkedHashMap

10.HashMap的remove陷阱？

• 通過Iterator方式可正確遍歷完成remove操作
• 直接調(diào)用list的remove方法就會拋異常

10.為什么只允許通過iterator進行remove操作吴汪？

• HashMap和keySet的remove方法都可以通過傳遞key參數(shù)刪除任意的元素
• 而iterator只能刪除當前元素(current)，一旦刪除的元素是iterator對象中next所正在引用的杆融，如果沒有通過modCount霜运、 expectedModCount的比較實現(xiàn)快速失敗拋出異常脾歇，下次循環(huán)該元素將成為current指向淘捡，此時iterator就遍歷了一個已移除的過期數(shù)據(jù)
• 之所以推薦迭代器remove的根本原因在于只有迭代器的remove方法中實現(xiàn)了變更時于modCount的同步工作
  expectedModCount = modCount;

10.如果是遍歷過程中增加或修改數(shù)據(jù)呢？

• 增加或修改數(shù)據(jù)只能通過Map的put方法實現(xiàn)激况，在遍歷過程中修改數(shù)據(jù)可以，但如果增加新key就會在下次循環(huán)時拋異常乌逐，因為在添加新key時modCount也會自增(迭代器只實現(xiàn)了remove方法也是原因之一)