HashMap原理

HashMap也是我們使用非常多的Collection麦萤，它是基于哈希表的 Map 接口的實(shí)現(xiàn)，以key-value的形式存在本涕。在HashMap中烹笔，key-value總是會(huì)當(dāng)做一個(gè)整體來(lái)處理，系統(tǒng)會(huì)根據(jù)hash算法來(lái)來(lái)計(jì)算key-value的存儲(chǔ)位置澄耍，我們總是可以通過(guò)key快速地存噪珊、取value。下面就來(lái)分析HashMap的存取齐莲。

一痢站、定義

HashMap實(shí)現(xiàn)了Map接口，繼承AbstractMap选酗。其中Map接口定義了鍵映射到值的規(guī)則瑟押，而AbstractMap類(lèi)提供 Map 接口的骨干實(shí)現(xiàn)，以最大限度地減少實(shí)現(xiàn)此接口所需的工作星掰，其實(shí)AbstractMap類(lèi)已經(jīng)實(shí)現(xiàn)了Map，這里標(biāo)注Map LZ覺(jué)得應(yīng)該是更加清晰吧嫩舟！

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

二氢烘、構(gòu)造函數(shù)

HashMap提供了三個(gè)構(gòu)造函數(shù)：
HashMap()：
??構(gòu)造一個(gè)具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的HashMap。
HashMap(int initialCapacity)：
??構(gòu)造一個(gè)帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap家厌。
HashMap(int initialCapacity, float loadFactor)：
??構(gòu)造一個(gè)帶指定初始容量和加載因子的空 HashMap播玖。

在這里提到了兩個(gè)參數(shù)：
?? 初始容量，加載因子饭于。這兩個(gè)參數(shù)是影響HashMap性能的重要參數(shù)蜀踏，其中容量表示哈希表中桶的數(shù)量，初始容量是創(chuàng)建哈希表時(shí)的容量掰吕，加載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿(mǎn)的一種尺度果覆，它衡量的是一個(gè)散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高殖熟，反之愈小局待。對(duì)于使用鏈表法的散列表來(lái)說(shuō)，查找一個(gè)元素的平均時(shí)間是O(1+a)，因此如果負(fù)載因子越大钳榨，對(duì)空間的利用更充分舰罚，然而后果是查找效率的降低；如果負(fù)載因子太小薛耻，那么散列表的數(shù)據(jù)將過(guò)于稀疏营罢，對(duì)空間造成嚴(yán)重浪費(fèi)。系統(tǒng)默認(rèn)負(fù)載因子為0.75饼齿，一般情況下我們是無(wú)需修改的饲漾。

HashMap是一種支持快速存取的數(shù)據(jù)結(jié)構(gòu)，要了解它的性能必須要了解它的數(shù)據(jù)結(jié)構(gòu)候醒。

三能颁、數(shù)據(jù)結(jié)構(gòu)

我們知道在Java中最常用的兩種結(jié)構(gòu)是數(shù)組和模擬指針(引用)，幾乎所有的數(shù)據(jù)結(jié)構(gòu)都可以利用這兩種來(lái)組合實(shí)現(xiàn)倒淫，HashMap也是如此伙菊。實(shí)際上HashMap是一個(gè)“鏈表散列”，如下是它數(shù)據(jù)結(jié)構(gòu)：

152128347367.png

從上圖我們可以看出HashMap底層實(shí)現(xiàn)還是數(shù)組敌土，只是數(shù)組的每一項(xiàng)都是一條鏈镜硕。其中參數(shù)initialCapacity就代表了該數(shù)組的長(zhǎng)度。下面為HashMap構(gòu)造函數(shù)的源碼：

public HashMap(int initialCapacity, float loadFactor) {
    //初始容量不能<0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: "+ initialCapacity);
    //初始容量不能 > 最大容量值返干，HashMap的最大容量值為2^30
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //負(fù)載因子不能 < 0
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: "+ loadFactor);

    // 計(jì)算出大于 initialCapacity 的最小的 2 的 n 次方值兴枯。
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    
    this.loadFactor = loadFactor;
    //設(shè)置HashMap的容量極限，當(dāng)HashMap的容量達(dá)到該極限時(shí)就會(huì)進(jìn)行擴(kuò)容操作
    threshold = (int) (capacity * loadFactor);
    //初始化table數(shù)組
    table = new Entry[capacity];
    init();
}
  從源碼中可以看出矩欠，每次新建一個(gè)HashMap時(shí)财剖，都會(huì)初始化一個(gè)table數(shù)組。table數(shù)組的元素為Entry節(jié)點(diǎn)癌淮。
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    .......
}

