摘要：前言系列文章目錄上一篇我們說(shuō)明了的算法說(shuō)到在構(gòu)造時(shí)會(huì)自動(dòng)將設(shè)為的整數(shù)次冪本篇我們就來(lái)聊聊的構(gòu)造函數(shù)本文的源碼基于版本構(gòu)造函數(shù)共有四個(gè)構(gòu)造函數(shù)默認(rèn)初始大小默認(rèn)負(fù)載因子沒(méi)有指定時(shí)使用默認(rèn)值即默認(rèn)初始大小默認(rèn)負(fù)載因子指定初始大小但使用默認(rèn)負(fù)載因子
前言
系列文章目錄
上一篇我們說(shuō)明了HashMap的hash算法, 說(shuō)到HashMap在構(gòu)造時(shí)會(huì)自動(dòng)將table設(shè)為2的整數(shù)次冪.
本篇我們就來(lái)聊聊HashMap的構(gòu)造函數(shù).
本文的源碼基于 jdk8 版本.
構(gòu)造函數(shù)
HashMap 共有四個(gè)構(gòu)造函數(shù)
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
// 默認(rèn)初始大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 默認(rèn)負(fù)載因子 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;
// 沒(méi)有指定時(shí), 使用默認(rèn)值
// 即默認(rèn)初始大小16, 默認(rèn)負(fù)載因子 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 指定初始大小, 但使用默認(rèn)負(fù)載因子
// 注意這里其實(shí)是調(diào)用了另一個(gè)構(gòu)造函數(shù)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 指定初始大小和負(fù)載因子
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);
}
// 利用已經(jīng)存在的map創(chuàng)建HashMap
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
}
不知道大家發(fā)現(xiàn)了沒(méi)有, 即使我們?cè)跇?gòu)造函數(shù)中指定了initialCapacity, 這個(gè)值也只被用來(lái)計(jì)算 threshold
this.threshold = tableSizeFor(initialCapacity);
而 threshold 這個(gè)值在初始化table時(shí), 就代表了數(shù)組的初始大小, 這個(gè)我們到后面用到的時(shí)候講.
我們先來(lái)看看tableSizeFor函數(shù)干了什么事:
/**
* 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這個(gè)方法用于找到大于等于initialCapacity的最小的2的冪, 這個(gè)算法還是很精妙的, 這里我稍微解釋一下:
我們知道, 當(dāng)一個(gè)32位整數(shù)不為0時(shí), 32bit中至少有一個(gè)位置為1, 上面5個(gè)移位操作的目的在于, 將 從最高位的1開(kāi)始, 一直到最低位的所有bit 全部設(shè)為1, 最后再加1(注意, 一開(kāi)始是先cap-1的), 則得到的數(shù)就是大于等于initialCapacity的最小的2的冪. 讀者自己找一個(gè)數(shù)算一下就明白了, 也可以參照這一篇博客.
最后我們來(lái)看最后一個(gè)構(gòu)造函數(shù), 它調(diào)用了 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);
}
}
}
我們知道, 當(dāng)使用構(gòu)造函數(shù)HashMap(Map m) 時(shí), 我們并沒(méi)有為 table 賦值, 所以, table值一定為null, 我們先根據(jù)傳入Map的大小計(jì)算 threshold 值, 然后判斷需不需要擴(kuò)容, 最后調(diào)用 putVal方法將傳入的Map插入table中.
resize 和 putVal 方法我們以后再細(xì)講.
總結(jié)
通過(guò)上面對(duì)四個(gè)構(gòu)造函數(shù)的分析我們發(fā)現(xiàn), 除了最后一個(gè)構(gòu)造函數(shù), 其他三個(gè)函數(shù):
HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
的調(diào)用中, 最多只牽涉到HashMap的兩個(gè)Field loadFactor, threshold, 而并不牽涉到 table 變量.
這說(shuō)明HashMap中, table的初始化或者使用不是在構(gòu)造函數(shù)中進(jìn)行的, 而是在實(shí)際用到的時(shí)候, 事實(shí)上, 它是在HashMap擴(kuò)容的時(shí)候?qū)崿F(xiàn)的, 即resize函數(shù), 我們?cè)谙乱黄恼轮杏懻?
(完)
下一篇: 深入理解HashMap(四): 關(guān)鍵源碼逐行分析之resize
查看更多系列文章：系列文章目錄
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76526.html
