18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.pdf
《18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.pdf》由会员分享,可在线阅读,更多相关《18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.pdf(14页珍藏版)》请在三一文库上搜索。
1、18|散列表(上):Word文档中的单词拼写检查功能是如何实现的? file:/F/temp/geektime/数据结构与算法之美/18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.html2019/1/15 15:35:41 18|散列表(上):Word文档中的单词拼写检查功能是如何实现的? Word这种文本编辑器你平时应该经常用吧,那你有没有留意过它的拼写检查功能呢?一旦我们在Word里输入一个错误的英文单词,它就会用标红的方式提示“拼 写错误”。Word的这个单词拼写检查功能,虽然很小但却非常实用。你有没有想过,这个功能是如何实现的呢? 其实啊,一点儿都不难。只要你学完今
2、天的内容,散列表(Hash Table)。你就能像微软Office的工程师一样,轻松实现这个功能。 散列思想 散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash表”,你一定也经常听过它,我在前面的文章里,也不止一次提到过,但是你是不是真的理解这 种数据结构呢? 散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。 我用一个例子来解释一下。假如我们有89名选手参加学校运动会。为了方便记录成绩,每个选手胸前都会贴上自己的参赛号码。这89名选手的编号依次是1到89。 现在我们希望编程实现这样
3、一个功能,通过编号快速找到对应的选手信息。你会怎么做呢? 我们可以把这89名选手的信息放在数组里。编号为1的选手,我们放到数组中下标为1的位置;编号为2的选手,我们放到数组中下标为2的位置。以此类推,编号 为k的选手放到数组中下标为k的位置。 因为参赛编号跟数组下标一一对应,当我们需要查询参赛编号为x的选手的时候,我们只需要将下标为x的数组元素取出来就可以了,时间复杂度就是O(1)。这样 按照编号查找选手信息,效率是不是很高? 实际上,这个例子已经用到了散列的思想。在这个例子里,参赛编号是自然数,并且与数组的下标形成一一映射,所以利用数组支持根据下标随机访问的时候, 时间复杂度是O(1)这一特
4、性,就可以实现快速查找编号对应的选手信息。 你可能要说了,这个例子中蕴含的散列思想还不够明显,那我来改造一下这个例子。 假设校长说,参赛编号不能设置得这么简单,要加上年级、班级这些更详细的信息,所以我们把编号的规则稍微修改了一下,用6位数字来表示。比如051167,其 中,前两位05表示年级,中间两位11表示班级,最后两位还是原来的编号1到89。这个时候我们该如何存储选手信息,才能够支持通过编号来快速查找选手信息 呢? 思路还是跟前面类似。尽管我们不能直接把编号作为数组下标,但我们可以截取参赛编号的后两位作为数组下标,来存取选手信息数据。当通过参赛编号查询选 手信息的时候,我们用同样的方法,取
5、参赛编号的后两位,作为数组下标,来读取数组中的数据。 这就是典型的散列思想。其中,参赛选手的编号我们叫作键(key)或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散 列函数(或“Hash函数”“哈希函数”),而散列函数计算得到的值就叫作散列值(或“Hash值”“哈希值”)。 18|散列表(上):Word文档中的单词拼写检查功能是如何实现的? file:/F/temp/geektime/数据结构与算法之美/18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.html2019/1/15 15:35:41 通过这个例子,我们可以总结出这样的规律:散列表
6、用的就是数组支持按照下标随机访问的时候,时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映 射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取 数据。 18|散列表(上):Word文档中的单词拼写检查功能是如何实现的? file:/F/temp/geektime/数据结构与算法之美/18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.html2019/1/15 15:35:41 散列函数 从上面的例子我们可以看到,散列函数在散列表中起着非常关键的作用。现在我们就来学习下散列函数。 散
7、列函数,顾名思义,它是一个函数。我们可以把它定义成hash(key),其中key表示元素的键值,hash(key)的值表示经过散列函数计算得到的散列值。 那第一个例子中,编号就是数组下标,所以hash(key)就等于key。改造后的例子,写成散列函数稍微有点复杂。我用伪代码将它写成函数就是下面这样: int hash(String key) / 获取后两位字符 string lastTwoChars = key.substr(length-2, length); / 将后两位字符转换为整数 int hashValue = convert lastTwoChas to int-type; ret
8、urn hashValue; 刚刚举的学校运动会的例子,散列函数比较简单,也比较容易想到。但是,如果参赛选手的编号是随机生成的6位数字,又或者用的是a到z之间的字符串,该如何 构造散列函数呢?我总结了三点散列函数设计的基本要求: 1. 散列函数计算得到的散列值是一个非负整数; 2. 如果key1 = key2,那hash(key1) = hash(key2); 3. 如果key1 key2,那hash(key1) hash(key2)。 我来解释一下这三点。其中,第一点理解起来应该没有任何问题。因为数组下标是从0开始的,所以散列函数生成的散列值也要是非负整数。第二点也很好理解。 相同的key,
9、经过散列函数得到的散列值也应该是相同的。 第三点理解起来可能会有问题,我着重说一下。这个要求看起来合情合理,但是在真实的情况下,要想找到一个不同的key对应的散列值都不一样的散列函数,几 乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法,也无法完全避免这种散列冲突。而且,因为数组的存储空间有限,也会加大散列冲突的概率。 所以我们几乎无法找到一个完美的无冲突的散列函数,即便能找到,付出的时间成本、计算成本也是很大的,所以针对散列冲突问题,我们需要通过其他途径来 解决。 散列冲突 再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢?我们常用的散列冲突解决方法有两类,开放
10、寻址法(open addressing)和链表法 (chaining)。 1.开放寻址法 开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。那如何重新探测新的位置呢?我先讲一个比较简单的探测方法,线 性探测(Linear Probing)。 当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直 到找到为止。 18|散列表(上):Word文档中的单词拼写检查功能是如何实现的? file:/F/temp/geektime/数据结构与算法之美/18散列表(上):Word文档中的单词
11、拼写检查功能是如何实现的?.html2019/1/15 15:35:41 我说的可能比较抽象,我举一个例子具体给你说明一下。这里面黄色的色块表示空闲位置,橙色的色块表示已经存储了数据。 从图中可以看出,散列表的大小为10,在元素x插入散列表之前,已经6个元素插入到散列表中。x经过Hash算法之后,被散列到位置下标为7的位置,但是这个位 置已经有数据了,所以就产生了冲突。于是我们就顺序地往后一个一个找,看有没有空闲的位置,遍历到尾部都没有找到空闲的位置,于是我们再从表头开始 找,直到找到空闲位置2,于是将其插入到这个位置。 在散列表中查找元素的过程有点儿类似插入过程。我们通过散列函数求出要查找元
12、素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元 素。如果相等,则说明就是我们要找的元素;否则就顺序往后依次查找。如果遍历到数组中的空闲位置,还没有找到,就说明要查找的元素并没有在散列表中。 18|散列表(上):Word文档中的单词拼写检查功能是如何实现的? file:/F/temp/geektime/数据结构与算法之美/18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.html2019/1/15 15:35:41 18|散列表(上):Word文档中的单词拼写检查功能是如何实现的? file:/F/temp/geektime/数据结构与算法之美/18散列表(上
13、):Word文档中的单词拼写检查功能是如何实现的?.html2019/1/15 15:35:41 散列表跟数组一样,不仅支持插入、查找操作,还支持删除操作。对于使用线性探测法解决冲突的散列表,删除操作稍微有些特别。我们不能单纯地把要删除的 元素设置为空。这是为什么呢? 还记得我们刚讲的查找操作吗?在查找的时候,一旦我们通过线性探测方法,找到一个空闲位置,我们就可以认定散列表中不存在这个数据。但是,如果这个空 闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被认定为不存在。这个问题如何解决呢? 我们可以将删除的元素,特殊标记为deleted。当线性探测查找的时候,遇到标记为
14、deleted的空间,并不是停下来,而是继续往下探测。 18|散列表(上):Word文档中的单词拼写检查功能是如何实现的? file:/F/temp/geektime/数据结构与算法之美/18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.html2019/1/15 15:35:41 你可能已经发现了,线性探测法其实存在很大问题。当散列表中插入的数据越来越多时,散列冲突发生的可能性就会越来越大,空闲位置会越来越少,线性探测 的时间就会越来越久。极端情况下,我们可能需要探测整个散列表,所以最坏情况下的时间复杂度为O(n)。同理,在删除和查找时,也有可能会线性探测整张散 列表,才能找
15、到要查找或者删除的数据。 对于开放寻址冲突解决方法,除了线性探测方法之外,还有另外两种比较经典的探测方法,二次探测(Quadratic probing)和双重散列(Double hashing)。 所谓二次探测,跟线性探测很像,线性探测每次探测的步长是1,那它探测的下标序列就是hash(key)+0,hash(key)+1,hash(key)+2而二次探测探测的步长就变 成了原来的“二次方”,也就是说,它探测的下标序列就是hash(key)+0,hash(key)+12,hash(key)+22 18|散列表(上):Word文档中的单词拼写检查功能是如何实现的? file:/F/temp/ge
16、ektime/数据结构与算法之美/18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.html2019/1/15 15:35:41 所谓双重散列,意思就是不仅要使用一个散列函数。我们使用一组散列函数hash1(key),hash2(key),hash3(key)我们先用第一个散列函数,如果计算得到的存 储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置。 不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证 散列表中有一定比例的空闲槽位。我们用装载因子(load facto
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 18 列表 Word 文档 中的 单词 拼写 检查 功能 如何 实现
链接地址:https://www.31doc.com/p-5529984.html