1 散列
散列表（HashTable），我们平时也会称它为“哈希表”，是一种经常使用的数据结构，也是典型的空间换时间的思路的体现。
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。
假如我们有 19 名选手参加学校运动会。为了方便记录成绩，每个选手胸前都会贴上自己的参赛号码，用 6 位数字来表示。比如 051167，其中，前两位 05 表示年级，中间两位 11 表示班级，最后两位是依次递增的编号 1 到 19。
尽管不能直接把编号作为数组下标，但我们可以截取参赛编号的后两位作为数组下标来存取选手信息。这就是典型的散列思想。其中，参赛选手的编号叫做key，参赛编号转化为数组下标的映射方法就叫作散列函数，而散列函数计算得到的值就是散列值，时间复杂度是 O(1)。
2 散列函数
散列函数在散列表中起着非常关键的作用，顾名思义就是一个函数，可以将其定义为 hash(key)，key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。
上述例子中，编号的后两位就是数组下标，所以 hash(key) 就等于 key，如下：
int hash(String key) { // 获取后两位字符 string lastTwoChars = key.substr(length-2, length); // 将后两位字符转换为整数 int hashValue = Integer.parseInt(lastTwoChars); return hashValue; }
如果参赛选手的编号是随机生成的 6 位数字，又或者用的是 a 到 z 之间的字符串，我们可以依据以下三点来设计散列函数：
1.散列函数计算得到的散列值是一个非负整数；
2.如果 key1 = key2，那 hash(key1) == hash(key2)；
3.如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。
第三点要求看起来合理，但是在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。此外，因为数组的存储空间有限，也会加大散列冲突的概率。所以针对散列冲突问题，我们需要通过其他途径来解决。
3 散列冲突
3.1 开放寻址法
开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。比较简单的探测方法是线性探测。
当往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
在散列表中查找元素的过程类似插入过程。通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。相等则说明就是要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
散列表跟数组一样，不仅支持插入、查找操作，还支持删除操作。对于使用线性探测法解决冲突的散列表，删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。
解决方案是将删除的元素，特殊标记一下。当线性探测查找的时候，遇到特殊标记的空间时，并不是停下来，而是继续往下探测。
线性探测法其实存在很大问题。当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，才能找到要查找或者删除的数据。
为了尽可能保证散列表的操作效率，一般情况下，会保证散列表中有一定比例的空闲槽位，空位的多少则用负载因子（load factor）表示。
负载因子 = 填入表中的元素个数 / 散列表的长度
负载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
3.2 链表法
链表法是一种更加常用的散列冲突解决办法。在散列表中，每个“槽（slot）”会对应一条链表，所有散列值相同的元素都放到相同槽位对应的链表中。
当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。
关于查找和删除操作的时间复杂度，和链表的长度k成正比，即O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。
