数据结构与算法之美:散列表

如何实现一个单词拼写检查功能？

散列思想

散列表的英文叫“Hash Table”，也叫Hash表，Hash表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展。

规律:

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

散列函数

散列函数,就是一个函数,我们可以把他定义成hash(key),其中key表示元素的键值,hash(key)的值表示经过散列函数计算得到的散列值

hash的要求

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

散列冲突

解决散列冲突的解决方法有两类,开放寻址法和链表法

1.  开放寻址法

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

          

          双重散列

意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

          二次探测

          所谓二次探测，跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+12，hash(key)+22……

装载因子

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

 

1.  链表法

链表法是一种更加常见的散列冲突解决办法,相比开放寻址法,在散列表中,每个"桶"对应一条链表,所有散列相同的元素我们都放到相同位置对应的链表中

当插入的时候,我们只需要通过散列函数计算初对应的散列槽位,将其插入到对应链表中即可,所以插入的时间复杂度是O(1).

查找删除一个元素的复杂度与链表的长度k成正比,也就是O(k)