Hash表和Hash冲突_线性hash表的冲突次数

Hash表中的元素存储地址是通过Hash函数计算出来的，当要取出指定元素的时候，直接通过Hash函数计算出元素的存储地址。有时候会出现KEY不同，但是通过Hash函数计算出来的值相同，这个值相同意味着这两个KEY要存在同一位置，这显然不对，这就是Hash冲突。
Hash函数有多种构造方法，常见的有直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等，这里选择除留余数法。
解决Hahs冲突也有多种方法，比如：开放定址法、再哈希法、链地址法、建立一个公共溢出区等。这里重点介绍两种，线性探测法和链地址法。
Hash表的装载因子 = 关键字总数/哈希表的长度。比如关键字总数为7，Hash表长度为10，那么装载因子为0.7。

线性探测法

当碰到Hash冲突的时候，多次散列，线性探测存储位置。对于关键字$K_i$，求得Hash函数的值$H_i$，但是在地址$H_i$处已经存放了元素，那么在$H_i$继续散列，求$H_{i+1}$，$H_{i+1}$ = （$H_i$ + 1）%L，直到遇到空白存储区。
成功时的平均查找长度为每个元素的散列次数的总和/元素总数；
失败时的平均查找长度为0~L-1的查找次数的总和/Hash表长度。失败的查找意思就是这个元素注定在该表中找不到，所以在遇到空白存储区之前会一直往下查找，遇到空白存储区停止，因为如果这个数真的存在那么一定会存在空白存储区，遇到空白存储区还没有找到说明不存在，这个时候就可以停止查找了。

链地址法

该方法解决Hash冲突的策略是，遇到地址相同的关键字就把它链接到已经存在的关键字后面，求失败时的查找长度时不用遍历所有Hash值，只用遍历本Hash值上的所有元素即可。

本Markdown编辑器使用[StackEdit][6]修改而来，用它写博客，将会带来全新的体验哦：

参考

链地址法
开地址法
线性探测法
哈希冲突
链地址法