7.5.3_2处理冲突的方法-开放定址法
知识总览：
开放定址法：
定义：发生冲突之后，给新元素另找一个位置存储。
一个散列地址既可以存储同义词，也可以存储非同义词
开放定址法的基本原理：
开放定址法即通过构造冲突散列地址来存储冲突时的同义词，而冲突散列地址的构造需要相对偏移量，相对偏移量的构造有如下后续的4种方法，相对偏移量是一个探测序列，每次发生冲突时偏移量值不同。
相对偏移量di:
di表示第i次发生冲突时，下一个探测地址与初始散列地址的相对偏移量。比如说如下散列表的第1号位置上存储了14，此时为d0，且d0=0即没有冲突则探测地址与初始散列地址相对偏移量为0，然后元素1经过散列函数得出1也存散列表的第1号位置，即d1第1次冲突，然后假如说把1可以存储到2号位且2号位地址上是空的，则d1=1即2号位地址与初始散列地址1号位相对偏移量为1，此时2号位满了，假如下一个元素17也计算得出要存在1号位，即d2第2次冲突，此时2号位满了不能存了，则按照某种规则可以把17存储到1号位左边0号位位置，则d2=-1即0号位置相对初始散列地址1号位的相对偏移量为-1(因为向右偏移为+，向左偏移为-)
如何找另一个空闲位置(即冲突散列地址)：
发生第i次冲突时的散列地址:
Hi=(H(key)+di)%m。即经过散列函数得到初始散列地址+冲突偏移量然后再对散列表长取余，这样是为了让计算得出的散列地址不超过散列表长
4种探测序列(又叫增量序列)构造偏移量，不同序列构造的偏移量不同，但是4种探测序列的d0=0即表示没有冲突是初始散列地址，则偏移量为0，每种探测序列下标都从0开始，且下标i<=m-1，因为散列表表长为m,当探测了从d0~dm-1这些位置之后，相当于探测了m个地址，因此i的取值范围是0<=i<=m-1(主要是d是从0开始的，所以当m个地址被占满了那肯定现在d是m-1）
线性探测法(插入、查找)：
探测序列：di=0,1,2,3,4,,,,,,,,,,,m-1
假如说插入元素1：
已知散列表表长m=13，H(key)=key%13 H(1)=1%13=1
由探测序列知d0=0,H0=(H(1)+d0)%m=(1+0)%13=1， 发生冲突第1次，因为1号位上已经有元素14了
由探测序列知d1=1,H1=(H(1)+d1)%m=(1+1)%13=2，发生冲突第2次，因为2号位上已经有元素2了
由探测序列知d2=2,H2=(H(1)+d2)%m=(1+2)%13=3，发生冲突第3次，因为3号位上已经有元素15了
由探测序列知d3=3,H2=(H(1)+d3)%m=(1+3)%13=4，未发生冲突，因为4号位上没有元素，可以把1存储在4号位，则插入4号位
查找和插入类似，即找目标元素在散列表中的什么位置：
1.先通过散列函数计算出目标元素初始散列地址，比如查找元素27，计算初始散列地址为1
2.如果初始散列地址上的元素值和目标元素不一致，则说明如果目标元素在散列表中存在则一定存在冲突散列地址上，所以再根据探测序列依次算出冲突散列地址并对比其上的存储单元的关键字是否和目标元素相等，若探测到目标关键字，则查找成功，若探测到空单元，则查找失败。即在探测序列中依次比较14≠27，2≠27，15≠27，1≠27，然后再比较就是下一个存储单元是空值则查找失败（就是根据探测序列查找冲突散列地址，然后去比较冲突散列地址上的元素值，如果相等说明查找成功，如果不相等且在比较的时候一直比较直到冲突散列地址上出现了空单元，则代表查找失败）
平方探测法(插入、查找)：
探测序列：di=0²，1²，-1²，2²，-2²，...........，k²，-k² k<=m/2
假如说插入元素1：
已知散列表表长m=13，H(key)=key%13 H(1)=1%13=1
由探测序列知d0=0²,H0=(H(1)+d0)%m=(1+0)%13=1， 发生冲突第1次，因为1号位上已经有元素14了
由探测序列知d1=1²,H1=(H(1)+d1)%m=(1+1)%13=2，发生冲突第2次，因为2号位上已经有元素2了
由探测序列知d2=-1²,H2=(H(1)+d2)%m=(1-1)%13=0，发生冲突第3次，因为0号位上已经有元素13了
由探测序列知d3=2²,H2=(H(1)+d3)%m=(1+4)%13=5，未发生冲突，因为5号位上没有元素，可以把1存储在5号位，则插入5号位
查找和插入类似：
估摸上同线性探测法，也是先根据散列函数算出初始散列地址，如果不匹配，再根据探测序列求出冲突散列地址(因为如果初始散列地址上的元素不匹配的话，这个目标元素一定存储在冲突散列地址上)，再依次比较冲突散列地址上的数据元素，如果找到相等的说明查找成功，如果找不到且一直比较直到冲突散列地址上出现了空单元，则代表查找失败，出现空单元就是估摸这些冲突散列地址上的数查找结束到末尾了吧，直到查找结束也没找到目标元素即查找失败
双散列法(插入、查找)：
探测序列：di=i*另外一个散列函数计算的值即di=i*H2(key)，感觉一般题目中会给出另外一个散列函数吧(散列表中的每个元素所计算出来的探测序列都不一样，因为H2跟key有关，而key一般应该不同，所以每个元素应该基本都会有一个探测序列吧)
假如说插入元素1：
已知散列表表长m=13，H(key)=key%13 H(1)=1%13=1，另外一个散列函数H2=13-(key%13)=12
由探测序列知d0=0*12=0,H0=(H(1)+d0)%m=(1+0)%13=1， 发生冲突第1次，因为1号位上已经有元素14了
由探测序列知d1=1*12=12,H1=(H(1)+d1)%m=(1+12)%13=0，发生冲突第2次，因为0号位上已经有元素13了
由探测序列知d2=2*12=24,H2=(H(1)+d2)%m=(1+24)%13=12，发生冲突第3次，因为12号位上已经有元素12了
由探测序列知d3=3*12=36,H2=(H(1)+d3)%m=(1+36)%13=11，未发生冲突，因为11号位上没有元素，可以把1存储在11号位，则插入11号位
查找和插入类似：上同
伪随机序列法(插入、查找)：
探测序列：di是一个伪随机序列，由人为程序员给出
假如说插入元素1：
已知散列表表长m=13，H(key)=key%13 H(1)=1%13=1，题目中给的伪随机序列为0,5,3,11.......
由伪随机序列知d0=0,H0=(H(1)+d0)%m=(1+0)%13=1， 发生冲突第1次，因为1号位上已经有元素14了
由伪随机序列知d1=5,H1=(H(1)+d1)%m=(1+5)%13=6，发生冲突第2次，因为6号位上已经有元素19了
由伪随机序列知d2=3,H2=(H(1)+d2)%m=(1+3)%13=4，未发生冲突，因为4号位上没有元素，可以把1存储在4号位，则插入4号位
查找和插入类似：上同
如何删除一个元素：
给定目标元素，要求在散列表中删除该元素，则需要先在散列表中查找到该元素，如果用的是开放定址法解决冲突，则题目中一定会说用了哪种探测序列，则再根据题目中的给定的探测序列去确定目标元素的地址，如果目标元素在散列表中存在，则删除目标元素，如果根据探测序列没找到目标元素，则就不用删除了吧。。。。。。。。
线性探测法删除元素：
删除目标元素15，先在散列表中找15位置，计算初始散列地址为H(15)=15%13=2,2号位上元素为12不匹配，则如果15存在一定在冲突散列地址上，根据线性探测法找冲突散列地址，H(1)=(2+1)%13=3，即下一个冲突散列地址是3号位，3号位上的是15==15，则查找成功(为啥直接找H(1)不找H(0)，是因为冲突散列地址公式为H(i)=(H(key)+di)%m，所有探测序列的d0=0，即初始散列地址就相当于是冲突散列地址的第一个位置，已经确定了初始散列地址上不是目标元素了，那就直接找下一个冲突散列地址)，然后删除3号位上的15元素，即此时在冲突散列地址上3号位上是空单元，但是可能下一个冲突散列地址上的存储单元并不为空，会影响查找。
特别注意关于删除操作1：
如上删除操作把3号位的15删除了，然后现在查找目标元素1，先找初始散列地址上1号位为14即1≠14，则根据线性探测序列匹配冲突散列地址上的元素，i=1，冲突散列地址为H1=2号位=2≠1，继续查找下一个，i=2，H2=3号位=空单元，查找失败，但是实际上目标元素1是存储在3后边的冲突散列地址4上，即查找出现问题
删除元素操作改进：
在进行散列表上元素删除时，要进行逻辑删除，不管用的是哪种探测序列法都要逻辑删除，而非物理删除，即给当前删除元素的位置上打个删除标记即可，这样是为了查找的精确性
删除改进后的查找：
还是如上删除改进前的操作查找元素1，不同的是在查找到3号位时，因为3号位已经标记上是逻辑删除标记，则即使3号位是空单元，依然会向后查找下一个冲突散列地址，即i=3,H3=4号位=1==1，即查找成功
特别注意关于删除操作2：
新元素可以插入到已经被逻辑删除的元素的位置，但是在查找的时候还要经过这些元素，比如如下图假如目标元素1前边的冲突散列地址上的元素都已经被逻辑删除了，但是还要从第一个冲突散列地址上开始查找目标元素1，则效率低下，即散列表看起来很满，但是实际很空，所以为了提高效率，则建议定期清理数据，即把已经逻辑删除的元素全都真正物理删除，然后把实际还存储在散列表中的数据根据要求的探测序列再重新放到该放的位置上，则散列表在查找的时候就不用再经过逻辑删除元素了。
知识回顾：
拓展：
只有线性探测法能覆盖到所有地址
线性探测法是只要散列表中有一个空闲地址，则最多经历m-1次冲突就可探测完整个散列表，因为最后一个空闲地址没发生冲突所以不算吧，并且因为在计算冲突散列地址时，如下即使初始散列地址为5，m=8，因为有取余操作，所以随着i冲突次数不断的增大，最终取余也会把空闲地址覆盖到，即只要有空闲地址，最终都会插入成功。。。。。
平方探测法能不能覆盖到所有(空闲)地址跟表长有关，即在某些情况下，即使散列表中有空位，元素也不能插入成功，如下当散列表长度m是一个4j+3的素数时，平方探测法就能覆盖到所有位置，否则，一般平方探测法只能覆盖到基本散列表至少一半的位置
双散列法能不能覆盖到所有(空闲)地址跟另外一个散列函数有关，一般不能全覆盖到即会出现和平方探测一样的问题，即使散列表中有空闲位置，但是元素也不能被插入，除非经过另外一个散列函数计算得出的值与散列表长m互质(即计算得出的值与m只有公因子1)，就能保证可以覆盖到所有地址，一般常用套路为令表长m本身是质数，让另外一个散列函数=m-key%m(则另外一个散列函数不管key是几得出来的值是几都<=m，确实是，因为被减数<=m)，则无论key值是多少，另外一个散列函数得出的值都和m互质。可能吧。。。。。。。。。
伪随机序列法能不能覆盖到所有地址和人为设计的伪随机序列有关，就看你伪随机序列设计的咋样了
。。。。。。。。。。又写得啰嗦了。。。。。。。。。。