重温数据结构_散列表/哈希表的查找
基本概念
基于线性表、树表结构的查找方法，这类查找方法都是以关键字的比较为基础的。在查找过程中只考虑各元素关键字之间的相对大小，记录在存储结构中的位置和其关键字无直接关系，其查找时间与表的长度有关，特别是当结点个数很多时，查找时要大量地与无效结点的关键字进行比较，致使查找速度很慢。如果能在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无需做比较或很少次的比较，按照这种关系直接由关键字找到相应记录。这就是散列查找(Hash Search)的思想,它通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。
在记录的存储位置p和它的关键字key之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。建立了关键字与存储位置的映射关系，公式如下：
p = f（key）
这里把这种对应关系f称为散列函数(哈希（Hash）函数)，p为散列地址。详情见：Java中hashCode的作用。
一块连续的存储空间中，用以存储按散列函数计算得到相应散列地址的数据记录。这块连续存储空间称为散列表或哈希表。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。
散列查找法主要研究以下两方面的问题：
- 如果构造散列函数；
- 如何处理冲突。
散列函数的构造方法
直接定址法
可以取关键字的某个线性函数值为散列地址，即：
f(key) = a × key + b
例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。
f(key) = key。
这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合査找表较小且连续的情况。由于这样的限制，在现实应用中不常用。
数字分析法
数字分析法通过适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布比较均匀，就可以考虑用这个方法。
比如11位的手机号"188****8888"，极有可能前7位都是相同的，选择后四位成为散列地址就是不错的选择。
平方取中法
这个方法计算很简单：取关键字平方后的中间几位为哈希地址。
假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227，用做散列地址。
平方取中法比较适合不知道关键字的分布，而位数又不是很大的情况。
折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和作为散列地址。
比如关键字是1234567890，散列表表长为三位，将它分为四组，123|456|789|0，然后将它们叠加求和123 + 456 + 789 + 0 = 1368，再求后3位得到散列地址368。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。
除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key MOD p (p<=m)
这方法不仅可以对关键字直接取模，也可以折叠、平方取中后再取模。
很显然，本方法的关键在于选择合适的p，p如果选不好，就可能会容易产生冲突。
根据前辈们的经验，若散列表的表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。
随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
H(key)=random(key），其中random为随机函数。通常用于关键字长度不等时采用此法。
散列函数的构造方法小结
在实际应用中，应该视不同的情况采用不同的散列函数，这里只能给出一些考虑的因素来提供参考：
- 计算散列地址所需的时间
- 关键字的长度；
- 散列表的长度；
- 关键字的分布情况；
- 记录查找的频率。
综合以上等因素，才能决策选择哪种散列函数更合适。
处理散列冲突的方法
无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，有一些方法可以避免冲突。
开放定址法(重要)
开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。
- 如果di值可能为1,2,3,...m-1，称线性探测法。
- 如果di取值可能为1,-1,4,-4,9,-9,16,-16,...kk,-kk(k<=m/2）
称二次探测法。 - 如果di取值可能为伪随机数列。称伪随机探测法。
开发定址法处理流程请见：散列冲突处理：开放定址法
总结：
开放定址法的思路就是一旦发生了冲突，就去寻找下一个空的散列地址。
链地址法(拉链法)(重要)
链地址法：简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。
具有相同函数值的关键字对该散列函数来说称作同义词。
将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。
JDK1.8之前HashMap底层结构就是哈希表，并且处理散列冲突的方法使用的是拉链法。
拉链法详情请见：散列冲突处理：链地址法
公共溢出区法
为所有冲突的关键字建立一个公共的溢出区来存放。
在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表中进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。
