当我们想在内存中通过关键字寻找特定数据时(键值对)，总是希望能快速找到所需数据，在无索引的情况使用二分查找、二叉树、b数也只能在O(lgn)的时间复杂度上查找。
而通过对数据的关键字和其存储位置建立对应关系f，使得每个关键字通过f能唯一确定一个储存位置，那么就能通过对关键字的查找实现O(1)级别的数据查询。
在此，我们称这个对应关系f为哈希函数，以此思想建立哈希表。
哈希函数的构造方法有多种，如：
1.直接定址法
H(key)=key或H(key)=a*key+b
该方法映射较为简单，其地址集合和关键字集合大小相同，虽然不会产生冲突，但是很少使用。
2.数字分析法
通过分析给定数据的特性来建立哈希函数
比如一组数据：814567，814123，814151...，可以发现该组数据前三位数字一样，后三位数字随机，且均为6位数，那么我们可以取其后三位通过各种方法操作去获得哈希地址。
3.折叠法
折叠法有移位叠加和间界叠加两种方法，移位叠加是将分割后的每一部分的最低位对齐后相加；间界叠加是从一端向另一端沿分割线来回折叠对齐相加。
如关键字0442205864，左边是移位叠加，右边是间界叠加。
5864 5864 4220 0224 + 04 + 04 ————————————— —————————————— 10088 6092
4.平方取中法
将关键字平方后的中间几位为哈希地址。
5.除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H(key)=key%p , (p<=m)
该方法较为简单，可以对关键字直接取模，也可以将关键字平方取中，折叠等操作后取模。
6.随机数法
将关键字作为种子产生随机数，取该随机数为哈希地址。
当然哈希函数的构造方法远远不止上述几种，实际环境中根据不同需求情况采用不同的哈希函数。
哈希函数不是万能的，其常常会产生冲突。冲突即不同的关键字通过哈希函数映射到了相同的地址。
通常处理哈希冲突的方法有一下几种：
1.开放定址法
(1)线性探测再散列，即往对应地址后继续寻找空位。
(2)二次探测再散列，取探测值为1²，-1²，2²，-2²...来回寻找空位。
(3)伪随机探测再散列，取探测值为伪随机序列。
需该方法可能产生数据聚集，即同义词均出现在同一片区域
2.再哈希法
当产生冲突时取不同的哈希函数再次进行计算。该方法不易产生聚集，但是增加了计算时间。
3.链地址法
将所有关键字为同义词的记录存储在同一线性链表中。
4.建立一个公共溢出区
所有同义词一旦发生冲突即填入溢出表。
大部分哈希函数，在数据量较少的情况下性能较好，不易产生冲突，能实现时间复杂度为O1的快速查找，但当数据量十分庞大的情况下，不建议采用哈希表作为查询方式。
c++中我们经常用unordered_map关联容器来实现哈希表，其内部冲突处理采用链地址法，需注意默认的unordered_map不支持以结构体或类作为键，需重载。
参考资料：数据结构(C语言版)---清华大学出版社