摘要：前言系列文章目錄上一篇我們說明了的算法說到在構造時會自動將設為的整數次冪本篇我們就來聊聊的構造函數本文的源碼基于版本構造函數共有四個構造函數默認初始大小默認負載因子沒有指定時使用默認值即默認初始大小默認負載因子指定初始大小但使用默認負載因子
前言
系列文章目錄
上一篇我們說明了HashMap的hash算法, 說到HashMap在構造時會自動將table設為2的整數次冪.
本篇我們就來聊聊HashMap的構造函數.
本文的源碼基于 jdk8 版本.
構造函數
HashMap 共有四個構造函數
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
// 默認初始大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 默認負載因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final float loadFactor;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
transient Node[] table;
// 沒有指定時, 使用默認值
// 即默認初始大小16, 默認負載因子 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 指定初始大小, 但使用默認負載因子
// 注意這里其實是調用了另一個構造函數
public HashMap(int initialCapacity) {
this(initialCapacity, 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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// 利用已經存在的map創(chuàng)建HashMap
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
}
不知道大家發(fā)現(xiàn)了沒有, 即使我們在構造函數中指定了initialCapacity, 這個值也只被用來計算 threshold
this.threshold = tableSizeFor(initialCapacity);
而 threshold 這個值在初始化table時, 就代表了數組的初始大小, 這個我們到后面用到的時候講.
我們先來看看tableSizeFor函數干了什么事:
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
tableSizeFor這個方法用于找到大于等于initialCapacity的最小的2的冪, 這個算法還是很精妙的, 這里我稍微解釋一下:
我們知道, 當一個32位整數不為0時, 32bit中至少有一個位置為1, 上面5個移位操作的目的在于, 將 從最高位的1開始, 一直到最低位的所有bit 全部設為1, 最后再加1(注意, 一開始是先cap-1的), 則得到的數就是大于等于initialCapacity的最小的2的冪. 讀者自己找一個數算一下就明白了, 也可以參照這一篇博客.
最后我們來看最后一個構造函數, 它調用了 putMapEntries 方法:
final void putMapEntries(Map m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
我們知道, 當使用構造函數HashMap(Map m) 時, 我們并沒有為 table 賦值, 所以, table值一定為null, 我們先根據傳入Map的大小計算 threshold 值, 然后判斷需不需要擴容, 最后調用 putVal方法將傳入的Map插入table中.
resize 和 putVal 方法我們以后再細講.
總結
通過上面對四個構造函數的分析我們發(fā)現(xiàn), 除了最后一個構造函數, 其他三個函數:
HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
的調用中, 最多只牽涉到HashMap的兩個Field loadFactor, threshold, 而并不牽涉到 table 變量.
這說明HashMap中, table的初始化或者使用不是在構造函數中進行的, 而是在實際用到的時候, 事實上, 它是在HashMap擴容的時候實現(xiàn)的, 即resize函數, 我們在下一篇文章中討論.
(完)
下一篇: 深入理解HashMap(四): 關鍵源碼逐行分析之resize
查看更多系列文章：系列文章目錄
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76526.html
