宁波网站建设公司推荐易企网,宜昌营销型网站建设,六安网站建设招聘,wordpress sae图床目录 前言散列思想散列函数散列冲突解答开篇 前言 本节课程思维导图#xff1a; Word 的单词拼写检查功能#xff0c;虽然很小但却非常实用。你有没有想过#xff0c;这个功能是如何实现的呢#xff1f;其实啊#xff0c;一点儿都不难。只要你学完今天的内容#xff0c;… 目录 前言散列思想散列函数散列冲突解答开篇 前言 本节课程思维导图 Word 的单词拼写检查功能虽然很小但却非常实用。你有没有想过这个功能是如何实现的呢其实啊一点儿都不难。只要你学完今天的内容散列表Hash Table。你就能像微软 Office 的工程师一样轻松实现这个功能。
散列思想
散列表的英文叫“Hash Table”我们平时也叫它“哈希表”或者“Hash 表”。你一定也经常听过它但是你是不是真的理解这种数据结构呢 散列表用的是数组支持按照下标随机访问数据的特性所以散列表其实就是数组的一种扩展由数组演化而来。可以说如果没有数组就没有散列表。 我用一个例子来解释一下。假如我们有 89 名选手参加学校运动会。为了方便记录成绩每个选手胸前都会贴上自己的参赛号码。假设校长说参赛编号不能设置得这么简单要加上年级、班级这些更详细的信息所以我们把编号的规则稍微修改了一下用 6 位数字来表示。比如 051167其中前两位 05 表示年级中间两位 11 表示班级最后两位还是原来的编号 1 到 89。这个时候我们该如何存储选手信息才能够支持通过编号来快速查找选手信息呢 我们可以把这 89 名选手的信息放在数组里。尽管我们不能直接把编号作为数组下标但我们可以截取参赛编号的后两位作为数组下标来存取选手信息数据编号为01 的选手我们放到数组中下标为 1 的位置编号为 02 的选手我们放到数组中下标为 2 的位置。以此类推编号为 k 的选手放到数组中下标为 k 的位置。
这就是典型的散列思想。其中参赛选手的编号我们叫做键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)。 第一点和第二点理解起来比较简单第三点理解起来可能会有问题。这个要求看起来合情合理但是在真实的情况下要想找到一个不同的 key 对应的散列值都不一样的散列函数几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法也无法完全避免这种散列冲突。
散列冲突
再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢我们常用的散列冲突解决方法有两类开放寻址法open addressing和链表法chaining。
开放寻址法 开放寻址法的核心思想是如果出现了散列冲突我们就重新探测一个空闲位置将其插入。那如何重新探测新的位置呢我先讲一个比较简单的探测方法线性探测Linear Probing。当我们往散列表中插入数据时如果某个数据经过散列函数散列之后存储位置已经被占用了我们就从当前位置开始依次往后查找看是否有空闲位置直到找到为止。 从图中可以看出散列表的大小为 10在元素 x 插入散列表之前已经 6 个元素插入到散列表中。x 经过 Hash 算法之后被散列到位置下标为 7 的位置但是这个位置已经有数据了所以就产生了冲突。于是我们就顺序地往后一个一个找看有没有空闲的位置遍历到尾部都没有找到空闲的位置于是我们再从表头开始找直到找到空闲位置 2于是将其插入到这个位置。 我们通过散列函数求出要查找元素的键值对应的散列值然后比较数组中下标为散列值的元素和要查找的元素。如果相等则说明就是我们要找的元素否则就顺序往后依次查找。如果遍历到数组中的空闲位置还没有找到就说明要查找的元素并没有在散列表中。 散列表跟数组一样不仅支持插入、查找操作还支持删除操作。对于使用线性探测法解决冲突的散列表删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。我们可以将删除的元素特殊标记为 deleted。当线性探测查找的时候遇到标记为 deleted 的空间并不是停下来而是继续往下探测。 你可能已经发现了线性探测法其实存在很大问题。当散列表中插入的数据越来越多时散列冲突发生的可能性就会越来越大空闲位置会越来越少线性探测的时间就会越来越久。 对于开放寻址冲突解决方法除了线性探测方法之外还有另外两种比较经典的探测方法二次探测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”或者“槽slot”会对应一条链表所有散列值相同的元素我们都放到相同槽位对应的链表中。 插入的时候我们只需要通过散列函数计算出对应的散列槽位将其插入到对应链表中即可所以插入的时间复杂度是 O(1)。当查找、删除一个元素时我们同样通过散列函数计算出对应的槽然后遍历链表查找或者删除。那查找或删除操作的时间复杂度是多少呢实际上这两个操作的时间复杂度跟链表的长度 k 成正比也就是 O(k)。对于散列比较均匀的散列函数来说理论上讲kn/m其中 n 表示散列中数据的个数m 表示散列表中“槽”的个数。
解答开篇
Word 文档中单词拼写检查功能是如何实现的 常用的英文单词有 20 万个左右假设单词的平均长度是 10 个字母平均一个单词占用 10 个字节的内存空间那 20 万英文单词大约占 2MB 的存储空间就算放大 10 倍也就是 20MB。对于现在的计算机来说这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。当用户输入某个英文单词时我们拿用户输入的单词去散列表中查找。如果查到则说明拼写正确如果没有查到则说明拼写可能有误给予提示。借助散列表这种数据结构我们就可以轻松实现快速判断是否存在拼写错误。
