集合框架 （第 06 篇） 源码分析：哈希冲突(哈希碰撞)与解决

一、集合框架源码分析

• 集合框架 （第 01 篇） 源码分析：Collection<E> 框架总览
• 集合框架 （第 02 篇） 源码分析：Map<K,V > 框架总览
• 集合框架 （第 03 篇） 源码分析：ArrayList<E>
• 集合框架 （第 04 篇） 源码分析：LinkedList
• 集合框架 （第 05 篇） 源码分析：Map<K, V>接口与其内部接口Entry<K,V>
• 集合框架 （第 06 篇） 源码分析：哈希冲突(哈希碰撞)与解决算法
• 集合框架 （第 07 篇） 源码分析：jdk1.7版 HashMap
• 集合框架 （第 08 篇） 源码分析：HashMap、Hashtable、ConcurrentHashMap之间的区别
• 集合框架 （第 09 篇） 源码分析：jdk1.7版 ConcurrentHashMap
• 集合框架 （第 10 篇） 源码分析：二叉树、平衡二叉树、二叉查找树、AVL树、红黑树
• 集合框架 （第 11 篇） 源码分析：jdk1.8版 HashMap
• 集合框架 （第 12 篇） 源码分析：jdk1.8版 ConcurrentHashMap
• 集合框架 （第 13 篇） 源码分析：LinkedHashMap
• 集合框架 （第 14 篇） 源码分析：TreeMap
• 集合框架 （第 15 篇） 源码分析：Set<E> 集合
• 集合框架 （第 16 篇） 源码分析：BlockingQueue 接口
• 集合框架 （第 17 篇） 源码分析：CopyOnWriteArrayList 与 CopyOnWriteArraySet

原文持续更新链接: https://github.com/about-cloud/JavaCore

正文

---

一、Hash冲突（哈希碰撞💥）

1.1、什么是冲突？

线性跳跃 这种增量序列。从 增量i 可以看出正负交替，特点是在探测时左右↔️跳跃式探测。

伪随机探测

原来线性探测的步长都是已知数，现在将每个步长改为随机获取。实际过程也是随机产生一批随机数，也就是 随机序列。

2.2、再哈希法

再哈希法是有多个哈希函数(算法)，当第一次产生哈希冲突时，就使用第二个哈希函数，如果还产生哈希冲突就使用第三个，以此类推，再次哈希，直达无冲突，这样的做法会增加哈希计算时间。

2.3、链地址法（链表法）

当多个元素产生哈希冲突时，它们的哈希码是一定相同，落脚的哈希槽也相同。将它们通过地址引用一一相连，也就是形成 链表 的形式。这样它们既可以存储，又不会占用其他哈希槽的位置。这种通过链表形式解决哈希冲突的算法称为链表法。由不同元素、相同哈希码经过组织形成的数据结构称为 哈希桶Bucket，或者说这个容器是 哈希桶。哈希槽的位置也就是哈希桶号 。

2.4、建立公共溢出区

为所有产生哈希冲突的元素建立一个公共溢出区域来存放溢出的元素。在查找时，如果通过计算发现对应的哈希槽处没该元素，则进入公共溢出区 进行查找，溢出的元素相对于 散列表 来说是比较小的。原来的表称为基本表，公共溢出区又称溢出表。

原文持续更新链接: https://github.com/about-cloud/JavaCore