摘要：否則，如果中的節(jié)點(diǎn)太多，則會(huì)調(diào)整表的大小。應(yīng)該至少為，以避免調(diào)整大小和樹(shù)化閾值之間的沖突。
常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默認(rèn)初始容量 (必須是2的冪，用左移動(dòng))
static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量，如果隱式指定更高的值，則使用該容量(必須是2的冪且小于等于1 << 30)
static final float DEFAULT_LOAD_FACTOR = 0.75f;//加載因子(負(fù)載系數(shù))(用來(lái)衡量HashMap滿的程度)(默認(rèn)0.75f)
static final int TREEIFY_THRESHOLD = 8;//（鏈表轉(zhuǎn)樹(shù)的閾值）
static final int UNTREEIFY_THRESHOLD = 6;//（樹(shù)轉(zhuǎn)鏈表的閾值）
static final int MIN_TREEIFY_CAPACITY = 64;//容器可以樹(shù)化的最小容量。 （否則，如果bin中的節(jié)點(diǎn)太多，則會(huì)調(diào)整表的大小。）應(yīng)該至少為4 * TREEIFY_THRESHOLD，以避免調(diào)整大小和樹(shù)化閾值之間的沖突。
基本哈希bin節(jié)點(diǎn)Node
static class Node implements Map.Entry {
final int hash;//哈希值
final K key;//存儲(chǔ)鍵
V value;//存儲(chǔ)值
Node next;//下一個(gè)節(jié)點(diǎn)
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }//返回鍵值
public final V getValue() { return value; }//返回存儲(chǔ)值
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);//鍵值的hash與上存儲(chǔ)值的hash，Objects.hashCode()入?yún)閚ull返回0
}
public final V setValue(V newValue) {//設(shè)置值并返回舊值
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)//內(nèi)存地址相同直接返回true
return true;
if (o instanceof Map.Entry) {//如果是Entry 的子類
Map.Entry e = (Map.Entry)o;
if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))//調(diào)用當(dāng)前節(jié)點(diǎn)key值的equal方法和當(dāng)前節(jié)點(diǎn)value值的equal方法，結(jié)果與
return true;
}
return false;
}
}
靜態(tài)工具類（方法）
hash(Object key)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key的hash值和key的hash值的高16位做異或(>>>左邊高位補(bǔ)0)(任何數(shù)跟0異或都是其本身)(所以結(jié)果是：也就是高十六位+高十六位^低十六位)
}
范例
hash(-10)
-10.hashCode: 1111111111111111_1111111111110110
-10.hashCode>>>16: 0000000000000000_1111111111111111
return: 1111111111111111_0000000000001001
comparableClassFor 如果它的形式為“class C implements Comparable ”，則返回x的Class，否則返回null
static Class comparableClassFor(Object x) {
if (x instanceof Comparable) {//如果是比較器子類
Class c; Type[] ts, as; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;//如果是String返回String類
if ((ts = c.getGenericInterfaces()) != null) {//如果實(shí)現(xiàn)了接口
for (Type t : ts) {//循環(huán)實(shí)現(xiàn)的接口
if (
(t instanceof ParameterizedType) &&
((p = (ParameterizedType) t).getRawType() == Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 &&
as[0] == c
) // type arg is c
return c;
}
}
}
return null;//不是比價(jià)器子類
}
compareComparables() 如果x匹配kc（k的篩選可比類），則返回k.compareTo（x），否則返回0。
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
tableSizeFor 返回給定目標(biāo)容量的兩個(gè)大小的冪（返回能裝下傳入?yún)?shù)的大小，且為2的次方）
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);//Integer.numberOfLeadingZeros返回左邊開(kāi)會(huì)連續(xù)的0個(gè)數(shù)
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Integer.numberOfLeadingZeros()返回左邊最高位開(kāi)始0的個(gè)數(shù)
計(jì)算范例 tableSizeFor(5)
n = -1 >>> Integer.numberOfLeadingZeros(5-1)
-1: 11111111_11111111_11111111_11111111
5-1=4： 00000000_00000000_00000000_00000100
Integer.numberOfLeadingZeros(5-1):29
-1>>>29: 00000000_00000000_00000000_00000111
n=7
n>0
n
變量
transient Node[] table;//哈希桶數(shù)組(該表在首次使用時(shí)初始化)
transient Set> entrySet;//保持緩存的entrySet() AbstractMap字段用于keySet()和values()
transient int size;//此映射中包含的鍵 - 值映射的數(shù)量
transient int modCount;//此HashMap已被結(jié)構(gòu)修改的次數(shù)
int threshold;//下一次需要擴(kuò)容時(shí)的大?。╟apacity * load factor）（初值為0）
final float loadFactor;//哈希表的加載因子
構(gòu)造方法
HashMap()(默認(rèn)的負(fù)載因子是0.75f)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他屬性都是默認(rèn)的(DEFAULT_LOAD_FACTOR = 0.75f)
}
HashMap(int initialCapacity)(自定義容量)(通過(guò)tableSizeFor來(lái)計(jì)算2的次方的容量大小)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//(DEFAULT_LOAD_FACTOR = 0.75f)
}
HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)//容量小于0，拋出異常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//容量大于最大容量1 << 30
initialCapacity = MAXIMUM_CAPACITY;//則使用最大容量
if (loadFactor <= 0 || Float.isNaN(loadFactor))//如果負(fù)載因子小于0或者不是數(shù)字，拋出異常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;//賦值負(fù)載因子
this.threshold = tableSizeFor(initialCapacity);//計(jì)算容量，為2的冪
}
HashMap(Map m)根據(jù)一個(gè)map構(gòu)造一個(gè)map
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//默認(rèn)的負(fù)載因子
putMapEntries(m, false);
}
putMapEntries(Map m, boolean evict)實(shí)現(xiàn)Map.putAll和Map構(gòu)造函數(shù)
final void putMapEntries(Map m, boolean evict) {
int s = m.size();//獲取m映射數(shù)量
if (s > 0) {//長(zhǎng)度大于0
if (table == null) { //表是空的（沒(méi)有數(shù)據(jù)）
float ft = ((float)s / loadFactor) + 1.0F;//按照默認(rèn)負(fù)載因子比例計(jì)算出的大小+1
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);//小于最大容量就使用ft計(jì)算，大于最大容量使用最大容量計(jì)算
if (t > threshold)//如果超過(guò)擴(kuò)容閾值，那么就重新計(jì)算擴(kuò)容閾值
threshold = tableSizeFor(t);//重新計(jì)算擴(kuò)容閾值（2的冪）
}
else if (s > threshold)//如果表不是空的，且大小大于擴(kuò)容閾值
resize();//進(jìn)行擴(kuò)容
for (Map.Entry e : m.entrySet()) {//循環(huán)插入
K key = e.getKey();//獲取key
V value = e.getValue();//獲取value
putVal(hash(key), key, value, false, evict);
}
}
}
resize()擴(kuò)容
final Node[] resize() {
Node[] oldTab = table;//舊的表
int oldCap = (oldTab == null) ? 0 : oldTab.length;//不為空的話賦值為舊表數(shù)據(jù)量
int oldThr = threshold;//獲取擴(kuò)容的閾值
int newCap, newThr = 0;
if (oldCap > 0) {//如果舊表不為空
if (oldCap >= MAXIMUM_CAPACITY) {//如果舊表數(shù)據(jù)量大于最大容量
threshold = Integer.MAX_VALUE;//擴(kuò)容閾值設(shè)置成0x7fffffff（1111111111111111111111111111111）
return oldTab;//返回舊的數(shù)據(jù)表
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY&&oldCap >= DEFAULT_INITIAL_CAPACITY)//否則，兩倍大小小于最大容量，且舊的空間大于初始化空間
newThr = oldThr << 1; // 新的閾值為舊的閾值兩倍
}
else if (oldThr > 0) //舊表為空，且舊表閾值>0
newCap = oldThr;//初始容量被置于閾值
else { //舊表為空，且舊表閾值<0
newCap = DEFAULT_INITIAL_CAPACITY;//默認(rèn)的空間
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//默認(rèn)的閾值
}//if (oldCap > 0)結(jié)束
if (newThr == 0) {//如果新的閾值等于0
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;//重新賦值閾值
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {//有舊的數(shù)據(jù)
for (int j = 0; j < oldCap; ++j) {// 把每個(gè)哈希桶里的值都移動(dòng)到新的哈希桶中
Node e;
if ((e = oldTab[j]) != null) {//哈希桶位不為空
oldTab[j] = null;//原位置空
if (e.next == null)//如果這個(gè)桶位只有這一個(gè)元素（沒(méi)有next）
newTab[e.hash & (newCap - 1)] = e;//用新的長(zhǎng)度取模，數(shù)據(jù)放置位置
else if (e instanceof TreeNode)//如果是紅黑樹(shù)
((TreeNode)e).split(this, newTab, j, oldCap);
else { //如果是鏈表
Node loHead = null, loTail = null;//低位頭尾
Node hiHead = null, hiTail = null;//高位頭尾
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);//循環(huán)直至鏈表沒(méi)有下一個(gè)節(jié)點(diǎn)
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}//(e.next == null)的else結(jié)尾
}//if ((e = oldTab[j]) != null)結(jié)尾
}// for (int j = 0; j < oldCap; ++j)結(jié)尾
}//if (oldTab != null)結(jié)尾
return newTab;
}
putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) 放置值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)//如果桶是空的，或者桶的長(zhǎng)度是0
n = (tab = resize()).length;//擴(kuò)容
if ((p = tab[i = (n - 1) & hash]) == null)//取模桶位是空的
tab[i] = newNode(hash, key, value, null);//直接賦值
else {//存在長(zhǎng)鏈或紅黑樹(shù)
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//和鏈表的第一個(gè)值同值，進(jìn)行覆蓋
e = p;
else if (p instanceof TreeNode)//紅黑樹(shù)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {//binCount為下標(biāo)指針循環(huán)鏈表
if ((e = p.next) == null) {//循環(huán)到鏈表的末尾（next為空）
p.next = newNode(hash, key, value, null);//把插入的節(jié)點(diǎn)作為鏈表的末尾的下一個(gè)節(jié)點(diǎn)
if (binCount >= TREEIFY_THRESHOLD - 1) //如果達(dá)到樹(shù)化的閾值，那么轉(zhuǎn)化為樹(shù)
treeifyBin(tab, hash);
break;//結(jié)束循環(huán)
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//插入的節(jié)點(diǎn)和鏈表某一個(gè)節(jié)點(diǎn)相同，直接跳出
break;
p = e;//循環(huán)指針p移到下一位
}
}
if (e != null) { //已存在映射，覆蓋
V oldValue = e.value;//獲取舊值
if (!onlyIfAbsent || oldValue == null)
e.value = value;//賦值
afterNodeAccess(e);//后期回調(diào)操作
return oldValue;
}
}
++modCount;
if (++size > threshold)//是否達(dá)到擴(kuò)容閾值
resize();
afterNodeInsertion(evict);//后期回調(diào)操作
return null;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/74959.html
