一、哈希表/散列表（Hash Table）简介
哈希表，也叫散列表（Hash table），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过一个关于键值的函数(哈希函数)将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。
- 哈希表是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。
- 把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。
- 通常，我们把这个关键字称为 Key，把对应的记录称为 Value，所以也可以说是通过 Key 访问一个映射表来得到 Value 的地址。
二、哈希函数
对于设定场景的好的哈希函数是产生哈希冲突的次数最少的哈希函数。对于一些特殊领域，有特殊领域的哈希函数设计方式，甚至有专门的论文。
“键”通过哈希函数得到的“索引”分布越均匀越好。
1、不同类型数据的哈希函数设计
直接寻址法：取关键字或关键字的某个线性函数值为散列地址。
− H ( k e y ) = a × k e y + b -H(key)=a×key+b−H(key)=a×key+b
比如：a = 1 , b = − 5 a=1,b=-5a=1,b=−5
除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要。m一般取素数或者直接用 n来减少哈希冲突。
− H ( k e y ) = k e y % m -H(key)=key\%m−H(key)=key%m
比如：m = 5 m=5m=5数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。
平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
2、不同类型数据通过哈希函数转为整型
3、哈希函数的设计原则
三、哈希冲突
哈希是通过对数据进行再压缩，提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对应相同的值。这时候就产生了哈希冲突。
对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称哈希冲突。
四、解决哈希冲突的方法
开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。
再哈希法：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
链地址法（Seperate Chaining）：链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的，我们会在后面着重学习这种方式。
建立一个公共溢出区：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。