输入一个错误的英文单词,它就会提示“拼写错误”。这个单词拼写检查功能,虽然很小但却非常实用。是如何实现的呢?
1 什么是散列?
散列表,Hash Table,用数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。
假如有89名候选人参加大选。为了方便记录投票,每个候选人胸前会贴上自己的参赛号码。这89名选手的编号依次是1到89。
通过编号快速找到对应的选手信息。你怎么做?
可以把这89人的编号跟数组下标对应,查询编号x的人时,只需将下标为x的数组元素取出,时间复杂度就是O(1)。看来按编号查对应人信息,效率很高。
这就是散列,编号是自然数,并且与数组的下标一一映射,所以利用数组支持根据下标随机访问时间复杂度是O(1),即可实现快速查找编号对应的人信息。
假设编号不能设置这么简单,要加上州名、职位等更详细信息,所以编号规则稍微修改,用6位数字表示。比如051167,其中,前两位05表示州,中间两位11表示职位,最后两位还是原来的编号1到89。
此时如何存储选手信息,才支持通过编号来快速查找人信息?
可以截取编号的后两位作为数组下标,来存取候选人信息数据。当通过编号查询人信息时,同样取编号后两位,作为数组下标读取数组数据。
这就是散列。候选人编号叫作键(key)或关键字,以标识一个候选人。把参赛编号转化为数组下标的映射方法就叫作散列函数(或“Hash函数”“哈希函数”),而散列函数计算得到的值就叫作散列值(或“Hash值”“哈希值”)。
散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。
1.1 装载因子(load factor)
表示空位的多少:
散列表的装载因子=填入表中的元素个数/散列表的长度
- 装载因子越大,说明空闲位置越少,哈希冲突概率越大,插入过程要多次寻址或拉长链,查找也会因此变得很慢。
- 太小,会导致内存浪费严重。
1.2 哈希表碰撞攻击
有些攻击者会构造数据,使得所有数据经过hash函数后同槽。若使用的链表法,这时哈希表就会退化为链表,查询时间复杂度从O(1)急剧退化为O(n)。
若哈希表有10w数据,退化后的hash表查询效率就下降10万倍。若之前运行100次查询需0.1s,则现在需1w s。这就可能消耗大量CPU或线程资源,导致系统无法响应其他请求,即拒绝服务攻击(DoS)。
2 hash函数
即hash(key),其中key表示元素的K值,hash(key)的值表示经过散列函数计算得到的hash值。
若编号就是数组下标,所以hash(key)就等于key。改造后的例子,写成hash函数稍微有点复杂。我用伪代码将它写成函数就是下面这样:
int hash(String key) { // 获取后两位字符 string lastTwoChars = key.substr(length-2, length); // 将后两位字符转换为整数 int hashValue = convert lastTwoChas to int-type; return hashValue; }
但现实都是复杂的,若候选人编号是随机生成的N位数或a到z之间的字符串,散列函数该如何实现?
2.1 要求
- 散列函数计算得到的散列值是个非负整数
因为数组下标从0开始 - 若key1 = key2,则hash(key1) == hash(key2)
- 若key1 ≠ key2,则hash(key1) ≠ hash(key2)
此要求看起来合理,但实际上几乎找不到一个不同key对应散列值都不同的散列函数,即使如MD5、SHA、CRC。而且数组存储空间也是有限的,散列冲突概率就更大了。 - 不能太复杂
过度复杂会消耗大量计算时间,影响hash表性能 - hash函数生成的值要尽可能随机并且均匀分布
避免或最小化哈希冲突,而且即便出现冲突,散列到每个槽里的数据也会比较平均,不会数据倾斜
2.2 案例
处理手机号码,因为手机号码前几位重复的可能性很大,但后面几位就比较随机,可以取手机号后四位作为散列值。这种设计方法称为“数据分析法”。
单词拼写检查功能的hash函数可考虑:
- 将单词中每个字母的ASCll码值“进位”相加
- 再跟哈希表的size求余、取模,作为散列值
比如,英文单词java,我们转化出来的散列值就是下面这样:
hash("java")=(("j" - "a") * 26*26*26 + ("a" - "a")*26*26 + ("v" - "a")*26+ ("a"-"a")) / 78978
还有很多设计方法,比如直接寻址法、平方取中法、折叠法、随机数法等。hash函数设计的好坏,决定了哈希表冲突的概率大小,也直接决定了哈希表的性能。
无论设计的多么优秀,还是得考虑如何解决散列冲突问题。
3 散列冲突
3.1 开放寻址法
若出现hash冲突,就重新探测一个空闲位置,将其插入。
最简单的就是
3.1.1 线性探测(Linear Probing)
当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。如ThreadLocalMap。
案例
- 黄块
空闲位置 - 橙块
已存储数据
散列表的大小10,在元素x插入散列表之前,已有6个元素在散列表。
x经过Hash算法后,被hash到下标7处,但该位置已有数据,所以hash冲突。
顺序再往后一个个找,看有无空闲位置,遍历到尾部都没有空闲位置,就再从表头开始找,直到找到空闲位置2插入。
查找元素
类似插入过程。通过hash函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素:
- 若相等
则为目标元素 - 否则
继续顺序往后查找
若遍历到数组中的空闲位置,还没找到,说明目标元素不在散列表。
线性探测法的散列表,删除操作不能单纯地把要删除的元素置null。这是为什么呢?
查找时,一旦通过线性探测方法,找到一个空闲位置,即可认定散列表不存在该数据。
但若该空闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被认定为不存在。
可以将删除的元素,特殊标记为deleted。当线性探测查找时,遇到deleted空间,并不是停下来,而是继续往下探测。