1.哈希表的概念
诸如线性表，树等存储结构，记录在结构中的位置都是随机的，和记录的关键字之间不存在对应关系，为此可以建立一个关键字对应存储位置的关系F(x) = x，F称为哈希函数，按这个思想所建立的表是哈希表。
哈希函数是一个映射，只要让关键字所得的哈希函数值落在表长允许的范围内即可。不同的关键字可能得到的哈希函数值相同，称为冲突。具有相同的哈希函数值的关键字称为同义词。一般情况下，冲突是很难避免的，所以在建造哈希表的时候，不仅要设定一个好的哈希函数，还要设定解决冲突的方法。
2.哈希函数的构造方法
一个好的哈希函数，使得关键字经哈希函数映射到任何一个地址的概率是相等的，称此类哈希函数为均匀的。
a.直接定址法
取关键字或者关键字的某个线性函数值为哈希地址：H(key) = key 或 H(key) = a * key + b。（a，b是常数）
由于直接定址所得的地址集合和关键字的集合大小相同。因此，不同的关键字不会发生冲突，但是实际中不实用。
b.数字分析法
假设关键字是以r为基的数（即r进制），并且哈希表中可能出现的关键字事先都知道，则可取关键字的若干数位组成哈希地址。如一个八位十进制数，取他的2和3位相加结果后舍去进位的值作为哈希地址。
c.平方取中法
取关键字平方后的中间几位为哈希地址。这是一种比较常用的方式，通常在选定哈希函数时不知道关键字全部情况下使用，取其中那几位都不合适，但是一个书平方后的中间几位数和数的每一位都想关，由此得到的哈希地址也是随机的。取的位数由表长决定。如：关键字0100,平方后0010000,取第2-4位，即010; 关键字1100,平方后1210000，即210。
d.折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍弃进位）作为哈希地址。
关键字很多，且关键字中每一位上数字分布大致均匀时，可以采用此法。如国际标准图书编号（ISBN），它是一个10位的十进制数字，当哈希表长度不超过1w时，可以采用折叠法构造一个四位数的哈希函数。
折叠法中数位叠加可以有移位叠加和间界叠加法两种，移位叠加法是将分割后的每一部分的最低位对齐，然后相加；间界叠加法是从一端向另一端延分割界来回折叠，然后对其相加。如：标准图书编号0-442-20586-4，移位叠加：5864 + 4220 + 04 = 10088，H(key) = 0088；间界叠加：5684 + 0224 + 04 = 6092，H(key) = 6092（H为构造四位数的哈希函数）。
e.除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址：H(key) = key mod p，p <= m。
这是一种简单的，也是常用的哈希函数，它不仅可以对关键字直接取模，也可以在平方，折叠后取模。需要注意的是，此方法对p的选择很重要，p选择不好很容易出现同义词。由经验得知：一般情况下，可以选p为质数或不包含小于20的质因数的合数。
f.随机数法
选择一个随机函数，取关键字的随机函数值作为哈希地址，即H(key) = random(key)，其中random是随机函数。通常当关键字长度不等时采用此法。实际中需要根据不同的情况采用不同的函数。
- 计算哈希函数所需要的时间（包括硬件指令的因素）
- 关键字的长度
- 哈希表的大小
- 关键字的分布情况
- 记录的查找频率
3.处理冲突的方法
a.开放定址法
Hi = （H(key) + di）MOD m，i = 1，2，3...，k （k <=m-1）
其中H(key)为哈希函数；m为哈希表表长，di为增量序列，可以有一下三种取法：
- di = 1,2,3,4...,m-1, 称为线性探测再散裂
- di = 1^2, -1^2, 2^2, -2^2,..., -k^2.(k <= m/2)，称为二次探测再散裂
- di = 伪随机序列，称为伪随机探测再散裂
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 11 |
| 60 | 17 | 29 |
如：在一个长度为11的哈希表中，已填入的关键字分别为17，60，29。哈希函数H(key) = key MOD 11。现在第四个记录的关键字为38，由哈希函数得到的地址5, 产生冲突。若用线性探测再散裂方法，得到下一个地址6,仍然冲突，在求下一个地址7,冲突，最后求得地址8为空，终止，将记录填入8.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 11 |
| 60 | 17 | 29 | 38 |
如果采用二次探测再散裂，则应该填入序号为4的位置。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 11 |
| 38 | 60 | 17 | 29 |
类似可以得到伪随机再散裂的地址。
b.在哈希法
Hi = RHi(key) i = 1,2,3,...,k RHi均是不同的哈希函数，即在同义词产生地址冲突时，使用另一个哈希函数计算出地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
c.链地址法
将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址区间在[0, m-1]上，则设立一个指针向量Chain ChainHash[m]，每个向量初始为空指针。凡是哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。
d.建立一个公共溢出区
假设哈希函数的值域为[0,m-1]，则社响亮HashTable[0...m-1]为基本表，每个分量存放一个记录，另设立响亮OverTable[0...v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。
4.哈希表的查找及其分析
哈希表在关键字和记录的存储位置间建立了映射，但是由于冲突的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。因此仍需以平均查找长度来衡量哈希表的查找效率。查找过程中需要和给定值进行比较的关键字个数由以下三个因素决定：哈希函数，处理冲突的方法和哈希表的装填因子（a = 表中填入的记录数/哈希表的长度）。a越小，发生冲突的可能性越小；反之a越大，冲突可能性越大。
- 线性探测再散裂的哈希表查找成功时的平均查找长度约等于（1+1/（1-a））/ 2
- 随机探测再散裂，二次探测再散裂和再哈希的查找成功的平均查找长度约等于-ln（1-a）/ a
- 链地址法查找成功的平均查找长度为1+a/2