HashMap源碼分析及沖突處理的細節

1.  首先看1下hashmap的數據結構，可以看到是數組加鏈表實現的。

transient Entry<K,V>[] table =(Entry<K,V>[]) EMPTY_TABLE;

可以看到它的實現是1個Entry<K,V>類型的名為table的數組。而Entry是HashMap中的1個內部類。

static class Entry<K,V> implementsMap.Entry<K,V> {

       final K key;

       V value;

       Entry<K,V> next;

       int hash;

       它有4個屬性，key，value，next，hash。由于有next屬性，所以自然會想到鏈表的結點類，事實上，當出現hash沖突時，由于HashMap使用鏈地址法來解決沖突。所以table數組的每個元素就會構成鏈表結構。所以可以說HashMap就是1個存儲鏈表的數組。

2.   HashMap的table數組的默許大小是16，并且大小永久是2的n次方。它還有1個負載因子，默許為0.75，可以通過帶參數的構造方法自己指定。負載因子loadFactor的作用是：HashMap中的實際的數據大小除以總容量(initialCapacity),當值到達loadFactor時，HashMap的總容量自動擴大1倍。

  staticfinal int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final float DEFAULT_LOAD_FACTOR = 0.75f;

   計算threshold，值為capacity *loadFactor。

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY +1);

   這里就會判斷，當size的值大于threshold（即capacity *loadFactor）時，就會進行擴容。

if ((size >= threshold) && (null != table[bucketIndex])){

            resize(2 * table.length);

3.接下來以put方法作為入口，進行分析。

1.首先進行hash運算，并求出將要存入的數組下標。

int hash = hash(key);

int i = indexFor(hash, table.length);

     接下來看看計算下標的算法是如何實現的。進入到indexFor方法中，實現的代碼以下：

static int indexFor(int h, int length) {

        // assertInteger.bitCount(length) == 1 : "length must be a non-zero power of2";

        return h &(length⑴);

    }

    具體是h &(length⑴)，這樣計算的值介于0和length⑴之間，有點類似于hash%length 的求模運算。之所以用&運算我認為是位運算的效力更高吧。

2.然后是下面這段代碼：

for (Entry<K,V> e = table[i]; e != null; e = e.next) {

            Object k;

            if (e.hash == hash&& ((k = e.key) == key || key.equals(k))) {

                V oldValue =e.value;

                e.value =value;

               e.recordAccess(this);

                returnoldValue;

            }

        }

        modCount++;

        addEntry(hash, key,value, i);

        會判斷table[i]是不是為null，這是會出現兩種情況，先分析第1種情況，即table[i]還沒有元素，是null的情況，這時候循環就沒有履行，繼續往下，去履行addEntry方法。addEntry方法中先進行判斷是不是需要擴容，如果需要，就進行擴容。然后又進入到createEntry方法中。它的代碼實現以下：

void createEntry(int hash, K key, V value, int bucketIndex) {

        Entry<K,V> e =table[bucketIndex];

        table[bucketIndex] =new Entry<>(hash, key, value, e);

        size++;

    }

        它做的工作就是把hash,key, value, e4個屬性組裝成1個Entry的對象e，并將它放在數組下標相應的位置，這時候如果加入的是第1個元素，e則為null,所以next指向了null。最后再把size加1.

        下面分析第2種情況，即即table[i]已有了元素，不是null的情況。這時候會履行上面的那1段for循環，這個循環的作用就是順次遍歷全部table[i]鏈表，并且判斷這個鏈表的每個元素的key是不是和新加進來的元素的key相同，如果相同新的value就會覆蓋舊的value，即保證HashMap中唯1的key有唯1的value.

         進行完了覆蓋的操作后，就會履行剩下的代碼，和第1種情況1樣，履行addEntry方法。addEntry方法中先進行判斷是不是需要擴容，如果需要，就進行擴容。再履行createEntry方法。這時候e = table[bucketIndex];計算出來的e就不為null了，為原來的i下標處的元素。然后又封裝1個新的Entry對象，放入到table[i]位置，它的next指向了e,即原來的table[i]處的元素。

        所以通過分析我們可以發現，最后放入的元素總是在這個沖突鏈表的表頭的位置。

        最后，可以看到，當出現沖突時，會把數據放入鏈表中，每次插入新的元素都會對全部鏈表進行遍歷操作，影響程序的效力。所以當我們向HasnMap中放入的key的數據類型是自定義類型的時候，要依照規范公道的實現hashcode和equals方法，盡可能避免沖突。另外，由于它的底層實現也是數組，所以也要盡可能避免擴容。最好能估算出初始的大小，而對負載因子，聽說0.75是計算出的最好值，所以還是用默許的吧。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