HashMap相关知识点
扰动函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 取对象的hashCode(32位整数)。
- 获取高16位(h >>> 16 无符号位移16位)。
- 跟自己的hashCode高16位进行亦或运算。
取模运算
return hash(key) & (length - 1)
这个length一定是2的整数次幂，减1保证二进制全是1。用位运算取模。
PUT增加元素
-
先通过hash值计算出key映射到哪个桶(扰动函数+ 取模)；
-
如果桶上没有碰撞冲突，直接插入；
-
如果出现冲突，则处理冲突：
a. 若使用传统的链式方法插入，链长度大于临界值，则进行链表树化；
b. 若该桶使用红黑树处理冲突，则调用红黑树的插入方法插入数据。
-
如果桶中存在重复的键，则为该键替换新值value；
-
若现有kv对数量(即size)大于阈值threshold，则进行扩容
Put完整代码
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断是不是第一次put数据，第一次put数据才申请分配内存 Node<>[] table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 判断 通过hash索引到的桶里面有没有其他Node，没有就new一个node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { //桶内有数据，需要在桶内添加链表或者是红黑树结点
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //判断新key和旧key是否相等，重复的键则替换。
e = p;
else if (p instanceof TreeNode)//键不重复，且是红黑树结点，用红黑树的插入方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//键不重复，且是链表节点
for (int binCount = 0; ; ++binCount) { //循环
if ((e = p.next) == null) { //链表为空或p指向最后一个链表结点，新建Node结点，链表长度大于树化阈值，树化；然而======>>>>>>>>树化条件是(桶长度>=64 && 链表长度>=8)，树化的时候检查如果桶长度不达标，就会扩容而不是树化
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)))) //同hash，同key
break;
p = e;// 等同于p = p.next;
}
}
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;
}
扩容
- 扩容的时机
- 数组长度大于threshold
- bucket的链表长度大于8，且桶的数量小于64，再次发生hash碰撞不树化直接扩容。
- 扩容的内容
扩容之后，重新申请一个长度为原来2倍的数组，遍历原来hash表中每个元素，重新索引(hash)，很耗费性能。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (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);
}
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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) { //old为null表示第一次分配内存，没有必要挪元素。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 这里使用了巧妙的重新hash方法，重新索引的位置要么在原位置，要么在 原位置+oldCap 的位置。
// e.hash直接和oldCap做&运算，0表示在原位置，1表示在新位置。在不在新位置取决于高位的1bit。
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;
}
树化
总结：
- 根据哈希表中元素个数确定是扩容还是树化。(树化条件 桶数量>=阈值 && 桶中链表长度>=阈值，若其中一个条件不满足)
- 如果是树化，遍历链表，新建树形结点，复制数据，建立树的连接。
- 然后让桶中的第一个元素指向新创建的树根结点，替换桶的链表内容为树形化内容。