HashMap
HashSet需要提起的只有一句话
HashSet使用适配器模式包装了HashMap，所有的Value都是同一个Object对象，只有Key不一样，HashSet就是HashMap的KeySet
HashMap概述
一个允许Key为空也允许Value为空的哈希表
Hash冲突
当多个对象的hashcode计算结果一致时，需要处理冲突
-
开放寻址法
-
基本思想是当发生冲突时，通过探测来查找另外一个空的位置
-
探测方法有线性探测、二次探测、双重hash
-
线程探测就是：i+1、i+2、i+3.....
-
二次探测就是间隔按照平方相加：i+12、i+22、i+3^2.....
-
双重hash就是使用第二个hash函数探测间隔i + j * h2(key)
-
使用开放寻址法时，删除操作需要标记为已删除，查找操作时需要根据探测策略生成探测序列，例如i+1、i+2、i+3。并且在探测时需要判断当前元素的hash值，防止探测位置溢出。
-
-
冲突链表法
-
HashMap在Java8之前采用的就是冲突链表法，将所有相同哈希值的元素放在同一个链表（bucket）中
-
table太大和太小会有什么影响？
-
table太小会导致频繁扩容，并且会有大量元素在链表中，影响查询速度。
-
table太大会导致迭代效率低，因为需要遍历全部bucket。
-
-
负载因子
负载因子 = 当前元素数量 / 哈希表的容量
负载因子低：
-
空间利用率低
-
查询效率高
负载因子高：
-
空间利用率高
-
哈希碰撞多，导致查询效率低
因此如何平衡空间利用率和查询效率是如何设计HashMap需要做的事情。
HashMap的内部参数
-
DEFAULT_INITIAL_CAPACITY：初始容量16
-
MAXIMUM_CAPACITY：最大容量2^30
-
DEFAULT_LOAD_FACTOR：负载因子阈值0.75，超过自动扩容
-
TREEIFY_THRESHOLD：树化阈值8，超过链表变成红黑树
-
UNTREEIFY_THRESHOLD：还原阈值6，小于红黑树变成链表
-
MIN_TREEIFY_CAPACITY：最小树型化阈值64，容量大于该值时才能使用红黑树，否则优先扩容，而不是树化。
-
modCount：结构性修改标志，用于快速失败。
链表转为红黑树的逻辑
// 在 HashMap 中，当链表长度达到 TREEIFY_THRESHOLD 时，考虑链表转化为红黑树
if (binCount >= TREEIFY_THRESHOLD) {
if (tab.length < MIN_TREEIFY_CAPACITY) {
// 扩容前的处理
resize();
}
treeifyBin(tab, hash);
}
解释：如果链表长度超过树化阈值8，此时考虑转为红黑树，但是不是马上转，而是如果当前哈希表容量小于64，则先扩容。扩容之后如果链表仍然很长，仍然大于8，则将链表转换为红黑树。
为什么优先扩容而不是优先转化红黑树？
-
减少负载因子，降低链表转化红黑树的频率，因为转化是一个复杂的操作，需要额外的开销和复杂性。
-
降低链表长度，有效利用hash表空间，优化性能。
-
一句话：用更多的空间换更多的性能。
为什么链表转树阈值为8，树转链表阈值为6？
- 为了避免红黑树和链表频繁转换降低性能，设置了一段缓冲区。
扩容逻辑
1、触发扩容：当元素数量超过了当前容量 * 负载因子时，进行扩容，默认负载因子为0.75，可以在初始化时指定。
2、计算新容量：扩容为原来的两倍
3、创建新的数组：分配一个新的数组Node[]，用于存储元素。
4、重新哈希Rehash
-
迁移元素，重新遍历旧数组中的每个桶，重新计算每个元素的索引，移动到新数组中的相应位置。
-
在Rehash过程中，如果某个bucket链表长度超过8，就转红黑树，此时不管MIN_TREEIFY_CAPACI
伪代码如下：
void resize() {
// 计算新容量
int newCapacity = oldCapacity * 2;
// 创建新数组
Node<K,V>[] newTable = (Node<K,V>[]) new Node[newCapacity];
// 迁移旧数组中的所有元素到新数组
transfer(newTable);
// 更新哈希表的容量和阈值
threshold = (int) (newCapacity * loadFactor);
table = newTable;
}
void transfer(Node<K,V>[] newTable) {
// 遍历旧数组中的每个桶
for (Node<K,V> e : table) {
if (e != null) {
// 将桶中的所有元素重新哈希到新数组中
Node<K,V> next;
do {
next = e.next;
int i = indexFor(e.hash, newTable.length);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
判断相同元素的逻辑
首先计算hashcode，hashcode不相同的元素一定不相同
如果hashcode相同，再使用equals方法判断
这也是为什么hashcode和equals方法要一起重写的原因，即：
保证equals方法相同的时候hashcode也相同
hashcode的计算方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
-
如果为空直接把索引设置为0，避免异常
-
计算元素自身的hashcode，但是为了避免自身hash方法的问题，加了一个哈希扰动
-
扰动函数：将原来的hash值和无符号右移16位的值异或，增加hash函数的随机性，减少哈希冲突
-
右移操作将哈希码的高 16 位移到低 16 位，有助于将哈希码的不同部分组合在一起。这样可以确保哈希值的变化更为复杂，不容易被预测。