1 散列表查找定义
- 散列技术：是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f (key)。
- 散列函数：对应关系 f 。又称为哈希 (Hash) 函数。
- 散列表：采用散列技术存储记录的一块连续的存储空间。又称为哈希表 (Hash table) 。
- 散列地址：关键字对应的记录存储位置
2 散列表查找步骤
- 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。
- 当查找时，通过同样的散列函数计算记录的散列地址，按此散到地址访问该记录 。
散列技术最适合的求解问题是查找与给定值相等的记录。
不适合一个关键字对应很多记录，不适合范围查找
- 散列冲突：两个关键字 key1 != key2，但是却有 f(key1) = f(key2)
3 散列函数的构造方法
好的散列函数两个原则：
- 计算简单
- 散列地址分布均匀
如果关键字是字符串，可以（通过ASCII 码或者 Unicoæ 码等）转化为某种数字来对待
1 直接定址法
需要事先知道关键字的分布情况，适合查找表较小且连续的情况。简单，但不常用。
取关键字的某个线性函数值为散列地址，即 f(key) = a * key + b （a、b 为常数）。
2 数字分析法
适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。
抽取方法是使用关键字的一部分来计算散列存储位置的方法
3 平方取中法
平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。
先平方，再取中间几位
4 折叠法
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。
折叠法是将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
有时可能这还不能够保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。
5 除留余数法
最常用的构造散列函数方法。
对于散列表长为 m 的散列函数公式为: f(key) = key mod p (p <= m)
不仅可以对关键宇直接取模，也可在折叠、 平方取中后再取模。
根据前辈们的经验，若散列表表长为 m ， 通常 p 为小于或等于表长(最好接近 m ) 的最小质数或不包含小于 20 质因子的合数。
6 随机数法
合适关键字的长度不等。
选择一个随机数（伪随机），取关键字的随机函数值为它的散列地址。也就是 f(key) = random(key) 。
4 处理散列冲突的方法
1 开放定址法
开放定址法就是一旦发生了冲突， 就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
$f_i( key ) = ( f ( key ) + d_i ) MOD m$
- 线性探测法
冲突后加1再mod：$d_i = 1,2,3.....,m-1$ - 二次探测法
增加平方运算，避免关键字聚集：$d_i=1^2,-1^2, 2^2,-2^2,…, q^2,-q^2,q<= m / 2$ - 随机探测法
冲突时，采用随机函数计算位移量$d_i$
2 再散列函数法
事先准备多个散列函数，每当发生散到地址冲突肘，就换一个散列函数计算
3 链地址法
将所有关键字为同义词的记录存储在一个单链表中，在散列表中只存储所有同义词子表的头指针。
4 公共溢出区法
为所有冲突的关键字建立了一个公共的溢出区来存放
在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找。
5 散列表查找实现
散列表的装填因子 = 填入表中的记录个数 / 散列表长度。