HashMap
HashMap 是 Java 的一种键值对容器,该容器的核心方法是 putVal 方法,为了提高查询稳定性,Java 团队向该类引入了红黑树结构,为了减少碰撞概率引入了扰动函数,在对象的哈希值相同时又调用了 equals 方法进行二次检测
泊松分布
* 树形节点的大小是普通节点的两倍
* 桶的数量和节点的数量的关系呈泊松分布
* 树化阈值 8 解树化阈值 6 初始容量为 16 是经验的选择
* 默认情况下,当 HashMap 中的元素个数超过其容量的 3/4 便会触发扩容
* 初始容量为 16 第一次扩容后 32 第二次扩容后 64, λ 分别为 12 24 48
* 横坐标代表初始容量,纵坐标代表发生冲突的概率,面积代表桶中元素的个数(与 capacity 无直接联系)。
* λ 与 冲突概率 P(K) 和柱状图的面积呈正比
* λ 的初始值为 0.75 初始 capacity 为 16 是容量大冲突概率小的均衡选择
* λ = loadFactor * capacity 当 HashMap 超过此数时,就会触发 HashMap 的扩容操作
* 红黑树最好 O(logn) 最坏 O(logn)
* 链表 + 数组最好 O(1) 最坏 O(N)
* 为了保证系统查询的稳定性 Java 在 JDK 1.8 中使用了 数组 + 链表 <-----> 红黑树的结构
允许为空
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
* 为什么只允许一个 key 为 null 的对象?
当 key 为 null 时 HashMap#hash 只会返回 0
* 为什么可以允许多个 key !=null 但 value == null 的键值对?
HashMap#putVal 不会对 value == null 做出检查,只要 key 不同就会允许插入
扰动函数
// 哈希冲突无法解决只能尽力避免
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
* Java 在计算对象在 HashMap 的位置时利用了最优化问题中的扰动函数,基本思路是:先将对象的 hasCode 右移 16 位,获得大概四十亿的映射空间中的一个值,
再将该值和原先的 hashCode 做异或运算进行缩放,使之能够放入 HashMap 中
* 当一个对象的 hasCode 足够特殊时(很小或是个奇数)经扰动函数扰动后结果仍可能相同,此时通过 equals 比较是否相等是避免碰撞的最好方法
以二为底的幂
* 同一时期 HashMap 的长度是固定的
* 与运算: 0 与 1 为 0,1 与 1 为 1
* e = tab[index = (n - 1) & hash]
* 以 2 为底的 k 次幂的值减一后的结果的二进制表示是 k 个一
* 以 2 为底的幂可以保证 HashMap 中的每一个位置发生冲突的概率是相同的
* HashMap 未对扩容和插入删除做同步设计,并发环境下请使用 HashTable 或 ConcurrentHashMap
static final int tableSizeFor(int cap) {
// 无符号左移高位补零
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
// 溢出返回一
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 计算一个 int 类型的整数补码的前导零的数量
public static int numberOfLeadingZeros(int i) {
// HD, Count leading 0's
if (i <= 0)
return i == 0 ? 32 : 0; // 0 的补码全是零,负数没有前导零
int n = 31;
/*
32 位整数,每 8 位一段,从 1 开始,最多有 31 个 0
*/
// i >= 2 ** 16
if (i >= 1 << 16) { n -= 16; i >>>= 16; } // 65535
// i >= 2 ** 8
if (i >= 1 << 8) { n -= 8; i >>>= 8; } // 256
// i >= 2 ** 4
if (i >= 1 << 4) { n -= 4; i >>>= 4; } // 32
// i >= 2 ** 2
if (i >= 1 << 2) { n -= 2; i >>>= 2; } // 2
return n - (i >>> 1);
}
final Node<K,V>[] resize() { // resize 用于调整 HashMap 的大小,不只用于扩容
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// oldCap 超出最大容量时不再扩容
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
} // 使用单参构造方法,在第一次会缩小至 0.75 * capacity
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 使用空构造方法,在第一次直接扩容至 16,阈值扩大为 12
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) {
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;
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;
}
标签:Node,详细,null,HashMap,int,key,解析,oldCap
From: https://blog.csdn.net/weixin_63594548/article/details/140813709