散列表其实就是数组的一种扩展。用的是数组下标支持随机访问数据的特性。

假设一个班级有 30 个学生，如何快速查找到每一个名字对应的人？

我们把这 30 个学生，按照学号把编号 1 的学生信息放到数组下标为 1 的位置，以次类推；当我们需要查找编号为 k 的学生时，只需要将数组下标为 k 的元素取出来就可以了。

如果学号前面还有班级信息用六位数表示，如 050301 表示五年级三班 01 号学生。这个时候查找学生就不能直接使用学号作为下标，但我们可以截取学号后两位用来作为下标来存储学生信息实现学号与数组中个人信息的的对应。

其中，学生的学号我们叫做键(key)，用来标识一个学生。把六位数的学号转化为下标的方法叫做散列函数，而用散列函数计算得到的值就叫做散列值(哈希值)。

1
2
3

function hash(key) {
  return key.substring(key.length - 2, key.length);
}

散列函数

设计要求

散列函数计算得到的散列值是一个非负整数;
因为数组下标是从 0 开始的，所以散列函数生成的散列值也要是非负整数。
如果 key1 == key2,那么 hash(key1) == hash(key2);
相同的 key 经过散列函数得到的散列值也应该是相同的。
如果 key1 ≠ key2,那么 hash(key1) ≠ hash(key2);
在实际情况中，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的，即无法避免散列冲突，而且数组的存储空间有限，也会加大散列冲突的概率。

如果出现了散列冲突，我们就重新探测一个空闲位置将其插入。

当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

和线性探测很像，线性探测每次探测步长是 1，（如下标序列 hash(key) + 0, hash(key) + 1, …）而二次探测的步长是原来的二次方(如下标序列 hash(key) + 0, hash(key) + 1²， hash(key) + 0 + 2²)。

双重散列不仅使用一个散列函数，当计算得到的存储位置已经被占用时，再用第二个散列函数，直到找到空闲的存储位置。

不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会提高。一般情况下，为了保证散列表的操作效率，我们会尽可能保证散列表中有一定比例的空闲槽位。用装载因子表示空位的多少。

装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大，说明空闲越少，冲突越多，散列表的性能会下降。

在链表中每个位置都会对应一条链表，所有散列值相同的元素都放到相同槽位对应的链表中。