Hash与Hash冲突
大家都了解过HashMap或者其他有着hash表结构的容器，所以首先我们来谈谈什么是Hash，什么是Hash冲突
什么是Hash？
Hash表也称散列表，也有直接译作哈希表，Hash表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。
原理
- Hash表采用一个映射函数 f : key —> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置.
- 通常情况下，这种映射关系称作为Hash函数，而通过Hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置，并不是实际的物理地址)称作为Hash地址.
p=H(key) p为地址，H为hash函数，key为关键字
举例：
我们平时查字典时，要查哪个字，就会先去找这个字的拼音所在的那一页。例如我们想查“陈”字，我们就会想到chen这个拼音，每个字都有与之对应的拼音，由“陈”字转为chen拼音这个过程就可以理解为关键字由Hash函数计算所得的存储位置，“陈”为关键字，而我们利用小学拼音的知识去把这个字转为拼音的这个思路就是Hash函数，而chen这个拼音就是我们的存储位置
什么是Hash冲突？
举例：
利用刚刚查字典的例子，现在想想看，一个拼音下是不是有多个字？我们查到了chen的拼音，但发现，chen下不仅有陈，还有称、臣、晨等很多个字，这样的话，就与我们开始的想法通过查拼音查到某个特定的字产生了矛盾，简单地理解为，某些关键字经过hash函数计算后得出相同的结果(一个拼音下有多个字)，就叫做hash冲突。
如何解决Hash冲突？
- 开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
- 再哈希法
- 链地址法
- 建立一个公共溢出区
1.开放定址法
开放定址法也叫闭散列，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
线性探测再散列
平方探测再散列
随机探测再散列
di=伪随机数序列。
优点：
①记录更容易进行序列化（serialize）操作（由于不存在指针）
②如果记录总数可以预知，可以创建完美哈希函数，此时处理数据的效率是非常高的。
缺点：
①扩容成本飙升。存储记录的数目不能超过桶数组的长度，如果超过就需要扩容，而扩容会导致某次操作的时间成本飙升，这在实时或者交互式应用中可能会是一个严重的缺陷
②加大计算成本。使用探测序列，有可能其计算的时间成本过高，导致哈希表的处理性能降低
③有空槽导致内存浪费。由于记录是存放在桶数组中的，而桶数组必然存在空槽，所以当记录本身尺寸（size）很大并且记录总数规模很大时，空槽占用的空间会导致明显的内存浪费
④删除记录时，比较麻烦。比如需要删除记录a，记录b是在a之后插入桶数组的，但是和记录a有冲突，是通过探测序列再次跳转找到的地址，所以如果直接删除a，a的位置变为空槽，而空槽是查询记录失败的终止条件，这样会导致记录b在a的位置重新插入数据前不可见，所以不能直接删除a，而是设置删除标记。这就需要额外的空间和操作。
2.再哈希法
使用哈希函数去散列一个输入的时候，输出是同一个位置就再次哈希，直至不发生冲突位置
举个例子关键字key由hash函数得到地址p后，若发生hash冲突，此时我们就可以通过得到的地址p来继续hash，也就是p2=H§，若再次发生hash冲突，我们又继续利用地址进行hash，循环往复，直到得到的p不发生hash冲突为止。
缺点：每次冲突都要重新哈希，计算时间增加。
3.链地址法（拉链法）
原文链接
HashMap，HashSet其实都是采用的拉链法来解决哈希冲突的，就是在每个位桶实现的时候，我们采用链表（jdk1.8之后采用链表+红黑树）的数据结构来去存取发生哈希冲突的输入域的关键字（也就是被哈希函数映射到同一个位桶上的关键字）。首先来看使用拉链法解决哈希冲突的几个操作：
①插入操作：在发生哈希冲突的时候，我们输入域的关键字去映射到位桶（实际上是实现位桶的这个数据结构，链表或者红黑树）中去的时候，我们先检查带插入元素x是否出现在表中，很明显，这个查找所用的次数不会超过装载因子（n/m:n为输入域的关键字个数，m为位桶的数目），它是个常数，所以插入操作的最坏时间复杂度为O(1)的。
②查询操作：和①一样，在发生哈希冲突的时候，我们去检索的时间复杂度不会超过装载因子，也就是检索数据的时间复杂度也是O(1)的
③删除操作：如果在拉链法中我们想要使用链表这种数据结构来实现位桶，那么这个链表一定是双向链表，因为在删除一个元素x的时候，需要更改x的前驱元素的next指针的属性，把x从链表中删除。这个操作的时间复杂度也是O(1)的。
优点
与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
缺点
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
4.建立一个公共溢出区
建立一个公共溢出区域，就是把冲突的都放在另一个地方，不在表里面，具体实现涉及到知识盲区了
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176721.html原文链接：https://javaforall.net
