七大查找算法之哈希表查找

       哈希查找是通过计算数据元素的存储地址进行查找的一种方法，是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。

       哈希表查找又叫散列表查找，通过查找关键字不需要比较就可以获得需要记录的存储位置，它是通过在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个 key 对应一个存储位置 f(key)。若查找集合中存在这个记录，则必定在 f(key) 的位置上。

哈希查找的操作步骤：

           ⑴用给定的哈希函数构造哈希表；

           ⑵根据选择的冲突处理方法解决地址冲突；

           ⑶在哈希表的基础上执行哈希查找。

怎么样的才算是好的哈希函数？

      1、计算简单，哈希函数的计算时间（指的是产生地址的时间），不应该超过其他查找技术与关键字比较的时间。        2、 地址分布均匀，尽量让哈希地址均匀分布在存储空间中，这样可以使空间有效的利用。

1、直接定址法

      哈希地址：f(key) = a*key+b  (a,b为常数)

      这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道 key 的分布情况，适合查找表较小并且连续的情况。

2、数字分析法

             比如我们的11位手机号码“136xxxx5889”，其中前三位是接入号，一般对应不同运营公司的子品牌，如130是联通如意            通，136是移动神州行等等。中间四位表示归属地。最后四位才是用户号。

             若我们现在要存储某家公司员工登记表，如果用手机号码作为 key，那么极有可能前7位都是相同的，所以我们选择最后         四位作为 f(key) 就是不错的选择。

3、平方取中法

      故名思义，比如 key 是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为 f(key) 。

4、折叠法

             折叠法是将 key 从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按          哈希表的表长，取后几位作为 f(key) 。

      比如：我们的 key 是 9876543210，哈希表的表长为3位，我们将 key 分为4组，987|654|321|0 ，然后将它们叠加求和                987+654+321+0=1962，再取后3位即得到 f(key) = 962 。

5、除留余数法

      哈希地址：f(key) = key mod p (p