散列表 | Notes

散列思想

散列表用的数组支持按照下标随机访问数据的特性，是数组的一种扩展，由数组演化而来。没有数组，就没有散列表。

键/key/关键字–标识唯一数据
散列函数/Hash函数/哈希函数–将键转化为数组下标的映射方法
散列值/Hash值/哈希值–散列函数计算得到的值

通过散列函数把元素的键值映射为下标（取模），然后将数据存储在数组中对应下标的位置。按照键值查询元素时，用同样的散列函数，将键值转化为数组下标，从对应的数组下标的位置取数据。

散列函数

散列函数–hash(key)，其中key表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值。

散列函数设计的基本要求：

散列函数计算得到的散列值是一个非负整数；
如果key1=key2，那hash(key1) == hash(key2)；
如果key1!=key2，那hash(key1) != hash(key2)；

数组的存储空间有限，找到一个不同的key对应的散列值都不一样的散列函数，几乎是不可能的。必然存在散列冲突。

散列冲突

再好的散列函数也无法避免散列冲突，常用的散列冲突解决方法有两类：开放寻址法、链表法。

开放寻址法
如果出现散列冲突，就重新探测一个空闲位置，将其插入。
- 线性探测
  往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
  在散列表中查找元素的过程类似插入过程。通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
  使用线性探测法解决冲突的散列表，不能单纯的把要删除的元素设置为空。在查找的时候，一旦通过线性探测方法，找到一个空闲位置，可以认定散列表中不存在这个数据。但是如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据会被认定为不存在。解决方案，将删除的元素特殊标记为deleted，当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来，而是继续往下探测。
  
  缺陷：当散列表中插入的数据越来越多时，散列冲突发生的可能性会越来越大，空闲位置会越来越少，线性探测的时间会越来越久，极端情况下，可能需要探测整个散列表，所以最坏情况下的时间复杂度为O(n)。在删除和查找时也可能会探测整张散列表，才只能找到要查找或者删除的数据。
- 二次探测
  类似线性探测，线性探测每次探测的步长是1，探测的下标序列是hash(key)+0,hash(key)+1,hash(key)+2…二次探测的步长变成了原来的“二次方”，探测的下标序列是hash(key)+0,hash(key)+1²,hash(key)+2²…
- 双重散列
  不仅仅使用一个散列函数。使用一组散列函数hash1(key),hash2(key),hash3(key)…先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。
不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，尽可能保证散列表中有一定比列的空槽位置。用装载因子来表示空位的多少。
计算公式：

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

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
链表法
在散列表中，每个“桶”或者“槽”会对应一条链表，所有散列值相同的元素都放到相同槽位对应的链表中。
当插入的时候，只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是O(1)。当查找/删除一个元素时，同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。查找、删除的时间复杂度跟链表的长度k成正比O(k)。对于散列比较均匀的散列函数来说，k=n/m，其中n表示散列中数据的个数，m表示散列表中“槽”的个数。