Java7 HashMap详解
文章推薦
- 精選java等全套學習資源
- 精選java電子圖書資源
- 精選大數據學習資源
- java項目練習精選
HashMap 是最簡單的，一來我們非常熟悉，二來就是它不支持并發操作，所以源碼也非常簡單。
首先，我們用下面這張圖來介紹 HashMap 的結構。
這個僅僅是示意圖，因為沒有考慮到數組要擴容的情況，具體的后面再說。
-
大方向上，HashMap 里面是一個數組，然后數組中每個元素是一個單向鏈表。
-
上圖中，每個綠色的實體是嵌套類 Entry 的實例，Entry 包含四個屬性：key, value, hash 值和用于單向鏈表的 next。
-
capacity：當前數組容量，始終保持 2^n，可以擴容，擴容后數組大小為當前的 2 倍。
-
loadFactor：負載因子，默認為 0.75。
-
threshold：擴容的閾值，等于 capacity * loadFactor
##put 過程分析
還是比較簡單的，跟著代碼走一遍吧。
public V put(K key, V value) {// 當插入第一個元素的時候，需要先初始化數組大小if (table == EMPTY_TABLE) {inflateTable(threshold);}// 如果 key 為 null，感興趣的可以往里看，最終會將這個 entry 放到 table[0] 中if (key == null)return putForNullKey(value);// 1. 求 key 的 hash 值int hash = hash(key);// 2. 找到對應的數組下標int i = indexFor(hash, table.length);// 3. 遍歷一下對應下標處的鏈表，看是否有重復的 key 已經存在，// 如果有，直接覆蓋，put 方法返回舊值就結束了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);return oldValue;}}modCount++;// 4. 不存在重復的 key，將此 entry 添加到鏈表中，細節后面說addEntry(hash, key, value, i);return null; }##數組初始化
在第一個元素插入 HashMap 的時候做一次數組的初始化，就是先確定初始的數組大小，并計算數組擴容的閾值。
private void inflateTable(int toSize) {// 保證數組大小一定是 2 的 n 次方。// 比如這樣初始化：new HashMap(20)，那么處理成初始數組大小是 32int capacity = roundUpToPowerOf2(toSize);// 計算擴容閾值：capacity * loadFactorthreshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);// 算是初始化數組吧table = new Entry[capacity];initHashSeedAsNeeded(capacity); //ignore }這里有一個將數組大小保持為 2 的 n 次方的做法，Java7 和 Java8 的 HashMap 和 ConcurrentHashMap 都有相應的要求，只不過實現的代碼稍微有些不同，后面再看到的時候就知道了。
##計算具體數組位置
這個簡單，我們自己也能 YY 一個：使用 key 的 hash 值對數組長度進行取模就可以了。
static int indexFor(int hash, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return hash & (length-1); }這個方法很簡單，簡單說就是取 hash 值的低 n 位。如在數組長度為 32 的時候，其實取的就是 key 的 hash 值的低 5 位，作為它在數組中的下標位置。
##添加節點到鏈表中
找到數組下標后，會先進行 key 判重，如果沒有重復，就準備將新值放入到鏈表的表頭。
void addEntry(int hash, K key, V value, int bucketIndex) {// 如果當前 HashMap 大小已經達到了閾值，并且新值要插入的數組位置已經有元素了，那么要擴容if ((size >= threshold) && (null != table[bucketIndex])) {// 擴容，后面會介紹一下resize(2 * table.length);// 擴容以后，重新計算 hash 值hash = (null != key) ? hash(key) : 0;// 重新計算擴容后的新的下標bucketIndex = indexFor(hash, table.length);}// 往下看createEntry(hash, key, value, bucketIndex); } // 這個很簡單，其實就是將新值放到鏈表的表頭，然后 size++ 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++; }這個方法的主要邏輯就是先判斷是否需要擴容，需要的話先擴容，然后再將這個新的數據插入到擴容后的數組的相應位置處的鏈表的表頭。
##數組擴容
前面我們看到，在插入新值的時候，如果當前的 size 已經達到了閾值，并且要插入的數組位置上已經有元素，那么就會觸發擴容，擴容后，數組大小為原來的 2 倍。
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];// 將原來數組中的值遷移到新的更大的數組中transfer(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }擴容就是用一個新的大數組替換原來的小數組，并將原來數組中的值遷移到新的數組中。
由于是雙倍擴容，遷移過程中，會將原來 table[i] 中的鏈表的所有節點，分拆到新的數組的 newTable[i] 和 newTable[i + oldLength] 位置上。如原來數組長度是 16，那么擴容后，原來 table[0] 處的鏈表中的所有元素會被分配到新數組中 newTable[0] 和 newTable[16] 這兩個位置。代碼比較簡單，這里就不展開了。
##get 過程分析
相對于 put 過程，get 過程是非常簡單的。
- 根據 key 計算 hash 值。
- 找到相應的數組下標：hash & (length - 1)。
- 遍歷該數組位置處的鏈表，直到找到相等(==或equals)的 key。
getEntry(key):
final Entry<K,V> getEntry(Object key) {if (size == 0) {return null;}int hash = (key == null) ? 0 : hash(key);// 確定數組下標，然后從頭開始遍歷鏈表，直到找到為止for (Entry<K,V> 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; }出處：https://www.javadoop.com/post/hashmap#Java7%20HashMap
總結
以上是生活随笔為你收集整理的Java7 HashMap详解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： LinkedList详解，看这篇就够了
- 下一篇： Java7 ConcurrentHash