网站建设云主机云服务器,建筑设计作品展示网站,网站建设方案书 个人,桂林东西巷美食文章来源于极客时间前google工程师−王争专栏。 一旦我们在Word里输入一个错误的英文单词#xff0c;它就会用标红的方式提示“编写错误”。Word的这个单词拼写检查功能#xff0c;虽然很小但却非常实用。这个功能是如何实现的#xff1f;
散列别#xff08;Hash Table它就会用标红的方式提示“编写错误”。Word的这个单词拼写检查功能虽然很小但却非常实用。这个功能是如何实现的
散列别Hash Table可以轻松实现这个功能。
散列思想
“Hash Table”我们平时也叫它“哈希表”或者“Hash表”。
散列表用的是数组支持按照下标随机访问数据的特性所以散列表其实就是数组的一种扩展由数组演化而来。可以说如果没有数组就没有散列表。
场景假如我们有89名选手参加学校运动会为了方便记录成绩每个选手胸前都会贴上自己的参赛号码。89名选手的编号依次是1到89。我们希望编程实现这样一个功能通过编号快速找到对应的选手信息。怎么做
将选手放到数组中编号为k放到数组中下标为k的位置。
需要查询参赛为x的直接取数组下标为x位置就可以时间复杂度为O(1)。
在这个场景中参赛编号为自然数与数组下标形成一一映射利用数组支持根据下标随机访问的特性O(1)时间复杂度就可以实现快速查找编号对应的选手信息。这就是散列的思想。
编号如果详细比如05116705表示年级11表示班级最后两位代表编号。可以截取参赛编号的后两位作为数组的下标来存储选手信息。
散列思想
参赛选手的编号我们叫做键key或者关键字。参赛编号转化为数组下标的映射方法就叫做散列函数或“Hash函数”“哈希函数”。散列函数计算得到的值就叫作散列值或“Hash值”“哈希值”。
规律总结散列表用的就是数组支持按照下标随机访问时间复杂度为O(1)的特性。我们通过散列函数把元素的键值映射为下标然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时我们用同样的散列函数将键值转化为数组下标从对应的数组下标的位置取数据。
散列函数
散列函数我们可以把它定义成hash(Key)其中key表示元素的键值hash(Key)的值表示经过散列函数计算得到的散列值。
上述场景中散列函数实现如下
int hash(String key) {// 获取后两位字符string lastTwoChars key.substr(length-2, length);// 将后两位字符转换为整数int hashValue convert lastTwoChas to int-type;return hashValue;
}
如果参赛选手的编号是随机生成的6位数字又或者用的是a到z之间的字符串该如何构造散列函数呢三类函数设计有三个基本要求
散列函数计算得到的散列值是一个非负整数如果key1 key2那么hash(key1) hash(key2)如果key1 ≠ key2那么hash(key1) ≠ hash(key2)
第三点在真是的情况下几乎是不可能的。著名的MD5、SHA、CRC等哈希算法也无法避免这种散列冲突。而且数组的存储空间有限也会加大散列冲突的概率。
散列冲突
常见的散列冲突解决方法有两类开放寻址法open addressing和链表法chaining。
开放寻址法
开放寻址法的核心思想是如果出现了散列冲突我们就重新探测一个空闲位置将其插入。那么如何重新探测新的位置呢线性探测Linear Probing。
当我们往散列表中插入数据时如果某个数据经过散列函数散列之后存储位置已经被占用了我们就从当前位置开始依次往后查找看是否有空闲位置直到找到为止。
如上图所示黄色的色块表示空闲位置橙色的色块表示已经存储了数据。x经过Hash算法之后被散列到位置下标为7的位置但是这个位置已经有数据了所以就产生了冲突。于是我们就顺序地往后一个一个找看有没有空闲的位置遍历到尾部都没有找到空闲位置于是我们再从表头开始找直到找到空闲位置2于是将其插入到这个位置。
在散列表中查找元素的过程有点类似插入过程。计算出散列值然后比较数组中下标为散列值的元素和要查找的元素。如果相等就说明是我们要找的元素否则就顺序往后依次查找。如果遍历到数组中的空闲位置还没有找到就说明要查找的元素并没有在散列表中。查找建立在插入的基础上 删除操作将删除的元素特殊标记为deleted不能直接置为空。当线性探测查找的时候遇到标记为deleted的空间并不是停下来而是继续往下探测。
极端情况下我们可能需要探测整个散列表所以最坏情况下的时间复杂度为O(n)。
对于开放寻址冲突解决方法除了线性探测方法之外还有另外两种比较经典的探测方法二次探测Quadratic probing和双重散列Double hashing。
二次探测跟线性探测很像线性探测每次探测的步长是1那它探测的下标序列就是hash(key)0hash(key)1hash(key)2……而二次探测探测的步长就变成了原来的“二次方”也就是说它探测的下标序列就是hash(key)0hash(key)12hash(key)22
双重散列意思就是不仅要使用一个散列函数。使用一组散列函数hash1(key),hash2(key),hash3(key)…先用第一个散列函数如果计算得到的存储位置已经被占用再用第二个散列函数直到找到空闲的存储位置。
不管哪种探测方法当散列表中空闲位置不多的时候散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率一般情况下我们会尽可能保证散列表中有一定比例的空闲槽位。使用**装载因子load factor**来表示空位的多少。
装载因子的计算公式是 散列表的装载因子 填入表中的元素个数 / 散列表的长度 装载因子越大说明空闲位置越少冲突越多散列表的性能会下降。
2.链表法
链表法是一种更加常用的散列冲突解决办法相比开发寻址法它要简单的多。在散列表中每个“桶bucket”或者“槽solt”会对应一条链表所有散列值相同的元素我们都放到相同槽位对应的链表中。
当插入的时候我们只需要通过散列函数计算出对应的散列槽位将其插入到对应链表中即可所以插入的时间复杂度为O(1)。当查找、删除一个元素时我们同样通过散列函数计算出对应的槽然后遍历链表查找或者删除。查找删除的复杂度是多少
查找删除时间复杂度跟链表的长度k成正比也就是O(k)。对于散列比较均匀的散列函数来说理论上kn/m其中n表示散列中数据的个数m表示散列表中“槽”的个数。
解答开篇
Word文档中单词拼写检查功能是如何实现的
常用的英文单词20万个左右假设单词的平均长度是10个字母平均一个单词也就是占用10个字节的内存空间那么20万英文单词大约占2MB的存储空间就算放大10倍也就是20MB。对于现在的计算机来说这个大小完全可以放在内存里面。所以可以用散列表来存储整个英文单词词典。
总结
散列表来源于数组它借助散列函数对数组这种数据结构进行扩展利用的是数组支持按照下标随机访问元素的特性。散列表的两个核心问题是散列函数设计和散列冲突解决。散列函数设计的好坏决定了散列冲突的概率也就决定了散列表的性能。
思考
1.假设我们有10万条URL访问日志如何按照访问次数给URL排序
遍历 10 万条数据以 URL 为 key访问次数为 value存入散列表同时记录下访问次数的最大值 K时间复杂度 O(N)。
如果 K 不是很大可以使用桶排序时间复杂度 O(N)。如果 K 非常大比如大于 10 万就使用快速排序复杂度 O(NlogN)。
2.有两个字符串数组每个数组中大约有10万条字符串如何快速找出两个数组中相同的字符串
以第一个字符串数组构建散列表key 为字符串value 为出现次数。再遍历第二个字符串数组以字符串为 key 在散列表中查找如果 value 大于零说明存在相同字符串。时间复杂度 O(N)。
