10 KiB
HashMap笔记
Node类
Node类有hash、key、value、下一个节点地址等4个属性，可以构成一个单项链表，为HashMap中存储数据的基本类型
static class Node<K,V> implements Map.Entry<K,V> {
// 经过计算之后的hash值
final int hash;
final K key;
V value;
// 链表中下一个节点的地址
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
TreeNode类
TreeNode类可以构成一个红黑数，为HashMap中链表树化之后的类型；
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K, V> parent; // red-black tree links
TreeNode<K, V> left;
TreeNode<K, V> right;
TreeNode<K, V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K, V> next) {
super(hash, key, val, next);
}
}
HashMap属性
hash表
HashMap中有个table属性，用于存储键值对数据，即是hash表。 其类型为Node数组，数组中每个位置称为桶，桶中保存链表或者红黑树的头节点地址，组成了一个二维的数据结构， 数组的长度即为HashMap的表容量
transient Node<K,V>[] table;
默认初始容量
默认为16，即不指定初始容量的情况下，hash表数组长度为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
最大初始容量
static final int MAXIMUM_CAPACITY = 1 << 30;
默认负载因子
负载因子用于计算hash表扩容值，当hash表桶数量大于 负载因子与表容量的乘积 时，需要对hash表进行扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
###链表树化阈值
当hash表某个桶中的链表元素大于树化阈值的时候，且桶个树大于树化最小表容量的时候，就要将这个链表转化为红黑树。 这个值必须大于2，并且应该至少为8，
static final int TREEIFY_THRESHOLD = 8;
非树化阈值
hash表某个桶中保存的是红黑树且树的节点个数小于非树化阈值的时候，红黑树将转化为链表 这个值应小于链表树化阈值，且最多为6
static final int UNTREEIFY_THRESHOLD = 6;
树化最小表容量
链表树化前需要判断是否达到了最小表容量，即判断hash表的大小是否大于这个值， 这个值应该大于等于4倍链表树化阈值，以避免调整大小和树化阈值之间的冲突
static final int MIN_TREEIFY_CAPACITY = 64;
负载因子
HashMap中空值扩容阈值的属性
final float loadFactor;
扩容阈值
控制hash表扩容的阈值，该值通过 负载因子 * hash表容量计算得到。 初始化的时候不指定表容量，这个值为0，初始化时指定表容量，这个值等于计算后的表容量， 但是第一次put的时候会将表容量与负载因子相乘计算并给这个树形重新赋值
int threshold;
hash表操作次数
put、remove、merge、clear等操作都会使得该值增加， 在foreach、replaceAll等会影响hash表结构的操作期间，会判断这个值是否变化 ，如果变化了，会快速失败
transient int modCount;
hash表索引计算&表容量为2的幂次方原因
元素在放入hash表中某个桶的时候，需要通过hash算法计算出桶位置，即hash表索引（数组下标）。 计算公式为 hash & (table.length - 1)。
如果hash表容量为2的幂次方，即table.length = 2^n，那么该公式即为计算hash值除以表容量后的余数。 通过%同样可以获取到余数，但是位运算更加高效，所以这里需要限定hash表容量必须是2的幂次方。
通过表索引公式，可以将任意hash值转变为0到表容量范围的整数，可以通过该整数直接为元素分配存储的桶。
通过简单的代码对公式可以进行验算：
public class Test {
public static void main(String[] args) {
int length = 16;
for (int i = 0; i < 50; i++) {
int hash = i & (length - 1);
System.out.println(i + " -> " + hash);
}
}
}
hash计算
HashMap中用于索引计算的hash值不是key的hash值，而是通过hash计算方法得到的。 算法为hash值异或hash值无符号右移16位后的值。
hash无符号右移16位之后，高16位会变为0，异或计算不会改变原hash值的高16位，但是会改变低16位， 将高16位与低16的特征将结合，使得hash值的低16位更加散列
当两个hash值高位不同，但是低位相同的时候，通过hash索引算法，高位会被屏蔽，得到的结果是相同的， 容易造成hash冲突，将低位特征与高位特征相结合可以减少hash冲突提高效率
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
扩容
在HashMap添加数据的时候会做扩容判断，如HashMap#putVal方法中：
// size：hash表容量，即table数组的长度
// threshold：扩容阈值，一般为0.75倍表容量
if (++size > threshold){
resize();
}
HashMap的扩容逻辑在 HashMap#resize 方法中。
// oldCap：旧表容量
// newCap：新表容量
// newThr 、oldThr：新旧扩容阈值
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
//扩容，新表容量*2 ，新阈值*2
newThr = oldThr << 1;
}
}
hash表容量限定都是2的幂次方，扩容时直接按位左移一位，即表容量乘以2. 但是在扩容之后，表容量变化了，表索引的计算结果也会改变。此时需要重新hash，并移动元素保存位置。 对于同一个链表的节点来说，索引计算结果也会改变，所以链表的节点也会移动位置。
但是容量以及索引计算公式都与2的幂次方有关，所以节点移动只有两种结果： 1是位置不变，2是移动到 当前索引 + 旧容量值 的桶上。
if (oldTab != null) {
//oldCap：旧表容量，遍历旧表数组，移动元素到新表上
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null){
// 重新hash
newTab[e.hash & (newCap - 1)] = e;
}else if (e instanceof TreeNode){
//移动红黑树节点
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
}else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
// 如果hash按位与旧容量值为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;
}
}
}
}
}
链表树化
当hash表中某个桶内的链表节点过多时，需要将链表转换为红黑树以提高查询效率，如在HashMap#putVal方法中：
//该循环体逻辑为：插入节点数据时，在hash表某个桶上的链表知道key值相同的节点或者找到节点末尾空位
//binCount：当前链表节点数量
//TREEIFY_THRESHOLD：链表树化阈值
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//在链表末尾添加节点
p.next = newNode(hash, key, value, null);
//链表中节点数量大于树化阈值，
if (binCount >= TREEIFY_THRESHOLD - 1) {
treeifyBin(tab, hash);
}
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
break;
}
p = e;
}
在向hash表中插入数据的时候，如果插入位置是同一个桶的链表，那么会根据链表树化阈值，判断是否需要进行树化， 树化方法为HashMap#treeifyBin，在树化方法中还要先判断hash表容量是否大于最小树化表容量（默认为64）， 否则不会进行树化，而是进行表扩容。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果表容量小于最小树化表容量，那么会先扩容，不会进行树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//重新hash扩容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}