說到HashMap相信大家并不陌生补胚，這是一個(gè)非常常用的以鍵值對(duì)形式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)甩骏，但是對(duì)其內(nèi)部原理可能不是很了解纺弊，它的內(nèi)部是以什么形式存儲(chǔ)的卧波，它的存取的性能號(hào)稱能達(dá)到O(1)又是如何實(shí)現(xiàn)的，我們從源碼來做個(gè)簡要的分析赃蛛。

主要成員變量

我們先來看以下HashMap主要有哪些成員變量

//最小值
private static final int MINIMUM_CAPACITY = 4;
//最大值恃锉，2的30次方
private static final int MAXIMUM_CAPACITY = 1 << 30;
//加載因子
static final float DEFAULT_LOAD_FACTOR = .75F;
//大小
transient int size;
//獨(dú)立的entry，專用用來處理key為null的情況
transient HashMapEntry<K, V> entryForNullKey;
//加載的閥值呕臂，當(dāng)size超過這個(gè)值時(shí)破托，將會(huì)調(diào)用doubleCapacity()方法擴(kuò)容
private transient int threshold;
//存儲(chǔ)數(shù)據(jù)的主要容器，一個(gè)HashMapEntry數(shù)組
transient HashMapEntry<K, V>[] table;
//分別是存儲(chǔ)key和value的集合
private transient Set<K> keySet;
private transient Collection<V> values;
//存儲(chǔ)Entry的集合
private transient Set<Entry<K, V>> entrySet;

可以看到存儲(chǔ)數(shù)據(jù)的主要容器是一個(gè)數(shù)組歧蒋，而HashMapEntry是我們循環(huán)遍歷HashMap時(shí)的Entry的子類土砂，下面我們看一下這個(gè)類

static class HashMapEntry<K, V> implements Entry<K, V> {
        final K key;
        V value;
        final int hash;
        HashMapEntry<K, V> next;

        HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
            ...
        }
        ...
    }

table中的元素類型HashMapEntry，我們稱之為桶疏尿，HashMapEntry里一個(gè)變量hash用于存儲(chǔ)key的哈希值瘟芝，還有一個(gè)next變量也是HashMapEntry類型，可見HashMapEntry是一個(gè)單鏈表結(jié)構(gòu)褥琐，每一個(gè)桶都可以存儲(chǔ)多個(gè)元素锌俱。

下面是HashMap的主要構(gòu)造函數(shù)

public HashMap(int capacity) {
        ...  //參數(shù)判斷和capacity為0時(shí)的空表創(chuàng)建

        //將capacity控制在既定的范圍內(nèi)并保證capacity為偶數(shù)
        if (capacity < MINIMUM_CAPACITY) {
            capacity = MINIMUM_CAPACITY;
        } else if (capacity > MAXIMUM_CAPACITY) {
            capacity = MAXIMUM_CAPACITY;
        } else {
            capacity = Collections.roundUpToPowerOfTwo(capacity);
        }
        makeTable(capacity);  //創(chuàng)建一個(gè)容量大小為capacity的數(shù)組
    }

makeTable方法中有如下代碼：
threshold = (newCapacity >> 1) + (newCapacity >> 2);
其中threshold表示HashMap擴(kuò)容的閥值，意思是在初始化時(shí)threshold等于總?cè)萘?0.75（加載因子）敌呈，一旦HashMap中存儲(chǔ)的元素?cái)?shù)量超過threshold贸宏，就會(huì)對(duì)整個(gè)HashMap就行擴(kuò)容造寝。

擴(kuò)容的方法如下

