本文首发于 vivo互联网技术 微信公众号 
链接：https://mp.weixin.qq.com/s/5vxYoeARG1nC7Z0xTYXELA
作者：Xuegui Chen
哈希是一种通过对数据进行压缩, 从而提高效率的一种解决方法，但由于哈希函数有限，数据增大等缘故，哈希冲突成为数据有效压缩的一个难题。本文主要介绍哈希冲突、解决方案，以及各种哈希冲突的解决策略上的优缺点。
一、哈希表概述
哈希表的哈希函数输入一个键，并向返回一个哈希表的索引。可能的键的集合很大，但是哈希函数值的集合只是表的大小。
哈希函数的其他用途包括密码系统、消息摘要系统、数字签名系统，为了使这些应用程序按预期工作，冲突的概率必须非常低，因此需要一个具有非常大的可能值集合的散列函数。
密码系统:给定用户密码，操作系统计算其散列，并将其与存储在文件中的该用户的散列进行比较。(不要让密码很容易被猜出散列到相同的值)。
消息摘要系统:给定重要消息，计算其散列，并将其与消息本身分开发布。希望检查消息有效性的读者也可以使用相同的算法计算其散列，并与发布的散列进行比较。(不要希望伪造消息很容易，仍然得到相同的散列)。
这些应用的流行哈希函数算法有:
md5 : 2^128个值（找一个冲突键，需要哈希大约2 ^ 64个值）
sha-1：2^160个值（找一个冲突键，需要大约2^80个值）
二、哈希冲突
来看一个简单的实例吧，假设采用hash函数：H(K) = K mod M，插入这些值：217、701、19、30、145
H(K) = 217 % 7 = 0
H(K) = 701 % 7 = 1
H(K) = 19 % 7 = 2
H(K) = 30 % 7 = 2
H(K) = 145 % 7 = 5
上面实例很明显 19 和 30 就发生冲突了。
三、冲突解决策略
除非您要进行“完美的散列”，否则必须具有冲突解决策略，才能处理表中的冲突。
同时，该策略必须允许查找，插入和删除正确运行的操作！
冲突解决技术可以分为两类：开散列方法( open hashing，也称为拉链法，separate chaining )和闭散列方法( closed hashing，也称为开地址方法，open addressing )。这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。
下面介绍业内比较流行的hash冲突解决策略：
线性探测(Linear probing)
双重哈希(Double hashing)
随机散列(Random hashing)
分离链接(Separate chaining)
上面线性探测、双重哈希、随机散列都是闭散列法，而分离链接则是开散列法。
1、线性探测(Linear probing)
插入一个值
使用散列函数H（K）在大小为M的表中插入密钥K时：
设置 indx = H（K）
如果表位置indx已经包含密钥，则无需插入它。Over
否则，如果表位置indx为空，则在其中插入键。Over
其他碰撞。设置 indx =（indx + 1）mod M.
如果 indx == H（K），则表已满！就只能做哈希表的扩容了
因此，线性探测基本上是在发生碰撞时对空槽进行线性搜索。
优点：易于实施；总是找到一个位置（如果有）；当表不是很满时，平均情况下的性能非常好。
缺点：表的相邻插槽中会形成“集群”或“集群”键；当这些簇填满整个阵列的大部分时，性能会严重下降，因为探针序列执行的工作实际上是对大部分阵列的穷举搜索。
简单例子
如哈希表大小M = 7, 哈希函数：H(K) = K mod M。插入这些值：701, 145, 217, 19, 13, 749
H(K) = 701 % 7 = 1
H(K) = 145 % 7 = 5
H(K) = 217 % 7 = 0
H(K) = 19 % 7 = 2
H(K) = 13 % 7 = 1(冲突) --> 2(已经有值) --> 3(插入位置3)
H(K) = 749 % 7 = 2(冲突) --> 3(已经有值) --> 4(插入位置4)
可见，如果哈希表如果不是很大，随着数据插入，冲突也会组件发生，探针遍历次数将会逐渐变低，检索过程也就成为穷举。
检索一个值
如果使用线性探测将键插入表中，则线性探测将找到它们！
当使用散列函数 H（K）在大小为N的表中搜索键K时：
设置 indx = H（K）
如果表位置indx包含键，则返回FOUND。
否则，如果表位置 indx 为空，则返回NOT FOUND。
否则设置 indx =（indx + 1）modM。
如果 indx == H（K），则返回NOT FOUND。就只能做哈希表的扩容了
问题：如何从使用线性探测的表中删除键？
能否进行“延迟删除”，而只是将已删除密钥的插槽标记为空？ 
很明显，在线性探测很难做到，如果把位置置为空，那么如果后面的值也是哈希冲突，线性探测插入，则再也无法遍历这些值了。
2、双重哈希(Double hashing)
线性探测冲突解决方案会导致表中出现簇，因为如果两个键发生碰撞，则探测到的下一个位置对于这两个键都是相同的。
双重哈希的思想：使偏移到下一个探测到的位置取决于键值，因此对于不同的键可以不同。
需要引入第二个哈希函数 H 2（K），用作探测序列中的偏移量（将线性探测视为 H 2（K）== 1 的双重哈希）。
对于大小为 M 的哈希表，H 2（K）的值应在 1到M-1 的范围内；如果M为质数，则一个常见选择是 H2（K）= 1 +（（K / M）mod（M-1））。
然后，用于双哈希的插入算法为：
设置 indx = H（K）; offset = H 2（K）
如果表位置indx已经包含密钥，则无需插入它。Over
否则，如果表位置 indx 为空，则在其中插入键。Over
其他碰撞。设置 indx =（indx + offset）mod M.
如果 indx == H（K），则表已满！就只能做哈希表的扩容了
哈希表为质数情况，双重hash在实践中非常有效
双重 Hash 也见：https://blog.csdn.net/chenxuegui1234/article/details/103454285
3、随机散列(Random hashing)
与双重哈希一样，随机哈希通过使探测序列取决于密钥来避免聚类。
使用随机散列时，探测序列是由密钥播种的伪随机数生成器的输出生成的（可能与另一个种子组件一起使用，该组件对于每个键都是相同的，但是对于不同的表是不同的）。
然后，用于随机哈希的插入算法为：
创建以 K 为种子的 RNG。设置indx = RNG.next() mod M。
如果表位置 indx 已经包含密钥，则无需插入它。Over
否则，如果表位置 indx 为空，则在其中插入键。Over
其他碰撞。设置 indx = RNG.next() mod M.
如果已探测所有M个位置，则放弃。就只能做哈希表的扩容了。
随机散列很容易分析，但是由于随机数生成的“费用”，它并不经常使用。双重哈希在实践中还是经常被使用。
4、分离链接(Separate chaining)
在具有哈希函数 H（K）的表中插入键K时
设置 indx = H（K）
将关键字插入到以 indx 为标题的链接列表中。（首先搜索列表，以避免重复。）
在具有哈希函数H（K）的表中搜索键K时
设置 indx = H（K）
使用线性搜索在以 indx 为标题的链表中搜索关键字。
使用哈希函数 H（K）删除表中的键K时
设置 indx = H（K）
删除链接列表中以 indx 为标题的键
优点：随着条目数量的增加，平均案例性能保持良好。甚至超过M；删除比开放地址更容易实现。
缺点：需要动态数据，除数据外还需要存储指针，本地性较差，导致缓存性能较差。
很明显，Java7 的 HashMap 就是一种分裂链接的实现方式。
分离链哈希分析
请记住表的填充程度的负载系数度量：α = N / M。
其中M是表格的大小，并且 N 是表中已插入的键数。
通过单独的链接，可以使 α> 1 给定负载因子α，我们想知道在最佳，平均和最差情况下的时间成本。
成功找到
新键插入和查找失败（这些相同），最好的情况是O（1），最坏的情况是O（N）。让我们分析平均情况
分裂链接的平均成本
假设负载系数为 α = N / M 的表
在M个链接列表中总共分配了N个项目（其中一些可能为空），因此每个链接列表的平均项目数为：
如果查找/插入失败，则必须穷举搜索表中的链表之一，并且表中链表的平均长度为α。因此，使用单独链接进行插入或不成功查找的比较平均次数为
成功查找后，将搜索包含目标密钥的链接列表。除目标密钥外，该列表中平均还有（N-1）/ M个密钥；在找到目标之前，将平均搜索其中一半。因此，使用单独链接成功找到的比较平均次数为
当α<1时，它们分别小于1和1.5。并且即使当α超过1时，它们仍然是O（1），与N无关。
四、开散列方法 VS 闭散列方法
如果将键保留为哈希表本身中的条目，则可以使用线性探测，双重和随机哈希... 这样做称为“开放式寻址”，也称为“封闭式哈希”。
另一个想法：哈希表中的条目只是指向链表（“链”）头部的指针；链接列表的元素包含键... 这称为“单独链接”，也称为“开放式哈希”。
通过单独的链接，冲突解决变得容易：只要在其链表中插入一个键，就可以将其插入（为此，可以使用比链表更高级的数据结构；但是正如我们将看到的，链表在一般情况下效果很好）。
让下面我们看一下这些策略的时间成本。
开放式地址哈希分析
分析哈希表“查找”或“插入”性能时，一个有用的参数是负载系数 α = N / M。
其中 M 是表格的大小，并且 N 是表中已插入的键数负载系数是表满度的一种度量。
给定负载因子 α ，我们想知道在最佳，平均和最差情况下的时间成本。
成功找到
对所有键，最好的情况是O（1），最坏的情况是O（N），新键插入和查找失败（这些相同），所以让我们分析平均情况。
我们将给出随机哈希和线性探测的结果。实际上，双重哈希类似于随机哈希；
平均不成功的查找/插入成本
假定负载系数为α= N / M的表。考虑随机散列，因此聚类不是问题。每个探针位置是随机且独立生成的对于每个探针，找到空位置的可能性为（1-α）。查找空位置将停止查找或插入，这是一个伯努利过程，成功概率为（1-α）。该过程的预期一阶到达时间为 1 /（1-α）。所以：
使用随机哈希进行插入或不成功查找的探针的平均数量为
使用线性探测时，探头的位置不是独立的。团簇形成，当负载系数高时会导致较长的探针序列。可以证明，用于线性探测的插入或未成功发现的探针的平均数量约为
当 α 接近1时，这些平均案例时间成本很差，仅受M限制；但当 α 等于或小于7.75（与M无关）时，效果还不错（分别为4和8.5）
平均成功查找成本
假定负载系数为 α= N / M 的表。考虑随机散列，因此聚类不是问题。每个探针位置是随机且独立生成的。
对于表中的键，成功找到它所需的探针数等于将其插入表中时所采用的探针数。每个新密钥的插入都会增加负载系数，从0开始到α。
因此，通过随机散列成功发现的探测器的平均数量为
通过线性探测，会形成簇，从而导致更长的探针序列。可以证明，通过线性探测成功发现的平均探针数为
当α接近1时，这些平均案例时间成本很差，仅受M限制；但当α等于或小于7.75时好（分别为1.8和2.5），与M无关。

	

