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

主要成員變量

我們先來看以下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超過這個值時，將會調(diào)用doubleCapacity()方法擴(kuò)容
private transient int threshold;
//存儲數(shù)據(jù)的主要容器，一個HashMapEntry數(shù)組
transient HashMapEntry<K, V>[] table;
//分別是存儲key和value的集合
private transient Set<K> keySet;
private transient Collection<V> values;
//存儲Entry的集合
private transient Set<Entry<K, V>> entrySet;

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

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里一個變量hash用于存儲key的哈希值，還有一個next變量也是HashMapEntry類型，可見HashMapEntry是一個單鏈表結(jié)構(gòu)，每一個桶都可以存儲多個元素。

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

public HashMap(int capacity) {
        ...  //參數(shù)判斷和capacity為0時的空表創(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)建一個容量大小為capacity的數(shù)組
    }

makeTable方法中有如下代碼：
threshold = (newCapacity >> 1) + (newCapacity >> 2);
其中threshold表示HashMap擴(kuò)容的閥值，意思是在初始化時threshold等于總?cè)萘?0.75（加載因子），一旦HashMap中存儲的元素數(shù)量超過threshold，就會對整個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的過程使用了兩個for循環(huán)遍歷其中的元素，有一點(diǎn)復(fù)雜，我們先看HashMap的put方法，看看元素是如何存儲的。

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的對應(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時，調(diào)用擴(kuò)容的方法，得到一個新的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里相對應(yīng)的下標(biāo)index，然后針對table[index]進(jìn)行鏈表遍歷，通過比較hash值和equals方法查找桶內(nèi)是否存在相同的key，如果存在，則將新的value代替舊的存入，將舊的vaule返回；否則創(chuàng)建一個新的Entry，作為這個桶的頭節(jié)點(diǎn)，最后返回空值。其實(shí)doubleCapacity方法只是將oldTable的遍歷和newTable的定位及插入邏輯合并到了一起，原理跟put方法是十分類似的。

然后我們來看一下put方法的時間復(fù)雜度，該方法其實(shí)分為4個步驟，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)時間內(nèi)完成。我們之前了解到當(dāng)size超過總?cè)萘?0.75后，會進(jìn)行擴(kuò)容，所以大部分情況下(key的hash分布較為均勻)，每個桶中的元素個數(shù) <= 1，極少數(shù)情況 >=2，所以第三步也可以在O(1)內(nèi)完成，我們可以認(rèn)為其整體時間復(fù)雜度為O(1)。

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