摘要：
1，散列表的介绍
2，散列函数的构造
2.1 直接定址法
2.2 除留余数法
2.3 数字分析法
2.4 平方取中法
2.5 折叠法
2.6 随机数法
3，散列冲突的解决
3.1 开放定址法(开放寻址法)
3.2 链地址法(拉链法)
3.3 再散列法
3.4 建立一个公共溢出区
4，散列表的实现
1，散列表的介绍
散列表(Hash table，也叫哈希表)，是根据键值对(key，value)进行访问的一种数据结构。他把一对(key，value)通过 key 的哈希值来映射到数组中，这个映射函数叫做散列函数，存放数据的数组叫做散列表。
散列表就是通过把关键字映射到表中位置来查询，以加快查找的速度。
举个例子，为了查找某个好友的微信号，你可以按照好友首字母顺序查找，在首字母为 W 的表中查找王姓的好友，显然比直接查找要快得多。
这里使用人名作为关键字， 取首字母是这个例子中散列函数的函数法则，存放首字母的表对应散列表，关键字和函数法则理论上可以任意确定。
2，散列函数的构造
散列表是根据key值的函数法则映射到数组中，不同的key值有可能会映射到数组的同一个位置，所以在选择散列函数的时候要使key值映射到函数的位置尽可能分散。
在构造散列函数时，必须注意以下几点：
1，散列函数计算出来的值尽可能等概率、均匀分布在整个空间中，从而减少冲突的发生。
2，散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址。
常见的散列函数有：直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法。
直接定址法：
直接定址法是取关键字或关键字的某个线性函数值为散列地址，散列函数为：
ℎℎ()=或ℎℎ()=⋅+；
其中 ， 为常数，这种方法计算最简单。
它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
例如：使用直接定址法存储序列 [100, 600, 700, 200, 300]，选择散列函数 hash(k) = k / 100 (a=1/100, b=0)，我们假设key值和value值都是它们本身。
直接定址法在特定条件下（如关键字范围已知且较小）是非常高效的散列方法。然而，在实际应用中，由于其对关键字分布的限制和可能的空间浪费，直接定址法并不是最常用的散列方法。