基本概念

散列表查找(K -- V)。
存储位置 = f(关键字) 查找的时候根据key的映射f(key)找到值存储的位置。

构造散列函数。

1. 直接定制法。

f(key) = a x key + b（a b 为常数）

2. 数字分析法。

   通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀。

3. 平方取中法。

比较适合不知道关键字的分布，而位数又不是很大的情况。

if  key == 1234;
     key^2 == 1522756
  address = 227

4. 折叠法。

适合关键字位数比较多的情况。

以适当的位数分割整个关键字，然后分割出来的数进行相加。

5. 除留取余数发。

f(key) = key mod p (p<=m)
若散列表表长为m，通常p为小雨或等于表长的最小质数或不包含小于20质因子的合数。

解决散列冲突

1. 开放定址法。
2. 再散列函数法。
3. 链地址发。
4. 公共溢出区法。

实现