深入理解Java之HashMap —— 03
1. HashMap的操作流程
1.1 HashMap的构造函数
作者：Bert.King
首先我们来看一下HashMap的构造函数：
/**
* Constructs an empty {@code HashMap} with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity 初始化容量
* @param loadFactor the load factor 负载因子
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive 非法参数异常
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 注意这里的Float.isNaN(loadFactor)
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// tableSizeFor():这里对HashMap的容量阀值作了处理
this.threshold = tableSizeFor(initialCapacity);
}
需要注意的是这里的:this.threshold = tableSizeFor(initialCapacity); ,这里的threshold 为 2的幂次方，而不是capacity * load factor，当然此处并非是错误，因为此时 table 并没有真正的被初始化, 初始化动作被延迟到了putVal() 当中，所以 threshold 会被重新计算。
1.1.1 tableSizeFor函数返回大于等于capacity的最小2的整数次幂，如 cap 为 3 ，返回4；cap 为 15，返回16；
/**
* Returns a power of two size for the given target capacity.
* 返回大于等于capacity的最小2的整数次幂
*/
static final int tableSizeFor(int cap) {
// 为了防止传入的cap本身就是二的幂次方，此时得到的就是下一个二的幂次方了
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
我们可以发现在构造函数中并没有像我们所想的那样，去初始化数组。这个也是基于成本的考虑，初始化而不用，岂不浪费空间。不过在构造函数中已经对于阀值(threshold)进行初始化，超过该值时，则会进行扩容。
1.2 HashMap的put操作 1.2.1 put()函数 public V put(K key, V value) {
// 本质上调用的是putVal()
return putVal(hash(key), key, value, false, true);
}
1.2.2 putVal()函数
这里需要强调一下：
table数组的初始化操作实际上在**putVal()**中； putVal() 只跟Key相关，跟Value没有任何关系； 当桶数组对应下标的元素为null时，直接插入新建节点； 当哈希冲突时，就会对第一个节点进行判断，从而进行相应的操作。
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)
n = (tab = resize()).length;
// 如果 table在(n-1)&hash 的值如果为null,则新建一个节点插入到该位置；
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 这里表示出现哈希冲突，下标一样。处理冲突的操作
else {
Node e;
K k;
// 1. 首先判断链表的第一个元素，是不是要替换的值；
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 2. 判断 第一个节点的类型是链表or红黑树，对应进行相应的处理。处理节点是红黑树的情况。
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// 3. 处理节点类型是链表的情况；
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;
// 判断是否需要resize()。
if (++size > threshold)
resize();
// 这行代码是为了LinkedHashMap使用的。
afterNodeInsertion(evict);
return null;
}
1.2 HashMap的resize()操作
扩容操作 resize() 是 HashMap中Boss级别的存在。
首先我们来讲解一下扩容：
主要包括：
扩大数组长度，创建新数组； 迁移元素到新数组中(元素的位置可能是在原位置，也可能是原位置后移2次方的位置)；
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 1. 若原数组的容量 超过 最大容量，不作处理，即：任你碰撞
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 2. 若原容量大于默认初始化容量16 且 扩大一倍仍小于 最大容量，则 直接扩容为原来的2倍
else if ((newCap = oldCap << 1) = DEFAULT_INITIAL_CAPACITY)
newThr = oldThr < 0) // initial capacity was placed in threshold
// 初始化时指定阀值的情况
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 第一次初始化的默认配置
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 处理resize()的阀值
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;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 红黑树节点：调用TreeNode 的split() 方法对当前节点作为根节点的红黑树进行修剪
((TreeNode)e).split(this, newTab, j, oldCap);
else {
// 链表优化的节点分配
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
// 结果为0，表示索引没变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}else { // 结果为1，表示索引 = 原索引 + oldCap;
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;
}
具体可以参考：
HashMap的扩容机制—resize() Java中HashMap底层实现原理(JDK1.8)源码分析 1.2 HashMap的get操作 public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
取操作的逻辑都是通过getNode() 这个方法进行实现的。
final Node getNode(int hash, Object key) {
Node[] tab; // 桶数组
Node first, e;
int n;
K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 始终检查第一个节点是不是目标节点；
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
/**
* 若第一个节点不是目标节点，则对其进行相应的获取操作。
* 1. 判断若是TreeNode类型，则从getTreeNode();
* 2. 若是链表节点，则进行遍历查找。
*/
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
2. 总结
HashMap 中的获取桶下标： (n-1) & hash ；
Hash冲突即不通的Key桶下标相同；
处理Hash冲突，首先要判断桶数组的第一个元素是不是目标，若是直接返回；否则 判断节点类型，对应进行遍历操作。
判断是不是同一个节点：(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))
作者：Bert.King
