java HashMap相關


java中HashMap是使用最多的數據結構之一,也是面試java基礎必問的問題之一。它有以下特性:

(1) 一般情況下查找的時間為O(1),特殊情況下為O(n) (jdk7)

(2) 存儲鍵值對(鍵是唯一的)

(3) 不支持並發


一、數據結構


為瞭實現特性(1),HashMap使用瞭由數組和鏈表組成的hash表,這樣在查找的時候根據key的hashCode值找到對應的桶(數組所在的下標),然後遍歷桶找到對應的元素(key的equals())




當HashMap中的元素到達一定數量時,為瞭滿足條件(1),需要進行擴容。為瞭明確擴容的條件,引入瞭裝載因子(loadFactor),當size > capacity * loadFactor時進行擴容(resize)。但這解決不瞭HashMap最壞情況下查找變為O(n),當元素key的hashCode都相同,插入的數據就都在同一個桶裡面,此時HashMap退化為LinkList,在自定義對象的時候應該註意hashCode的定義。


二、循環鏈表


HashMap中的元素個數大於規定的閾值時,就會進行擴容,重新hash,並分配到相應的桶


    Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;

在單線程情況下重新resize分配的過程如下:




在多線程情況下,resize過程容易出現環,下面就上圖例子說明多線程情況下環形成的過程。

場景:兩個線程同執行HashMap擴容操作

條件:當Thread1線程執行到上面代碼片的第一行,cpu被另Thread2線程占用且執行完擴容操作,此時Thread1看到的HashMap數據結構為下圖所示,接著Thread1繼續執行擴容操作



結果:Thread1執行完畢,形成瞭如下圖所示的環

0 個評論

要回覆文章請先登錄註冊