数据结构与算法之散列查找

散列表

下面是几种已知的查找方法，右边是他们的时间复杂度。

时间复杂度最好也只是O(N)，有没有一种查找方式可以一找就找到呢，有，那就是散列查找散列查找的关键就是创建散列表。
散列表：是实现字典操作的一种有效数据结构。最坏查找时间为O(n)，理论上可以达到的平均查询时间是O(1)。散列表是普通数组概念的推广，当实际存储的关键字数目比全部的可能关键字总数要小时，采用散列表就成为直接数组寻址的一种有效替代，因为散列表使用一个长度与实际存储的关键字数目成比例的数组来存储。在散列表中，不是直接把关键字作为数组的下标，而是根据关键字计算出相应的下标。散列：是一种极其有效和实用的技术，基本的字典操作平均只需要O(1)的时间。散列冲突，就是指多个关键字映射到数组的同一个下标。

先来看第一项

构造散列函数

直接定址法（不常用）除留余数法（最常用）

数字分析法（适合于关键字位数较大的情况）
平方取中（适合于位数不是很大的情况）折叠法（适合于关键字位数较多的情况）
**

有一类比较独立的散列查找就是字符串的哈希，参考我以前的文章

**（点击进入）

处理散列冲突的方法

一、开放定址法
一旦产生了冲突（所选地址已有其他元素），就按照某种规则（改变di的规则，共有三种）去寻找另一地址。

线性探测最简单，发现冲突后直接将di往后移一位看是否还冲突，如果是则继续后移。但也是这么一种简单的解决办法，导致出现了聚集现象（每次只移一位，冲突的多了就都在那一坨了），这会导致以后对散列表插入和查找造成不便。


二、再散列函数法
对于我们的散列表来说，我们事先准备多个散列函数。这里讲的再散列就是重复用不同的散列函数，你可以把我们前面说的什么除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉。这种方法能够使得关键字不产生聚焦，当然，相应地也增加了计算的时间。
三、链地址法
思路还可以换一换，为什么有冲突就要换地方呢，我们直接就在原地想办法不可以吗？于是我们就有了链地址法。将冲突的元素接在当前位置的单链表的最后一个元素后面，在散列表中只存储单链表的头节点。

散列表查找性能分析

如果没有冲突，散列查找是所有查找算法中效率最高的，因为它的时间复杂度为0(1)。
然而没有冲突的散列只是一种理想，在实际的应用中，冲突不可避免。那么散列查找的平均查找长度取决于哪些因素呢？
散列函数是否均匀
散列函数的好坏直接影响着出现冲突的频繁程度，不过由于不同的散列函数对于同一组随机的关键字产生冲突的可能性是相同的，因此我们可以不考虑它对平均查找长度的影响。
处理冲突的方法
相同的关键字，相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法（di = 1,-12,2,-22,···m/2，在冲突点前后两个方向定址）好，而链地址法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。
散列表的装填因子
所谓的装填因子α=填入表中的记录个数/散列表长度。α标志着散列表的装满程度。当填入表中的记录越多，α就越大，产生冲突的可能性就越大。也就是说，散列表的平均查找长度取决于装填因子，而不是取决于查找集合中的记录个数。不管记录个数有多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内，此时我们散列查找的时间复杂度就真的是0(1)了。为了做到这一点，通常我们都是将散列表的空间设置得比查找集合大，此时虽然是浪费了一定的空间，但换来的是查找效率的大大提升，总的来说，还是非常值得的。