面试题编号：1013
发送消息“1013”即可获取该面试题详细解答
01
问题描述         
Java中HashMap是怎么解决哈希冲突的？这道面试题需要面试者对Java中的HashMap数据结构、哈希冲突原理以及红黑树相关知识有非常深的了解，有一定难度。
02
参考回答         
在解决这个问题之前，我们首先需要知道什么是哈希冲突，而在了解哈希冲突之前我们还要知道什么是哈希才行。
什么是哈希？
Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值(哈希值)；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
什么是哈希冲突？
当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞(哈希碰撞)。
HashMap的数据结构
在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突：
这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下，但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化。
hash()函数
上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或)
}
这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算(9次扰动)，在1.8中，只进行了1次位运算和1次异或运算(2次扰动)；
JDK1.8新增红黑树
通过上面的链地址法(使用散列表)和扰动函数我们成功让我们的数据分布更平均，哈希碰撞减少，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；
总结
简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：
1. 使用链地址法(使用散列表)来链接拥有相同hash值的数据；
2. 使用2次扰动函数(hash函数)来降低哈希冲突的概率，使得数据分布更平均；
3. 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；
对该面试题的解答有疑议，欢迎在留言区讨论点个在看，帮助到更多面试的朋友❤️↓

1 简介
哈希表：又称散列表，是一种根据给定的关键字来计算关键字在表中地址的数据结构，即散列表建立了关键字和存储地址之间的一种直接映射关系。
哈希函数：又称散列函数，将给定关键字映射为该关键字对应的地址的函数，记为Hash(key)=Addr。
哈希冲突：散列函数将两个以上的不同关键字映射到同一个地址，这种情况成为哈希冲突，这些冲突的不同关键字称为同义词。
2 哈希函数和冲突处理方法
2.1 构造哈希函数的要点
哈希函数定义域必须包含需要存储的全部关键字，值域的范围依赖于哈希表的大小或者地址范围。
哈希函数计算出来的地址应该能等概率，均匀地分布在整个地址空间，减少冲突的发生。
哈希函数应该尽量简单，计算时间短
2.2 常用的Hash函数的构造方法
2.2.1.直接定址法
直接取关键字的某个线性函数值为散列地址，散列函数为Hash(key)=a*key+b，其中，a和b是常数。这种方法计算最简单，不会产生冲突。
2.2.2.取模法
假定哈希表表长为m，取一个不大于m但最接近或等于m的质数p，用取模运算把关键字转换成哈希地址。散列函数为Hash(key)=key%p。该方法的关键是选好p，使得每一个关键字通过该函数转换后等概率的映射到散列空间上任一地址，从而尽可能的减少冲突的可能性。
2.2.3.数字分析法
设关键字是r进制数（如十进制），而r个数码在各位上出现的概率不一定相同，可能在某些位上分布均匀些，每种数码出现的几率均等；而在某些位上分布不均匀，只有集中数码经常出现，则应选取数码分布较为均匀的若干位做为散列地址。这种方法是用于已知的关键字集合。
2.2.4.平方取中法
取关键字的平方值的中间几位作为散列地址。具体取多少位要看实际情况而定。这种方法得到的散列地址与关键字的每一位都有关系，是的散列分布比较均匀。
2.2.5.折叠法
将关键字拆分为相同的几个部分（最后一部分位数可以短一些），然后取这部分的叠加和作为散列地址，这种方法称为折叠法。这种方法适合用于关键字位数较多且关键字中每一位数字分布大致均匀时。
### 2.3 常用Hash函数冲突处理方法
2.3.1.开放定址法
将产生冲突的Hash地址作为自变量，通过某种冲突解决函数得到一个新的空闲的Hash地址。
2.3.1.1 线性探测法
冲突发生时，顺序查看表中的下一单元（循环），直到出现一个空闲单元或者查遍全表。（表不为空的时候一定可以找到）
缺点：会造成大量元素在相邻散列地址上聚集起来，大大降低了查找效率。
2.3.1.2 平方探测法
设发生冲突的地址为d，平方探测法得到新的地址序列为d+1²，d-1²，d+2²，d-2²......平方探测法是一种比较好的探测方法，可以避免出现聚集问题。
缺点：不能探测到哈希表上的所有单元，但是至少能探测一半单元。
2.3.1.3 再哈希法
又称双哈希法。需要使用两个散列函数，当通过第一个散列函数Hash(key)得到的地址发生冲突时，则利用第二个散列函数Hash2(key)计算该关键字的地址增量。哈希函数为Hi=(H(key)+i*Hash2(key))%m，其中m是表长，i是冲突次数。 
2.3.1.4 伪随机序列法
发生哈希冲突时，地址增量为随机数序列，称为伪随机序列法。
2.3.2 拉链法
对于不同的关键字可能会通过哈希函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一表示。拉链法是用于经常进行插入和删除的情况。
3 散列表的查找
给定一个关键字key，根据哈希函数计算其哈希地址，然后检查哈希地址有没有关键字。
如果没有，表明该关键字不存在，返回查找失败；
如果有，则检查该记录是否等于关键字，1)如果等于，返回改字，查找成功。2)如果不等，则按照给定的冲突解决办法计算悬疑散列地址，再执行上述过程。
4 散列表查找性能
散列表查找性能跟装填因子有关，一般记为α，定义为一个表的装满程度。计算方法为 α=表中记录数n/表长m
散列表的平均查找长度依赖于散列表的装填因子α，而不直接依赖于n或者m。α越大，表示装天的纪录越满，发生冲突的可能性就大，反之发生冲突的可能性越小`。 
5 实例
5.1 问题描述
设计散列表，实现电话号码查找系统。设电话号码簿长度为n（0≤n≤10000），系统应该实现如下工作：
⑴ 电话号码簿保存在磁盘文件中，每一条电话号码记录包含数据项：编号（唯一），用户名，通信地址，电话号码（手机号）
⑵ 创建散列表：系统运行时，读取磁盘文件的电话号码，构建散列表，用于查询。要求：自选散列函数(至少2种)，自选解决冲突的方法(至少2种)，分别以电话号码和用户名为关键字，建立散列表。
⑶ 查询：根据输入的用户名，查找并显示给定用户的信息。
⑷ 性能分析：
① 计算并输出不同散列函数、不同解决冲突方法的平均查找长度。
② 通过改变装填因子、改变哈希函数等方式，改善平均查找长度：通过数据表、柱形图、折线图等方式，记录实验数据的变化情况，对影响平均查找长度变化的原因进行分析。
5.2 问题分析
以电话号码为关键字建立哈希表，散列函数选用折叠法，将手机号的后八位拆分成两个四位，然后相加再模哈希表长度得到地址。，如图一
​                               
​                                                                                                                   图一
其中，x，y分别是输入手机号后八位的前四位与后四位，10000是哈希表的长度。
以姓名为关键字建立哈希表，哈希函数选用平方取中法，由于我生成的随机数据中姓名是由4个字符组成，因此计算四个字符与’a’的差值再乘10/27得到一个4位10进制数字，即是散列地址。具体操作如图二
初始散列因子为0.7，哈希表长度是10000，数据量是7000条。
解决冲突办法分别是1.线性探测法，即出现冲突线性寻找下一个非空位置放数据，缺点是容易产生数据堆积。2.其次是平方探测法，平方探测法得到新的地址序列为d+1²，d-1²，d+2²，d-2²……计算如图三
5.3 实验结果及分析
（1）实验数据描述
电话簿初始为7000条数据，哈希表长固定为10000，每一条记录包含四个字段，分别是id(唯一)，四位随机字符串姓名，20位随机字符串地址，150开始，后八位随机数字表示电话号码。以txt文件存储在磁盘中，每一行数据就是一条记录，读取/写入一次操作一行。
（2）实验结果
某一次程序输入结果如图四
​                          
α为装填因子，AVL为平均查找长度。
 电话号码为关键字，哈希方法为折叠法，解决冲突方法线性探测法。
 电话号码为关键字，哈希方法为折叠法，解决冲突平方探测法。
 姓名为关键字，哈希方法为平方取中法，解决冲突方法线性探测法。
 姓名为关键字，哈希方法为平方取中法，解决冲突平方探测法。
5.4 结论
结论：根据与图五可知，由于哈希函数和冲突处理方法不同，以及关键字不同，建立哈希表的查找性能也不同，α越大，即表填的越‘满’，查找性能越低，反之查找性能越高。
6 源代码
代码写的渣渣，能测试就行。
实体类：
package com.sufu.data.structure.experiments;

import java.io.Serializable;

/**
 * @author sufu
 * @version 1.0.0
 * @date 2020/5/17 3:27
 * @description 电话号码实体类
 */
public class PhoneNumber implements Serializable {
    private int id;
    private String username;
    private String stress;
    private String phoneNumber;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getUsername() {
        return username;
    }

    public void setUsername(String username) {
        this.username = username;
    }

    public String getStress() {
        return stress;
    }

    public void setStress(String stress) {
        this.stress = stress;
    }

    public String getPhoneNumber() {
        return phoneNumber;
    }

    public void setPhoneNumber(String num) {
        this.phoneNumber = num;
    }

    public PhoneNumber(int id, String username, String stress, String phoneNumber) {
        this.id = id;
        this.username = username;
        this.stress = stress;
        this.phoneNumber = phoneNumber;
    }
    public PhoneNumber(String s){
        String[] info = s.split(",");
        this.id = Integer.parseInt(info[0]);
        this.username = info[1];
        this.stress = info[2];
        this.phoneNumber = info[3];
    }

    @Override
    public String toString() {
        return id+","+username+","+stress+","+phoneNumber;
    }
}
主函数：
package com.sufu.data.structure.experiments;

import java.io.*;
import java.util.Date;

/**
 * @author sufu
 * @version 1.0.0
 * @date 2020/5/17 3:29
 * @description
 */
public class Main {
    static char[] CHARS = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N', 'O','P','Q','R','S','T','U','V','W','X','Y','Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
    static char[] NUMS = {'0','1','2','3','4','5','6','7','8','9'};
    static String FILE_PATH = "C:UsersDELLDesktop数据结构";
    static int DATA_SIZE = 8000;//数据大小
    static int HASH_TABLE_LENGTH = 10000;//哈希表长
    static int HASH_TYPE = 1;//哈希方法选用类型 1或非1
    static int DEAL_TYPE = 2;//冲突处理方法选用类型 1或非1
    static double CPMPARETIMES = 0;
    static int ADDR = 1;//解决冲突方法2中的地址增量
    static boolean ISADD = false;//结局冲突方法2中是否是加号
    public static void main(String[] args) {
        System.out.println("创建随机数据.....");
        getRandomData();//创建DATA_SIZE条测试数据,输出创建时间
        System.out.println("初始化哈希表中..............");
        PhoneNumber[] hashTable = init();//创建并返回哈希表
        System.out.println("初始化完成！");
//        int op;
//        while(true){
//            System.out.println("欢迎使用！ 输入编号执行响应操作：n1.根据电话号码查找 2.根据姓名查找 3.性能分析n输入-1结束");
//            Scanner scanner = new Scanner(System.in);
//            op = scanner.nextInt();
//            if(op == 1){
//                System.out.println("请输入电话号码：");
//                String s = scanner.next();
//                PhoneNumber result = search(s, hashTable);
//                if(result!=null){
//                    System.out.println(result);
//                }else
//                    System.out.println("查找失败，没有该用户！");
//                System.out.println("比较次数："+compareTimes);
//            }else if(op == 2){
//                System.out.println("2");
//            }else if(op == -1)
//                break;
//            else
//                System.out.println("输入有误");
//        }
        PhoneNumber[] original = readFromDisk();//源数据
        for(int i =0;i<DATA_SIZE;i++){
            if(search(original[i].getPhoneNumber(),hashTable)==null){
                System.out.println("false");
            };
        }
//        for(int i =0;i<DATA_SIZE;i++){
//            if(search(original[i].getUsername(),hashTable)==null){
//                System.out.println("false");
//            };
//        }
        System.out.println(CPMPARETIMES /DATA_SIZE);

    }
    static PhoneNumber search(String key,PhoneNumber[] hashTable){
        int index;
        if(HASH_TYPE == 1){
            index = hash1(key);
        }else {
            index = hash2(key);
        }
        while(true){
            PhoneNumber re =  hashTable[index];
            CPMPARETIMES++;
            if(re == null){
                return null;
            }
            else if(re.getPhoneNumber().equals(key)){
                return re;
            }else {
                if(DEAL_TYPE == 1){
                    index = deal1(index);
                }else {
                    index = deal2(index);
                }
            }
        }
    }
    public static PhoneNumber[] init(){
        PhoneNumber[] data = readFromDisk();
        PhoneNumber[] hashTable = new PhoneNumber[HASH_TABLE_LENGTH];
        String num;
        int index,count = 0;
        for(int i =0;i<data.length;i++){
            num = data[i].getPhoneNumber();
            if(HASH_TYPE==1){
                //选择第一个哈希函数
                index = hash1(num);
            }else {
                //否则是第二个哈希函数
                index = hash2(num);
            }
            while(true){
                if(hashTable[index]==null){
                    //无冲突 直接存放数据
                    hashTable[index] = data[i];
                    break;
                }else {
                    if(DEAL_TYPE == 1){
                        index = deal1(index);
                    }else {
                        index = deal2(index);
                    }
                }
            }
        }
        saveItemsToDisk(FILE_PATH+"test.txt",hashTable);
        return hashTable;
    }
    public static String getRandomString(Integer len,char[] chars){
        char[] chrs = new char[len];
        int index = 0;
        for(int i=0;i<len;i++){
            index = (char) (Math.random()*chars.length);
            chrs[i] = chars[index];
            }
        return String.valueOf(chrs);
    }
    public static void saveItemsToDisk(String path,PhoneNumber[] items){
        File file = new File(path);
        if(file.exists()){
            file.delete();
        }
        try {
            file.createNewFile();
            FileWriter fileWriter = new FileWriter(file);
            PrintWriter printWriter = new PrintWriter(fileWriter);
            for (PhoneNumber item : items) {
                printWriter.println(item);
            }
            printWriter.close();
            fileWriter.close();

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    public static void  getRandomData(){
        Date date1 = new Date();
        int index = 0;
        PhoneNumber[] items = new PhoneNumber[DATA_SIZE];
        for (int i=0;i<items.length;i++) {
            items[i] = new PhoneNumber(index+","+getRandomString(4,CHARS)+","+getRandomString(20,CHARS)+","+"150"+getRandomString(8, NUMS));
            index++;
        }
        saveItemsToDisk(FILE_PATH+"data.txt", items);
        Date date2 = new Date();
        System.out.println(date2.getTime()-date1.getTime()+"ms");
    }
    public static PhoneNumber[] readFromDisk(){
        PhoneNumber[] phoneNumber = new PhoneNumber[DATA_SIZE];
        File filePath = new File(FILE_PATH+"data.txt");
        if (filePath.exists()){
            try {
                FileReader fileReader = new FileReader(filePath);
                BufferedReader reader = new BufferedReader(fileReader);
                for (int i=0;i<DATA_SIZE;i++){
                    phoneNumber[i] = new PhoneNumber(reader.readLine());
                }
                return phoneNumber;
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return null;
    }
    static int hash1(String input){
        //折叠法，输入电话号码后八位，得到索引，此法只针对输入电话号码查找
        //input = input.substring(3, 11);//取后八位
        int x = Integer.parseInt(input.substring(0, 4));//去后八位中的前四位
        int y = Integer.parseInt(input.substring(4, 8));//取后八位中的后四位
        return (x+y)%HASH_TABLE_LENGTH;
    }
    static int hash2(String input){
        //平方取中法，输入四个字符，计算每个字符与字符a的差值做平方再取中间四位
        int index = 0;
        for(int i =0;i<input.length();i++){
            index = index + (int)((input.charAt(i)-'a')*10/27*Math.pow(10,3-i));
        }
        index*=index;
        return (index/100)%HASH_TABLE_LENGTH;
    }
    static int deal1(int input){
        //线性探测法解决冲突
        return ++input%HASH_TABLE_LENGTH;
    }
    static int deal2(int input){
        //平方探测法解决哈希冲突
        if(ISADD){
            input = input+ADDR*ADDR;
            ADDR++;
        }else
            input = (HASH_TABLE_LENGTH+input-ADDR*ADDR)%HASH_TABLE_LENGTH;
        return input;
    }
}

开放寻址是其中一种缓解散列冲突的编程技术，当使用开放寻址作为冲突解决技术时，键值对存储在表(数组)中，而不是像单独链表那样的数据结构中。这意味着我们需要时刻留意哈希表的尺寸以及当前表中已有的元素数量。因为一旦哈希表中有太多元素，也将很难找到可用的位置来存放我们新插入的元素，因此这里我们需要引入一个重要的术语，负载系数(Load Factor)
负载系数

其实就是表中已有元素个数和表尺寸的比例，我们要密切关注这个系数的是因为哈希表的O(1)恒定时间行为假设负载因子k保持一定的固定值，这意味着一旦k>阈值，我们就需要增加表的大小(理想情况下是指数增长，例如，两倍)

在上图中，你会看到有两种缓解冲突的方法，即单独链表和线性探测(Linear Probing),在开放寻址(线性探测)技术看来，一旦达到某个阀值，它的时间复杂度就会呈现指数级恶化的趋势
当我们想要将键值对插入哈希表时，我们对键进行哈希处理并获得该键值对所属位置的原始位置。如果我们的键被散列到的位置被占用(此时出现了冲突)，对于开放寻址来说，同一个位置中不允许有两个键的，这不是数组的工作方式，我们要做的是使用一个探测序列函数(Probing Seque Function) 这里简称p(x)，因为我们已从散列函数获取了冲突点的所在位置，现在我们使用p(x)进行探测直到在沿途发现一个空闲的位置为止
探测函数
您可以提出无限数量的探测序列，这里仅提及一些常见的探测函数：
线性探测(Linear Probing)：p(x)= kx + b其中a，b是常数
二次探测(Quaratic Probing):p(x)= ax ^ 2 + bx + c，其中a，b，c是常数
双重散列(Double Hashing):p(k，x)= x * h(k)，其中h(k)是辅助s散列函数
伪随机数发生器(Pseudo Random Number Generator): p(k，x)= x*RNG(h(k),x)其中RNG是以H(k)作为种子的随机数生成器函数
本篇仅介绍线性探测函数进行线性探测，因此给定输入参数x,当我们进行探测时，我们通常会将变量x初始化为0或1作为一个起点,如果我们找不到空闲的位置，会依次将x增加1,对以上所有这些探测函数都是一样的
开放寻址的通用算法
接下来，这是一个通用的开放寻址插入算法，假设我们有一个表的尺寸为n,开放寻址算法首先会初始化变量x=1,因为x是一个变量，我们要用它来探测，每当我们未能到达闲置的位置时，都需要递增x，然后我们通过散列函数获得keyHash,而实际上我们首先要查看表的索引，当表索引被占用意味着它不为空，那么新索引就是我们散列的最初位置(keyHash所指向的起始索引)加上探测函数的总和再于表尺寸N取模运算得到整数，由于我们总是回到表里，在循环中要递增x。下一次当我们在不同的位置探测时，在while循环中，最终我们会找到一个空闲的位置
x=1keyHash=h(k)index=keyHashwhile table[index]!=NULL:      index=(keyHash+p(k,x)) mod N      x=x+1insert(k,v,index) 
死循环地狱(Chaos with Cycle)
由于我们知道负载系数被控制在一定的范围内，所以这里有个问题，就是开放寻址中的探测函数存在缺陷--死循环地狱,以表尺寸N为模的大多数随机选择的探测序列将产生比表大小N更短的循环。当您尝试插入一个键-值对并且循环中的所有存储桶都被占用时，这将成为灾难性问题，因为您将陷入无限循环,这在一些老外谈及哈希表的相关文章中有一个非常有趣的昵称叫死循环地狱(Chaos with Cycle)
为了生动说明什么叫死循环地狱,我们这里看一个例子，这里有一个尺寸为12的哈希表，并且使用开放寻址插入了一些键值对，，该哈希表已经部分填充。 占用的单元格填充有键值对(Ki，Vi)和带有空令牌Φ的空单元格，如下图所示
假设我们使用探测序列函数p(x)=4x，并且在表中插入一个新的键值对，并且该键值对的散列值为8,即h(x)=8这意味着我们会在索引8的位置插入该键值对，但是该位置已被占用，因为这里已经有简直对(k5,v5)，所以我们该怎么办呢？接下来，我们需要进行探测，所以我们计算： index=h(k)+p(1)=8+4 mod 12=0
此时，如下图，此时探测函数会跳转到索引为0的位置，糟糕的是索引1的位置也被占用了，因为(k1,v1)已经存在.
当x=2时，即index=h(k)+p(2)=(8+8) mod 12=4，探测函数会跳跃到索引4的位置，同样这里也是被占用的，如此类推
当x=3时,即index=h(k)+p(3)=(8+12) mod 12=8,p(x)跳跃到索引8的位置,该位置被占用
当x=4时,即index=h(k)+p(4)=(8+16) mod 12=0,p(x)跳跃到索引0的位置,该位置被占用
当x=5时,即index=h(k)+p(5)=(8+20) mod 12=4,p(x)跳跃到索引4的位置,该位置被占用
.....
这样尽管我们具有探测函数，但这种特定的情况下它一直在一个死循环里面一直做一些毫无意义的事情。
由这个例子我们可知探测函数存在缺陷，他们产生的周期短于表的尺寸，因此，我们要如何处理产生小于表大小的周期的探测功能？一般来说，一致的看法是我们不处理这个问题，相反，我们通过将探测函数的范围限制在那些产生长度为N的循环的函数上来避免这个问题，我们选择的那些产生的周期正好为N的探测函数，并且这些探测函数确实存在。
线性探测、二次探测和双重散列等技术都受到死循环地狱问题的影响，这就是为什么与这些方法一起使用的探测函数非常特殊的原因。这是一个很大的话题，将是接下来几篇文章会重点讲述这些，我们目前需要做的是重新定义非常具体的探测函数，这些函数会产生一个循环长度为表尺寸N，并且避免无法插入元素或陷入无限循环
注意，开放寻址对使用的哈希函数和探测函数非常敏感。如果使用单独的链接作为冲突解决方法，则不必担心此问题。
小结
我们本篇用一个反例生动地介绍了开放寻址插入算法的底层是由探测函数和散列函数相互作用的结果，同时我们也介绍了一些探测函数的固有缺陷，就是死循环地狱,下一篇我们会详细讨论线性探测函数的原理，敬请期待。

链接：https://www.jianshu.com/p/b8c47701dd07