1.Hash算法和Hash表

了解Hash冲突首先要了解Hash算法和Hash表

如图所示：1.Hash算法就是吧任意长度的输入通过散列函数算法变成固定长度的输出，这个输出结果是一个散列值。2.Hash表又叫做“散列表”它通过key直接访问到内存存储位置的数据结构，在具体的实现上，我们通过Hash函数，把key映射到表中的某个位置，来获取这个位置的映射，从而加快数据的查找。

2.Hash冲突

所谓的hash冲突是由于哈希算法被计算的数据是无限的，而计算后的结果的范围是有限的，所以总存在不同的数据，经过计算之后得到的值是一样的，那么这种情况下就产生了所谓的hash冲突。

3.解决hash冲突的四种方法

通常解决hash冲突的方法有四种，分别是开放地址法（也叫线性探测法）、链式寻址法、再Hash法、建议公共溢出区。

3.1 开放地址法

开放地址法也被称作线性探测法，就是在发生冲突的那个位置开始，按照一定次序从hash表中找到一个空闲位置然后把爱发生冲突的元素存入到这个位置，而在java中，ThreadLocal就用到了线性探测法来解决hash冲突。

如图所示，在Hash表索引1的位置存了key=name，再向它添加key=hobby的时候，假设计算得到的索引也是1，那么这个时候发生哈希冲突，而开放开放定址法就是按照顺序向前找到一个空闲的位置，来存储这个冲突的key。

3.2 链式寻址法

链式寻址法是一种常用的方法，简单理解就是把存在Hsh冲突的key以单向链表的方式来进行存储，比如HashMap，如图所示：

3.3 再Hash法

再Hash法，就是通过某个Hash函数计算的key，存在冲突的时候，再用另外一个Hash函数对这个可以进行Hash，一直运算，直到不再产生冲突为止，这种方式会增加计算的一个时间,性能上呢会有一些影响

3.4 建立公共溢出区

建立公共溢出区，就是把Hash表分为基本表和溢出表两个部分，凡是存在冲突的元素，一律放到溢出表中

4.HashMap选择的方法

HashMap在JDK1.8版本中是通过链式寻址法以及红黑树来解决Hash冲突的问题，其中红黑树是为了优化Hash表的链表过长导致时间复杂度增加的问题，当链表长度大于等于8并且Hash表的容量大于64的时候，再向链表添加元素，就会触发链表向红黑树的一个转化

5.补充：什么是红黑树

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。

对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间，视情况而定。那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题。

红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。

红黑树的原理：首先，红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。它同时满足以下特性：

• 节点是红色或黑色
• 根是黑色
• 叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），下图中的那些null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点
• 红色节点的子节点都是黑色
• 红色节点的父节点都是黑色
• 从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
• 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点