哈希表查找
哈希查找是通过计算数据元素的存储地址进行查找的一种方法，是一种以 键-值(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<=m) m为哈希表表长。
这种方法是最常用的哈希函数构造方法。
事实上，如果p选得不好，就很容易出现同义冲突的情况：
如上图所示，选择p=11，就会出现key=12、144的冲突。
若哈希表表长为m，通常p为小于或者等于表长的最小质数或不包含小于20质因子的合数。
6、随机数法
哈希地址：f(key) = random(key)
这里 random 是随机函数，当 key 的长度不等时，采用这种方法比较合适。
哈希函数冲突：
影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时，就会发生冲突。为减少发生冲突的可能性，哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。解决冲突的方法有以下两种：
1、开放定址法：
如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。
当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。容易造成冲突的堆积。
2、链地址法：
将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。这样的好处是，不怕冲突多；缺点是降低了散列结构的随机存储性能。本质是用单链表结构辅助散列结构的不足。
