什么是HashTable
对比其他数据结构，HashTable是一种典型的空间换时间思想的结构，大体思路就是创建一个数组，通过一个hash函数以及关键字计算出所要存值的数组下标，之后取值的时候再通过hash函数计算出所要取值的数组下标，下标地址index = hash(key)。但是使用hash函数计算出的下标可能会存在重复，也就是hash冲突，如何处理hash冲突是需要我们思考的。
Hash函数
直接地址法
取关键字或关键字的某个线性函数值为哈希地址，即 H(key)=key或H(key)=a*key+b
数字分析法
假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
平方取中法
去关键字平方后的中间几位为哈希地址。
折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。在折叠法中数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分隔界来回折叠，然后对齐相加。
除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址，即H(key)=key%p，p≤m。
随机数法
选择一个随机函数，去关键字的随机函数值为它的哈希地址，即H(key)=random(key)，其中random为随机函数。
Hash函数设计的考虑因素
- 计算散列地址所需要的时间（即hash函数本身不要太复杂）
- 关键字的长度
- 表长
- 关键字分布是否均匀，是否有规律可循
- 设计的hash函数在满足以上条件的情况下尽量减少冲突
Hash冲突
通过hash(key)计算出来的结果是有可能存在重复的，也就是hash冲突，也就是说我们需要解决hash冲突。
开放定址法
如果H（key1）=H（keyi） 那么keyi存储位置H i = ( H ( k e y ) + d i ) % m ，m为表长。di有三种取法 其中H(key)为hash函数，m为hash表表长，