Hash冲突的解决方案
总结
- 拉链法：冲突位置挂链表，链表过长转红黑树，HashMap 用的这个
- 开放地址法：冲突时在数组内找下一个空位，ThreadLocalMap 用的线性探查
- 再哈希法：冲突就换个哈希函数重新算，简单但开销大
1. 拉链法（链接法）
Hash 碰撞就是两个 key 算出来的 hash % 数组长度 一样，落到了同一个槽位。
拉链法的处理方式是：冲突了就在这个槽位挂一条链表，所有冲突的元素都串在上面。查找时定位到槽位，再遍历链表找到对应的 kv。
链表太长的话遍历性能会退化到 O(n)，所以 HashMap 在链表长度超过阈值后会把链表转成红黑树，复杂度降到 O(log n)。
2. 开放地址法
开放地址法的核心思路是：所有元素都存在数组里，冲突了就在数组内部找另一个空位放。数组放不下时触发扩容。
有三种探查方式：
2.1 线性探查
冲突时依次往后找，步长固定为 1，直到找到空位或遍历完整个表。
di = 1, 2, 3, ..., m-1
实现最简单，但容易产生"聚集"问题——冲突元素扎堆，越冲越慢。ThreadLocal 的 ThreadLocalMap 就是用的这个策略。
2.2 二次探查
冲突时左右跳跃式探测，步长按平方递增，分布更分散。
di = 1², -1², 2², -2², ..., k², -k² (k ≤ m/2)
2.3 伪随机探查
步长用伪随机数序列，每次加上一个随机偏移量，进一步打散聚集。
di = 伪随机数序列，如 i = (i + p) % m
3. 再哈希法
冲突了就换一个哈希函数重新算，直到落到空位为止。
思路简单，但每次冲突都要重新计算哈希，冲突多的时候开销比较大，实际用得不多。