一、hash表理解

将一组数据按照顺序存储的存储结构存储在：以数据通过一个特定的函数func(关键字)，我们称之为“散列函数”，以这个散列函数作为索引存储在一个较长的数组中，查询的时候，可以直接根据关键字查询，速度较数组和链表要快得多。

二、散列函数的设计

遵循原则：计算简单、分布均匀

① 直接定址法：直接利用数据作为散列函数
②数字分析法：比如电话号码前三位是运营商标识，接着四位是省市，最后的4位才是标识，所以同一运营商，同一省市的用户号码信息，可以利用最后这四位作为散列函数。
③平方取中法：比如13,15,16、、、13的平方为169，取中 6 作为散列函数。
④平方取余法：类似于平方取中，拿到13，用13%10 = 3 ，所以13的散列函数为3。

三、hash冲突的解决方案

11、12、20 、、、，假如采用取余法求散列函数，那么12和20与10求余的余数都为2，那么这样就会产生hash冲突，解决hash冲突的方式主要有以下几种：

①开放地址法：

也分为：

1、线性探测法

在求得相同余数后，将后者存储在前者紧跟着的后面一个位置。

2、二次探测法

线性探测法使得在数组中某一段的数据会过于的集中。
二次探测法也就是将线性探测法中一次只移动一个位置改成一次移动平方个位置，比如，上面的12和20,20的散列函数就变成：2的平方+2，也就是6 这个位置。这种方法优化了线性探测法，解决掉了数据聚集的问题。

3、再hash法

利用多个hash函数：func(关键字)，作为存储依据。

②链地址法：

将因为hash函数求得相同hashcode的数据存储在hash表的同一下标位置，多个数据采用链表的形式存储，也就是说，hash表中存储链表，查找的时候就可以根据hashcode找到hash表的下标索引位置，然后根据这个索引位置去找到这个数组元素，这个数组元素就是链表，对链表进行相应的操作。