利用线性探测法解决hash冲突

问题背景

　　有一种数据结构，叫做散列表，还有一些称之为“字典”（dict）、“映射”（map）、“哈希”（hash）。

　　这种数据结构有个特点，一般情况下，能在O(1)时间内根据关键字找到要查询的信息（进行一次或者很少次比较），这是因为散列表的底层一般会使用数组实现，利用“散列函数”或者称为“hash函数”，可以计算出该元素应该存到哪个位置，能够让所有的元素均匀分布在数组中，下一次查找的时候，根据散列函数计算出对应的位置，就能找到元素。

　　但是存在一个问题，没有完美的hash函数！！！！也就是说目前不能确定某个元素的位置，且不重复！也就是说，散列可能会存在冲突，比如某个元素通过散列函数计算，确定应该存在下标5的位置，下一次再来一个元素，计算后发现还是存在下标为5的位置，此时就出现了冲突。

　　出现hash冲突后，有多种方式可以解决冲突，比如开放地址法、链地址法（拉链法），本文主要介绍开放地址法的一种——线性探测法。

 

线性探测法的定义

　　根据维基百科对线性探测法的介绍，摘抄如下：

线性探测是一种开放寻址的策略。在这些策略里，散列表的每个单元都存储一对键值对。当散列函数对一个给定值产生一个键，并且这个键指向散列表中某个已经被另一个键值对所占用的单元时，线性探测用于解决此时产生的冲突：查找散列表中离冲突单元最近的空闲单元，并且把新的键插入这个空闲单元。同样的，查找也同插入如出一辙：从散列函数给出的散列值对应的单元开始查找，直到找到与键对应的值或者是找到空单元。

　　讲的通俗一点，就是发现蹲坑的时候发现坑已经被占了，就找后面一个坑，如果后面一个坑空闲，则占用这个空闲的坑；如果后面一个坑也被占了，则一直往后面的坑进行遍历，直到找到空闲的坑，否则就一直憋着。

 

线性探测法的插入过程图解

　　目前有一个长度为8的数组，选择的hash函数是 e.key%8，这个8是指数组的长度（容量），当数组长度发生变化，hash函数也应该变化。

　　

 

 

　　新加入一个元素e1，key为5，hash函数计算出应该存到位置5，因为5%8=5，然后看位置5有没有被占用，发现没有被占用，则将e1存入位置5：

　　

 

　　又加入一个新元素e2，key为13，hash函数计算出也应该存到位置5，因为13%8=5，但是发现位置5已经被占用了，此时就位置6有没有被占用，此时发现位置6没有被占用，则e2就存到位置6了

　　

 

　　此时又来一个e3，key为21，发现还要存到位置5，但是位置5已经被占了，往后看位置6，发现位置6也被占了，再看位置7，位置7空着，所以e3就存到位置7了

　　

 

 

　　此时来了一个e4，key为29，发现还是存到位置4，并且位置5、6、7已经都被占用了，此时只能从头考虑位置0了，发现位置0未被占用，则将e4存到位置0

 

 

 

 　　

　　所以说，上面的数组其实是一个环形数组。

 

 

线性探测法的查找操作

　　现在要查询key为5的元素，通过计算，对应的位置为5，查看位置5的key，发现位置5的key与要查找的key相等，则查找成功，返回e1；

　　如果要查询一个key为13的元素，通过计算key为13，对应位置5，但是位置5的key为5，与13不匹配，此时往后看位置6，发现位置6的key为13，与要查找的key相等，此时查找成功，返回e2即可；

　　如果要查询key为37的元素，通过计算对应位置5，但是位置5的key为5，与13不匹配，往后看位置6的key为13也和37不匹配，一直到位置0，发现e4的key为29，仍旧不匹配要找的37，接着看位置1，发现位置1没有元素，证明数组中没有存key为37的元素，查找失败。

　　

 

线性探测法的删除操作图解

　　以上面插入e4到位置0后进行介绍

　　

 

　　此时要删除一个元素key为13，此时，通过hash计算出位置应该在位置5，因为13%8=5，发现位置5的key为5，不等于要删除的13；

　　往后看位置6，发现位置6的key为13，和要删除的key相同，测试将位置6的元素删除：

　　

　　如果此时不进行其他修改操作，而是进行查找操作，比如查找key为21的元素，应该对应位置5，但是位置5已经有元素了，且不是要找的元素，此时会往后看下一个位置，发现位置6为空，没有元素，所以此次查询失败！！！

　　但是，这次查询是失败的！不是说查询的方式有问题，而是说数组的元素存放有问题，因为key为21的元素在数组中，但是却并没有被查询出来。

　　为了解决这个问题，我们在删除元素后，要将其后面的元素进行重新确定位置，也就是rehash，过程如下：

　　删除位置6的元素，所以看位置6后面的元素，7->0->5，每个元素都需要计算hash，确定新位置。

　　比如位置7的key为21，发现应该调整到位置5，发现位置5已经有了元素，看位置6，发现位置6空着，则将元素e3放入位置6

　　

　　接着看位置0的元素是否需要调整，在进行计算并且经过上面的流程后，e4应该调整到位置7

　　

　　需要注意的是，调整位置0后，由于位置1没有元素，则可以停止调整，因为没有元素，则表示后面的第一个非空位置存的元素（比如e1）肯定没有冲突。

 

线性探测法扩容

　　当数组中所有位置都填满了，此时再插入元素，就无处安放了，此时有两种做法：1.拒绝插入；2.扩容。

　　一般来说，并不是当数组没有空位时才扩容，而是数组元素达到一定阈值后就进行扩容，但是需要注意的是数组扩容要做的不只是数组扩容，还需要将旧数组中的元素拷贝到新数组中。

　　当数组扩容后（假设是翻倍），则数组长度变为16，下标从0~15，如下图所示：

　　

 

 

　　在拷贝的过程中，需要重新计算每个元素的hash值，也就是确定每个元素在新数组中的位置，其实从左往右遍历旧数组当中的元素，依次插入到新数组中，有冲突就按照原来的方式解决冲突即可。

　　扩容后，新的散列函数为e.key%16：

　　首先是看位置0，有元素，元素e4的key为29，则新位置为13，因为29%16=13，发现新数组的位置13空着，于是e4元素就放入位置13；

　　然后从左往右遍历到e1，发现元素e1的key为5，5%16=5，所以新位置为5，刚好位置5也空着，所以e1放入位置5；

　　然后轮到e2，计算的key应该保存到13，13%16=13，应该放到位置13上，但是位置13上已经有了元素，往后看位置14，发现位置14空着，于是e2就放入位置14

　　.....所有元素都完成拷贝后，数组的扩容才真的完成，如下图所示：

　　

 

 

　　

 

　　

　

　　

• 还没有人评论，欢迎说说您的想法！