什么是哈希表？如何处理冲突？

哈希表又名散列表，是根据关键字直接寻找数据的存储位置，不需要进行比较，查找效率较高。

在构建哈希表中，最关键的就是哈希函数的设计，一般有六种方法：

● 直接定址法：哈希函数为一次函数；

● 数字分析法：如果关键字由多个字符或数字组成，可以考虑抽取其中的若干位作为哈希地址；

● 平方取中法：对关键字做平方操作，取中间的若干位作为哈希地址；

● 折叠法：将关键字分割为位数相同的几部分，取这几部分的叠加和（舍去进位）作为哈希地址；

● 除留余数法：若已知整个哈希表的最大长度m，则可以取一个不大于m的数p，对关键字进行取余运算，将运算结果作为哈希地址；

● 随机数法：取关键字的一个随机函数值作为哈希地址；

处理冲突的方法：

● 开放定址法：包含线性探测法、二次探测法、伪随机数探测法，即

H(key)=(H(key) + d) MOD m

其中d就是用上面三种方法确定的增量，分别为

● 线性探测法：d = 1, 2, 3, ..., m-1，可以理解为一直向右寻找，子弹式；

● 二次探测法：d = 12, -12, 22, -22, 32，可以理解为一直向左/右寻找，涟漪式；

● 伪随机数探测法；

● 再哈希法：使用另一个哈希函数计算，直到冲突不再发生；

● 链地址法：将所有发生冲突的关键字所对应的数据全部存储在同一个线性链表中。