04、散列表查找算法

散列表查找算法(线性探测法)

下面我们来看一下散列表查找算法的实现

首先需要定义散列列表的结构以及一些相关常数，其中 elem 代表散列表数据存储数组，count 代表的是当前插入元素个数，size 代表哈希表容量，NULLKEY 散列表初始值，然后我们如果查找成功就返回索引，如果不存在该元素就返回元素不存在。

我们将哈希表初始化，为数组元素赋初值。

插入操作的具体步骤：

（1）通过哈希函数（除法散列法），将 key 转化为数组下标

（2）如果该下标中没有元素，则插入，否则说明有冲突，则利用线性探测法处理冲突。详细步骤见注释

查找操作的具体步骤：

（1）通过哈希函数（同插入时一样），将 key 转成数组下标

（2）通过数组下标找到 key 值，如果 key 一致，则查找成功，否则利用线性探测法继续查找。

下面我们来看一下完整代码

散列表性能分析

如果没有冲突的话，散列查找是我们查找中效率最高的，时间复杂度为 O(1),但是没有冲突的情况是一种理想情况，那么散列查找的平均查找长度取决于哪些方面呢？

1.散列函数是否均匀

我们在上文说到，可以通过设计散列函数减少冲突，但是由于不同的散列函数对一组关键字产生冲突可能性是相同的，因此我们可以不考虑它对平均查找长度的影响。

2.处理冲突的方法

相同关键字，相同散列函数，不同处理冲突方式，会使平均查找长度不同，比如我们线性探测有时会堆积，则不如二次探测法好，因为链地址法处理冲突时不会产生任何堆积，因而具有最佳的平均查找性能

3.散列表的装填因子

本来想在上文中提到装填因子的，但是后来发现即使没有说明也不影响我们对哈希表的理解，下面我们来看一下装填因子的总结

装填因子 α = 填入表中的记录数 / 散列表长度

散列因子则代表着散列表的装满程度，表中记录越多，α 就越大，产生冲突的概率就越大。我们上面提到的例子中 表的长度为 12，填入记录数为 6，那么此时的 α = 6 / 12 = 0.5 所以说当我们的 α 比较大时再填入元素那么产生冲突的可能性就非常大了。所以说散列表的平均查找长度取决于装填因子，而不是取决于记录数。所以说我们需要做的就是选择一个合适的装填因子以便将平均查找长度限定在一个范围之内。