在实际的开发过程中，我们总能看见大佬们说用一个哈希表（hash-table）来加快处理，但事实上并不清楚hash表到底做了什么事情。于是我又重温了一下当年的数据结构课程，大致了解了哈希表的思想以及他所做的事情。

简单来说，hash表的设计就是为了便于更好、更快的查找的。
我们知道一个基本的查找模式采用的是k-v键值法，即一个key对应一个value，我们根据自己的key去找到相应的value值，数组就是最典型的例子。但数组中的key都是从0开始，这样设计的key值是没什么意义的，只是为了单纯提供一个索引的作用。

而hash所做的工作就是根据value的值，通过一个hash算法（或成为hash函数）来为该value生成对应的key，这样，当我们在想找一个value的时候，就可以通过这个hash算法来得到对应的key，从而直接在hash表中去快速匹配对应的值了。

常见的hash函数构造法：
直接定址法：将k+c作为一个地址（h(k)=k+c，c是常量）
除留余数法：h（k）=k mod p，p<= hash表长度，且取为质数
数字分析法：将一些大数据范围，通过数据分析，将其映射到小数据范围内。

当然这样构造的得到的key很可能会出现冲突，即两个不同的value经过hash函数处理后出现了两个相同的key值，我们称之为哈希冲突

解决哈希冲突的方式当然就是要为冲突的value重新分配一个空闲的位置，采用的方式有如下几种：
线性探查法：$d_{0}=h(k)$ $d_i = (d_{i-1}+1)$ mod m
平方探查法：$d_{0}=h(k)$ $d_i = (d_0±i^2)$ mod m （ps：可避免出现堆积现象，但缺失是无法查找到哈希表中所有单元，但至少可以查找到一半单元）
拉链法：改良了hash表结构，在顺序存储的基础上采用了链式存储，使得一个key值空间下的value可以通过链表结构连接在一起，提高了空间利用率