摘要:關于不安全的問題,感興趣的可以去看一下這篇文章老生常談,的死循環。
廢話不多說,直接進入主題:
首先我們從構造方法開始:public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } 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); // 初始化加載因子(默認0.75f) this.loadFactor = loadFactor; // 初始化容器大小(默認16) threshold = initialCapacity; init(); } // 可以看到jdk1.7中hashMap的init方法并沒有創建hashMap的數組和Entry, // 而是移到了put方法里,后邊會講到 void init() { }最常用的put方法:
public V put(K key, V value) { // 可以看到,初始化table是在首次put時開始的 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 對key為`null`的處理,進入到方法里可以看到直接將其hash置為0,并插入到了數組下標為0的位置 if (key == null) return putForNullKey(value); // 計算hash值 int hash = hash(key); // 根據hash,查找到數組對應的下標 int i = indexFor(hash, table.length); // 遍歷數組第i個位置的鏈表 for (Entry根據put方法的流程,我們進入到inflateTable方法看一下他的初始化代碼:e = table[i]; e != null; e = e.next) { Object k; // 找到相同的key,并覆蓋其value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // 在table[i]下的鏈表中沒有找到相同的key,將entry加入到此鏈表 // addEntry方法后邊會再看一下 addEntry(hash, key, value, i); return null; }
// 容量一定為2的n次方,比如設置size=10,則容量則為大于10的且為2的n次方=16 // Find a power of 2 >= toSize int capacity = roundUpToPowerOf2(toSize); // 計算擴容臨界值:capacity * loadFactor,當size>=threshold時,觸發擴容 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 初始化Entry數組 table = new Entry[capacity]; initHashSeedAsNeeded(capacity);addEntry添加鏈表節點
能進入到addEntry方法,說明根據hash值計算出的數組下標沖突,但是key不一樣
void addEntry(int hash, K key, V value, int bucketIndex) { // 當數組的size >= 擴容閾值,觸發擴容,size大小會在createEnty和removeEntry的時候改變 if ((size >= threshold) && (null != table[bucketIndex])) { // 擴容到2倍大小,后邊會跟進這個方法 resize(2 * table.length); // 擴容后重新計算hash和index hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } // 創建一個新的鏈表節點,點進去可以了解到是將新節點添加到了鏈表的頭部 createEntry(hash, key, value, bucketIndex); }resize擴容
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 創建2倍大小的新數組 Entry[] newTable = new Entry[newCapacity]; // 將舊數組的鏈表轉移到新數組,就是這個方法導致的hashMap不安全,等下我們進去看一眼 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; // 重新計算擴容閾值(容量*加載因子) threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }get方法
對于put方法,get方法就很簡單了
public V get(Object key) { if (key == null) return getForNullKey(); Entry不安全的transfer方法entry = getEntry(key); return null == entry ? null : entry.getValue(); } final Entry getEntry(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); // 根據hash值找到對應的數組下標,并遍歷其E for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; // 遍歷舊數組 for (Entry這里粗略的講一下為什么transfer是不安全的e : table) { // 遍歷鏈表 while(null != e) { Entry next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 計算節點在新數組中的下標 int i = indexFor(e.hash, newCapacity); // 將舊節點插入到新節點的頭部 e.next = newTable[i]; newTable[i] = e; e = next; } } }
從上面的代碼可以看出,從oldTable中遍歷Entry是正序的,也就是a->b->c的順序,而插入到新數組的時候是采用的頭插法,也就是后插入的在首部,所以遍歷之后結果為c->b->a;
此時正常邏輯是沒有問題的,而當有多個線程同時進行擴容操作時就出現問題了,看下邊的圖
此時的狀態為a線程創建了新數組,b線程也創建了新數組,同時b的cpu時間片用完進入等待階段,
此時的狀態為a線程完成了數組的擴容,退出了transfer方法,但是還沒有執行下一句table = newTable;
b線程回來繼續執行代碼
Entrynext = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next;
結果如下:
b會繼續執行循環代碼,進入到死循環狀態。
關于transfer不安全的問題,感興趣的可以去看一下這篇文章老生常談,HashMap的死循環。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/75295.html
摘要:下面我來簡單總結一下的核心要點底層結構是散列表數組鏈表紅黑樹,這一點和是一樣的。是將所有的方法進行同步,效率低下。而作為一個高并發的容器,它是通過部分鎖定算法來進行實現線程安全的。 前言 聲明,本文用的是jdk1.8 前面章節回顧: Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹 HashMap就是這么簡單【源碼剖析】 LinkedHas...
摘要:值得位數有的次方,如果直接拿散列值作為下標訪問主數組的話,只要算法比較均勻,一般是很難出現碰撞的。但是內存裝不下這么大的數組,所以計算數組下標就采取了一種折中的辦法,就是將得到的散列值與數組長度做一個與操作。 hashMap簡單介紹 hashMap是面試中的高頻考點,或許日常工作中我們只需把hashMap給new出來,調用put和get方法就完了。但是hashMap給我們提供了一個絕佳...
摘要:注意排版不需要花花綠綠的,盡量使用語法。協議的長連接和短連接,實質上是協議的長連接和短連接。長連接短連接究竟是什么三次握手和四次揮手面試常客為了準確無誤地把數據送達目標處,協議采用了三次握手策略。 一 簡歷該如何寫 1.1 為什么說簡歷很重要?1.2-這3點你必須知道1.3-兩大法則了解一1.4-項目經歷怎么寫?1.5-專業技能該怎么寫?1.6-開源程序員簡歷模板分享1.7 其他的一些...
閱讀 3674·2021-11-23 09:51
閱讀 1036·2021-11-19 11:30
閱讀 3360·2019-08-29 14:16
閱讀 3370·2019-08-29 12:12
閱讀 2363·2019-08-26 13:40
閱讀 3471·2019-08-26 12:21
閱讀 3073·2019-08-26 11:55
閱讀 2221·2019-08-26 11:35