散列表(上)

Friday, April 26, 2019

散列思想

  • 散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。
  • 我们用key来标记,把key转换成数组下标的映射方法就叫作散列函数,而散列函数计算得到的值就叫作散列值。

file

如何构造散列函数

  1. 散列函数计算得到的散列值是非负整数
  2. 如果key1 = key2 ,那么hash(key1) == hash(key2)
  3. 如果key1 != key2. 那么hash(key1) != hash(key2)

但是第三点是不可能的,就算是MD5,SHA,CRC等哈希算法,也无法完全避免散列冲突。

散列冲突

开放寻址法

线性探测

如果出现了散列冲突,我们就重新探测一个空闲的位置,将其插入,线性探测就是其中一种。

当我们往散列表插入数据时,如果存储位置被占用了,我们就从当前位置依次往后找,直到找到空闲的位置。

file

查找也是类似插入过程,我们通过散列函数求出要查找元素的键值,然后比较下标为散列值的元素和要查找的元素,如果相等,则说明找到了,否则就顺序往后依次查找。如果遍历到空闲位置,还没有找到,则说明不在散列表中。

file

删除操作不能直接把元素删除,因为如果删除留空后,会对查找操作产生影响。上面有说到,查找操作,如果遍历到空,就不再查找了,认定为不存在。

我们可以把要删除的元素,标记为deleted,当查找时,遍历到标记deleted的,继续往下查找。

file

线性探测有个很明显的问题,数据越来越多的时候,散列冲突发生的概率会越来越大,空闲位置会越来越少,

还有两种经典的探测方法,二次探测和双重散列。

  • 二次探测的步长为n的2次方,比如下标序列就是hash(key) + 0, hash(key)+1^2, hash(key)+ 2^2
  • 双重散列就是,如果遇到位置被占用了,直接用第二个散列函数,依次类推

我们用装载因子来表示空位的多少,越大表示空闲位置越少

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

链表法

链表法更为常用,每个槽会对应一条链表,散列值相同的元素都会放到对应的链表中。

file

这种情况下,插入的时间复杂度是O(1),查找和删除的时间复杂度跟链表长度k成正比

Word文档中单词拼写检查功能是如何实现的

我们可以把常用的单词全部放入内存中,比如20w个单词,假设平均10个字母,一个单词10字节,20w单词占用2MB的存储空间,就算放大10倍也是20MB,所以可以完全可以用散列表存储整个英文单词。

当用户输入单词,就可以直接拿输入的单词去散列表查找,查到则说明拼写正确,没有则说明可能有误。

数据结构-算法

散列表(中)

二分查找(下)