一、什么是散列表
散列表又称哈希表，这种数据结构提供了键和值的映射关系，只要给出一个 key， 就可以高效查找到它所匹配的 value，时间复杂度接近? O(1)
举个例子，在读书的时候，我们每个人都有一个学号，一个学号对应一个学生。学号可以当作一个key, 学生名字就是一个value。
二、哈希表的作用
在日常开发中，我们经常会用到哈希表，如 redis 缓存，PHP 的关联数组，go 的 map 等。
再比如说，假设我们要统计一份名单中，每个名字出现的重复次数，那么我们就可以建立一个简单的哈希表，key 是名字，value是出现的次数。
三、哈希函数
当我们输入学生的学号时，希望可以得到学生的姓名，那么我们就需要一个“中转站”来帮我们实现这一功能。
其实这就是哈希函数，在不同的语言中，哈希函数大多都是不同的。
数据结构最底层结构就是数组，而哈希表的实现实际上也是基于数组的。
我们可以简单举个简单的例子：
index = hashCode(key) % Array.Length
这是简单的哈希函数。通过哈希函数，我们可以把字符串或者其他类型的 key ，转换成数组的下标 index。
根据上面的公式，假设数组的长度我们定义为 10。给定的key 为 001122
则 index = hashCode(key) % Array.Length = 225534817 % 10 = 7
其中 hashCode 的定义为
StringBuilder sb = new StringBuilder("001122");
System.out.println(sb.hashCode()); // 225534817
在 Java 及大多数面向对象的语言种，每个对象都会又属于自己的hashcode, 也是用来区分不同对象的重要标识，无论对象自身的类型是什么，它们的hash code都是一个整形变量。又例如
StringBuilder s2 = new StringBuilder("this");
System.out.println(s2.hashCode()); // 1878246837
通过这种方式，我们通过哈希函数获取到 index后，就可以直接访问数组来获取需要的元素，复杂度为 O(1)
四、哈希冲突
数组的长度总是有限的，哈希函数也不是万能的，总是会遇到坑位不足的情况，当不同的 key 获取到的 index 相同时，先进去的人就先占位，这是不可抢占的。后面的人就很尴尬。
这就好比说，有个酒店，店主自己搞了一个方法用来随机给客户房间号。但是房间是有限的，最后顾客太多了，店主发现他的方法，会重复分配，导致不同的顾客分配了同一个房间号
店主的方法此时就是哈希函数，而这种现象我们在数学上称之为 哈希冲突。
由于资源问题，哈希冲突是无法避免的，而且不同的哈希函数发生哈希冲突的可能性均不同。其表示为装填因子
装填因子（装填因子=数据总数 / 哈希表长）
当哈希表长固定时，数据总数影响着装填因子的大小，当因子越大时，发生哈希冲突的可行性也是越大。但是哈希表的空间利用率也是越高。
因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.
五、处理哈希冲突的方式
哈希冲突是无法避免的，但是可以解决，目前解决哈希冲突的方式主要有几种
5.1 开放地址方法
（1）线性探测
按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。
（2）再平方探测
按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。
（3）伪随机探测
按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。
这些方法，都有个共同点，就是重新寻址，因此称之为开放地址法。
5.2 链式地址法
对于相同的值，使用链表进行连接。使用数组存储每一个链表。
当来了一个新的元素G后，假设经过哈希函数计算后得到的地址是003，此时 003 已经被 C 占了，那么就基于数组拉出一个链表，按顺序去依次放冲突的元素。
优点：
（1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
（2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
（3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
（4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
缺点：
指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。
3.建立公共溢出区
建立公共溢出区存储所有哈希冲突的数据。
4.再哈希法
对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。
六、哈希表的扩容
不同语言或者说是工具对哈希表的扩容规则都有些区别。在这里，我们简单进行举例。
哈希表的扩容并不是简单的把长度增长，而是需要经历一些流程。一般的流程如下：
6.1 创建新的数组
一般来说，新的数组都是原数组的两倍大小
6.2 数据 rehash
将旧的数据重新 rehash 到新数组中，此时的哈希函数和旧的会不同，这是因为数组的长度改变了，如果还是沿用旧的哈希函数，新增加的数组内存也无法进行利用。
通过扩容后，原本拉出来的链表也会被平铺到新的数组的，查询效率也会大大增加，这是因为拉链法生成的链表只能通过遍历链表来寻找元素，因此复杂度会变成 O(n) (n为链表长度)，因此，当拉出来的链表越来越长时，必然会影响查询效率，因此扩容是必须的措施。
其中，一般来说，我们不会直接一次性直接扩容，例如在 redis 中，会有个渐进式 rehash 的方式，可以提高扩容的效率。详情可点击链接查看我的另一篇文章：
