HashMap涉及到的東西還真是挺多的.看了幾篇文章也算是個總結(jié)吧

前置知識

在分析HashMap之前先說一些基礎(chǔ)的知識.

HashCode

它是一個int類型的值由jdk根據(jù)對象計算得出.每個對象都會有這個值.這里涉及到和equals方法的關(guān)系.在Java中規(guī)定,如果equals()方法返回true,那么比較的hashCode必須是相等的.因此重寫equals方法必須要重寫hashCode方法.

Map的存儲結(jié)構(gòu)

Map的內(nèi)部有一個Entry類,,它是一個單鏈表,存放了key,value,以及下一個Entry.
Entry存儲在一個數(shù)組上,一個位置放一個單鏈表.

Map的存儲方式
通過key獲取vlaue的過程,首先通過key的hash值獲取到map數(shù)組存放的索引,然后再通過key的equals方法獲取對應(yīng)的值.

map的加載因子
默認為0.75 在hashMap中實際存儲量是數(shù)組的size * 0.75 也就是size為16實際存儲12以上元素的時候就會把數(shù)組尺寸擴大一倍為32.如果加載因子為1,那么數(shù)組上都會有鏈表.查詢會非常耗時.如果數(shù)值偏小,那么會浪費空間.
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

源碼分析

構(gòu)造函數(shù)

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);

        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

并沒有實際創(chuàng)建 一個Map,數(shù)組也沒有創(chuàng)建.真正的創(chuàng)建是在put方法里調(diào)用的inflateTable()

hash方法

final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

傳入的對象獲取hash值,然后進行異或運算.
h ^= (h >>> 20) ^ (h >>> 12);
h ^ (h >>> 7) ^ (h >>> 4);
為什么要經(jīng)過這樣的運算呢？這就是HashMap的高明之處。先看個例子，一個十進制數(shù)32768(二進制1000 0000 0000 0000)，經(jīng)過上述公式運算之后的結(jié)果是35080(二進制1000 1001 0000 1000)?？闯鰜砹藛?？或許這樣還看不出什么，再舉個數(shù)字61440(二進制1111 0000 0000 0000)，運算結(jié)果是65263(二進制1111 1110 1110 1111)，現(xiàn)在應(yīng)該很明顯了，它的目的是讓“1”變的均勻一點，散列的本意就是要盡量均勻分布。

那這樣有什么意義呢？
如果通過key獲取value值,需要經(jīng)過key的hash值來獲取到map存放數(shù)組的索引,h & (length-1)，這樣得到的結(jié)果就是一個比length小的正數(shù)，我們把這個值叫做index。其實這個index就是索引將要插入的值在數(shù)組中的位置.因此上面操作希望得到的索引更加的均勻.這樣每個數(shù)組上的都盡量平均覆蓋到單鏈表.

h&(length-1)為什么會比length小?
當(dāng) length 總是 2 的倍數(shù)時，h & (length-1) 將是一個非常巧妙的設(shè)計：假設(shè) h=5,length=16, 那么 h & length - 1 將得到 5；如果 h=6,length=16, 那么 h & length - 1 將得到 6 ……如果 h=15,length=16, 那么 h & length - 1 將得到 15；但是當(dāng) h=16 時 , length=16 時，那么 h & length - 1 將得到 0 了；當(dāng) h=17 時 , length=16 時，那么 h & length - 1 將得到 1 了……這樣保證計算得到的索引值總是位于 table 數(shù)組的索引之內(nèi)。

put方法

在看put源碼之前需hash方法作為支撐.現(xiàn)在再來看一下put方法

public V put(K key, V value) {
       if (table == EMPTY_TABLE) {
         //如果數(shù)組為空,則把數(shù)組擴容,擴容后的長度為2的n次方
           inflateTable(threshold);
       }
      //如果key為null,那么存放的位置是數(shù)組索引為0的位置
       if (key == null)
           return putForNullKey(value);
       //獲取hash值
       int hash = hash(key);
       //獲取索引
       int i = indexFor(hash, table.length);
      //遍歷單鏈表,如果key的equals返回true則覆蓋老的oldValue
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
       //如果重寫了equals方法,不重寫hashCode此時就會有問題了.
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }
     //修改了map的結(jié)構(gòu)
       modCount++;
     //新增一個Entry
       addEntry(hash, key, value, i);
       return null;
   }

addEntry方法

這個方法主要是判斷新增的Entry類是否會導(dǎo)致Map的尺寸.如果超過就將數(shù)組的長度擴展為當(dāng)前的兩倍.

void addEntry(int hash, K key, V value, int bucketIndex) {
//size代表在這個map中包含鍵值對映射數(shù)量.
//如果新增Entry類size是否大于閥值(默認是12),指定索引的數(shù)組是不為空,
        if ((size >= threshold) && (null != table[bucketIndex])) {
//map尺寸增加當(dāng)前table長度兩倍
//閥值是32*0.75
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

createEntry方法

新建一個Entry在單鏈表的頭部.next指向下一個Entry對象

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
      //新的Entry指向當(dāng)前存放的鏈表的頭部
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

resize方法

Map當(dāng)中設(shè)置map的最大尺寸
static final int MAXIMUM_CAPACITY = 1 << 30; 2的三十次方.
當(dāng)指定的超過這個數(shù)時也Map的size也不會增加了.
此時閥值會變成int最大值,也就是2的三十一次方.
這部分我很疑惑,既然達到了2的三十次方不會再次增加了,那么閥值也就沒有存在的意義了吧.何必還要符合規(guī)則是當(dāng)前的兩倍呢.設(shè)置為MAXIMUM_CAPACITY +1即可

 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
//如果是最大的尺寸,那么不會增加尺寸了,
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        //原來的Entry放到新的數(shù)組中,所以hash值要重新計算.
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

以上基本是一個put的過程.取也類似.