其中Entry為HashMap的內(nèi)部類(lèi)躺坟，它包含了鍵key、值value乳蓄、下一個(gè)節(jié)點(diǎn)next咪橙，以及hash值，這是非常重要的虚倒，正是由于Entry才構(gòu)成了table數(shù)組的項(xiàng)為鏈表美侦。

上面簡(jiǎn)單分析了HashMap的數(shù)據(jù)結(jié)構(gòu)，下面將探討HashMap是如何實(shí)現(xiàn)快速存取的魂奥。

四菠剩、存儲(chǔ)實(shí)現(xiàn)：##

首先我們先看源碼

public V put(K key, V value) {  
//當(dāng)key為null，調(diào)用putForNullKey方法捧弃，保存null與table第一個(gè)位置中赠叼，這是HashMap允許為null的原因    
    if (key == null)    
        return putForNullKey(value);    
    //計(jì)算key的hash值  
    int hash = hash(key.hashCode());                    ------(1)  
    //計(jì)算key hash 值在 table 數(shù)組中的位置  
    int i = indexFor(hash, table.length);               ------(2)  
    //從i出開(kāi)始迭代 e,找到 key 保存的位置  
    for (Entry<K, V> e = table[i]; e != null; e =   e.next) {  
        Object k;  
        //判斷該條鏈上是否有hash值相同的(key相同)  
        //若存在相同擦囊，則直接覆蓋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;     //返回舊值  
        }  
    }  
    //修改次數(shù)增加1  
    modCount++;  
    //將key嘴办、value添加至i位置處  
    addEntry(hash, key, value, i);  
    return null;  
}  

通過(guò)源碼我們可以清晰看到HashMap保存數(shù)據(jù)的過(guò)程為：首先判斷key是否為null瞬场，若為null，則直接調(diào)用putForNullKey方法涧郊。若不為空則先計(jì)算key的hash值贯被，然后根據(jù)hash值搜索在table數(shù)組中的索引位置，如果table數(shù)組在該位置處有元素妆艘，則通過(guò)比較是否存在相同的key彤灶，若存在則覆蓋原來(lái)key的value，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）批旺。若table在該處沒(méi)有元素幌陕，則直接保存。這個(gè)過(guò)程看似比較簡(jiǎn)單汽煮，其實(shí)深有內(nèi)幕搏熄。有如下幾點(diǎn)：

1、 先看迭代處暇赤。此處迭代原因就是為了防止存在相同的key值心例，若發(fā)現(xiàn)兩個(gè)hash值（key）相同時(shí)，HashMap的處理方式是用新value替換舊value鞋囊，這里并沒(méi)有處理key止后，這就解釋了HashMap中沒(méi)有兩個(gè)相同的key。

2溜腐、 在看（1）译株、（2）處。這里是HashMap的精華所在挺益。首先是hash方法古戴，該方法為一個(gè)純粹的數(shù)學(xué)計(jì)算，就是計(jì)算h的hash值矩肩。

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

我們知道對(duì)于HashMap的table而言，數(shù)據(jù)分布需要均勻（最好每項(xiàng)都只有一個(gè)元素肃续，這樣就可以直接找到）黍檩，不能太緊也不能太松，太緊會(huì)導(dǎo)致查詢(xún)速度慢始锚，太松則浪費(fèi)空間刽酱。計(jì)算hash值后，怎么才能保證table元素分布均與呢瞧捌？我們會(huì)想到取模棵里，但是由于取模的消耗較大润文，HashMap是這樣處理的：調(diào)用indexFor方法。

static int indexFor(int h, int length) {
    return h & (length-1);
}

HashMap的底層數(shù)組長(zhǎng)度總是2的n次方殿怜，在構(gòu)造函數(shù)中存在：capacity <<= 1;這樣做總是能夠保證HashMap的底層數(shù)組長(zhǎng)度為2的n次方典蝌。當(dāng)length為2的n次方時(shí)，h&(length - 1)就相當(dāng)于對(duì)length取模头谜，而且速度比直接取目ハ疲快得多，這是HashMap在速度上的一個(gè)優(yōu)化柱告。至于為什么是2的n次方下面解釋截驮。

我們回到indexFor方法，該方法僅有一條語(yǔ)句：h&(length - 1)际度，這句話除了上面的取模運(yùn)算外還有一個(gè)非常重要的責(zé)任：均勻分布table數(shù)據(jù)和充分利用空間葵袭。