private HashMapEntry<K, V>[] doubleCapacity() {
        HashMapEntry<K, V>[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            return oldTable;  //如果舊數(shù)組的容量已經(jīng)達(dá)到最大值，則直接返回
        }
        int newCapacity = oldCapacity * 2;  //將容量大小增加到以前的兩倍
        HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
        if (size == 0) {  //如果當(dāng)前大小為空吭练，則直接返回新數(shù)組
            return newTable;
        }

        //把oldTable中的元素重新整理到newTable中
        for (int j = 0; j < oldCapacity; j++) {
            /*
             * Rehash the bucket using the minimum number of field writes.
             * This is the most subtle and delicate code in the class.
             */
            HashMapEntry<K, V> e = oldTable[j];
            if (e == null) {
                continue;
            }
            int highBit = e.hash & oldCapacity;
            HashMapEntry<K, V> broken = null;
            newTable[j | highBit] = e;
            for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
                int nextHighBit = n.hash & oldCapacity;
                if (nextHighBit != highBit) {
                    if (broken == null)
                        newTable[j | nextHighBit] = n;
                    else
                        broken.next = n;
                    broken = e;
                    highBit = nextHighBit;
                }
            }
            if (broken != null)
                broken.next = null;
        }
        return newTable;
    }

在重新組裝table的過程使用了兩個(gè)for循環(huán)遍歷其中的元素诫龙，有一點(diǎn)復(fù)雜，我們先看HashMap的put方法鲫咽，看看元素是如何存儲(chǔ)的签赃。

put方法

public V put(K key, V value) {
        if (key == null) {  //先處理空值情況
            return putValueForNullKey(value);
        }

        int hash = Collections.secondaryHash(key);  //計(jì)算出key的hash值
        HashMapEntry<K, V>[] tab = table;
        int index = hash & (tab.length - 1);  //計(jì)算出key的對(duì)應(yīng)桶的下標(biāo)
        for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                preModify(e);
                V oldValue = e.value;
                e.value = value;
                return oldValue;  //key存在的情況下，直接更新value
            }
        }

        // No entry for (non-null) key is present; create one
        modCount++;
        if (size++ > threshold) {
            tab = doubleCapacity();  //size大于threshold時(shí)分尸，調(diào)用擴(kuò)容的方法锦聊，得到一個(gè)新的table
            index = hash & (tab.length - 1);
        }
        addNewEntry(key, value, hash, index);  //將新的桶更新到table中
        return null;
    }

put方法中，先計(jì)算出key的hash值箩绍，然后通過和table數(shù)組的最大index進(jìn)行&操作孔庭，得到key在table里相對(duì)應(yīng)的下標(biāo)index，然后針對(duì)table[index]進(jìn)行鏈表遍歷材蛛，通過比較hash值和equals方法查找桶內(nèi)是否存在相同的key圆到，如果存在，則將新的value代替舊的存入卑吭，將舊的vaule返回芽淡；否則創(chuàng)建一個(gè)新的Entry，作為這個(gè)桶的頭節(jié)點(diǎn)陨簇，最后返回空值吐绵。其實(shí)doubleCapacity方法只是將oldTable的遍歷和newTable的定位及插入邏輯合并到了一起，原理跟put方法是十分類似的河绽。

然后我們來看一下put方法的時(shí)間復(fù)雜度，該方法其實(shí)分為4個(gè)步驟唉窃，1.根據(jù)key計(jì)算出其hash值耙饰，并計(jì)算得到相應(yīng)桶的下標(biāo)index。2.查找table中index下標(biāo)的Entry纹份。3.遍歷Entry為頭節(jié)點(diǎn)的鏈表得到我們要找的Entry苟跪。4.取出Entry的value。
其中1蔓涧、2件已、4步都能在O(1)時(shí)間內(nèi)完成。我們之前了解到當(dāng)size超過總?cè)萘?0.75后元暴，會(huì)進(jìn)行擴(kuò)容篷扩，所以大部分情況下(key的hash分布較為均勻)，每個(gè)桶中的元素個(gè)數(shù) <= 1茉盏，極少數(shù)情況 >=2鉴未，所以第三步也可以在O(1)內(nèi)完成枢冤，我們可以認(rèn)為其整體時(shí)間復(fù)雜度為O(1)。

get方法的邏輯跟put基本一樣铜秆，有興趣可以自行了解一下淹真。