1.构造函数
//默认size=16，默认负载因子0.75
1.1
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;// all other fields defaulted
}
1.2
//map容量，负载因子
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次幂。位运算的速度要优于乘除加减
*/
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数据
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位做异或运算
// 使用异或 ^运算符 使得运算结果更有随机性，异或运算只有不同才是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数据的时候，hashmap才会初始化，并不是在构造函数中
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;
//说明已经是旧的hashmap可进行resize
if (oldCap >0) {
//hashmap >=最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
//扩容阈值=Integer.max
threshold = Integer.MAX_VALUE;
return oldTab;
}
//容量扩容1倍 后小于最大容量 且 老容量 >= 初始容量
//为什么扩容一倍大小呢？
//扩容一倍大小的原因是
// （1）为了保证hash 到数组位置的效率
// （2）关系到扩容后元素在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了已经
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;
//如果不是初始化进来的
if (oldTab !=null) {
//要遍历所有的节点
for (int j =0; j < oldCap; ++j) {
Node e;
//节点为null就continue 不为空的时候，把节点给临时节点e
if ((e = oldTab[j]) !=null) {
//把老结点 置为null
oldTab[j] =null;
//如果该结点没有next，也就是没有发生过冲突，桶的位置只有一个元素，把节点放入新的table中
if (e.next ==null)
//就把值直接扔到对应的位置。这里有个问题，没有发生过冲突的，就直接放进去了，扩容后也不会发生冲突吗
// ，感觉这个很nb啊
newTab[e.hash & (newCap -1)] = e;
//如果节点发生过冲突，并且是红黑树的数据结构
else if (einstanceof TreeNode)
//说明冲突的个数大于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;
}
