1.構(gòu)造函數(shù)
//默認(rèn)size=16，默認(rèn)負(fù)載因子0.75
1.1?
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;// all other fields defaulted
}
1.2
//map容量，負(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);
}
/**
* Returns a power of two size for the given target capacity.
* 為了控制hashmap的容量一定是2的n次方
* 通過位移運算弃秆，找到大于或等于 cap 的 最小2的n次冪饲宛。位運算的速度要優(yōu)于乘除加減
*/
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;
}
2.put數(shù)據(jù)
2.1?
public V put(K key, V value) {
return putVal(hash(key), key, value,false,true);
}
2.2
static final int hash(Object key) {
int h;
// h >>> 16 為了讓高位參與運算泼橘，使得更均勻
// (h = key.hashCode()) ^ (h >>> 16)
// 先計算key的hash值择份，然后再用哈希值與自己右移16位做異或運算
// 使用異或 ^運算符 使得運算結(jié)果更有隨機性蘸嘶，異或運算只有不同才是1
// PS:因為或運算履植，值會更偏向于1计雌，與運算，值會更偏向于0
? ? return (key ==null) ?0 : (h = key.hashCode()) ^ (h >>>16);
}
2.3
final V putVal(int hash, K key, V value,boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p;int n, i;
//第一次put數(shù)據(jù)的時候玫霎，hashmap才會初始化凿滤，并不是在構(gòu)造函數(shù)中
? ? if ((tab = table) ==null || (n = tab.length) ==0)
n = (tab = resize()).length;
//由于容量是2的n次方妈橄，所以 (n - 1) & hash 其實等同于 n % hash
//而且這樣運算的效率會更高
? ? if ((p = tab[i = (n -1) & hash]) ==null)
tab[i] = newNode(hash, key, value,null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key !=null && key.equals(k))))
e = p;
else if (pinstanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount =0; ; ++binCount) {
if ((e = p.next) ==null) {
p.next = newNode(hash, key, value,null);
if (binCount >= TREEIFY_THRESHOLD -1)// -1 for 1st
? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key !=null && key.equals(k))))
break;
p = e;
}
}
if (e !=null) {// existing mapping for key
? ? ? ? ? ? V oldValue = e.value;
if (!onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2.4
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab ==null) ?0 : oldTab.length;
//舊的擴容閾值
? ? int oldThr = threshold;
//新的容量和擴容閾值
? ? int newCap, newThr =0;
//說明已經(jīng)是舊的hashmap可進(jìn)行resize
? ? if (oldCap >0) {
//hashmap >=最大容量
? ? ? ? if (oldCap >= MAXIMUM_CAPACITY) {
//擴容閾值=Integer.max
? ? ? ? ? ? threshold = Integer.MAX_VALUE;
return oldTab;
}
//容量擴容1倍 后小于最大容量 且? 老容量 >= 初始容量
//為什么擴容一倍大小呢？
//擴容一倍大小的原因是
// （1）為了保證hash 到數(shù)組位置的效率
// （2）關(guān)系到擴容后元素在newCap中的放置問題：
? ? ? ? else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//擴容閾值也擴大1倍
? ? ? ? ? ? newThr = oldThr <<1;// double threshold
? ? }
else if (oldThr >0)// initial capacity was placed in threshold
? ? ? ? newCap = oldThr;
else {
// zero initial threshold signifies using defaults
// 如果是new 了一個新的hashmap的時候翁脆，會走這一行眷蚓，初始化容量和擴容閾值
? ? ? ? newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//1.第一次初始化的時候不是0了已經(jīng)
? ? if (newThr ==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;
//如果不是初始化進(jìn)來的
? ? if (oldTab !=null) {
//要遍歷所有的節(jié)點
? ? ? ? for (int j =0; j < oldCap; ++j) {
Node e;
//節(jié)點為null就continue 不為空的時候，把節(jié)點給臨時節(jié)點e
? ? ? ? ? ? if ((e = oldTab[j]) !=null) {
//把老結(jié)點 置為null
? ? ? ? ? ? ? ? oldTab[j] =null;
//如果該結(jié)點沒有next反番，也就是沒有發(fā)生過沖突沙热，桶的位置只有一個元素，把節(jié)點放入新的table中
? ? ? ? ? ? ? ? if (e.next ==null)
//就把值直接扔到對應(yīng)的位置罢缸。這里有個問題篙贸，沒有發(fā)生過沖突的，就直接放進(jìn)去了枫疆，擴容后也不會發(fā)生沖突嗎
// 爵川，感覺這個很nb啊
? ? ? ? ? ? ? ? ? ? newTab[e.hash & (newCap -1)] = e;
//如果節(jié)點發(fā)生過沖突，并且是紅黑樹的數(shù)據(jù)結(jié)構(gòu)
? ? ? ? ? ? ? ? else if (einstanceof TreeNode)
//說明沖突的個數(shù)大于8個息楔，那么就把樹切割開
? ? ? ? ? ? ? ? ? ? ((TreeNode)e).split(this, newTab, j, oldCap);
else {// preserve order
? ? ? ? ? ? ? ? ? ? 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);
if (loTail !=null) {
loTail.next =null;
newTab[j] = loHead;
}
if (hiTail !=null) {
hiTail.next =null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
