举报文档 收藏
/14
帮帮创意 > 其他文档 > 18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.pdf

18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.pdf

18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.pdf
内容要点:
18|散列表(上):Word文档中的单词拼写检查功能是如何实现的?file:///F/temp/geektime/数据结构与算法之美/18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.html[2019/1/15 15:35:41]18|散列表(上):Word文档中的单词拼写检查功能是如何实现的?Word这种文本编辑器你平时应该经常用吧,那你有没有留意过它的拼写检查功能呢?一旦我们在Word里输入一个错误的英文单词,它就会用标红的方式提示“拼写错误”。Word的这个单词拼写检查功能,虽然很小但却非常实用。你有没有想过,这个功能是如何实现的呢?其实啊,一点儿都不难。只要你学完今天的内容,散列表(Hash Table )。你就能像微软Office的工程师一样,轻松实现这个功能。散列思想散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash表”,你一定也经常听过它,我在前面的文章里,也不止一次提到过,但是你是不是真的理解这种数据结构呢?散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。我用一个例子来解释一下。假如我们有89名选手参加学校运动会。为了方便记录成绩,每个选手胸前都会贴上自己的参赛号码。这89名选手的编号依次是1到89。现在我们希望编程实现这样一个功能,通过编号快速找到对应的选手信息。你会怎么做呢?我们可以把这89名选手的信息放在数组里。编号为1的选手,我们放到数组中下标为1的位置;编号为2的选手,我们放到数组中下标为2的位置。以此类推,编号为k的选手放到数组中下标为k的位置。因为参赛编号跟数组下标一一对应,当我们需要查询参赛编号为x的选手的时候,我们只需要将下标为x的数组元素取出来就可以了,时间复杂度就是O(1)。这样按照编号查找选手信息,效率是不是很高?实际上,这个例子已经用到了散列的思想。在这个例子里,参赛编号是自然数,并且与数组的下标形成一一映射,所以利用数组支持根据下标随机访问的时候,时间复杂度是O(1)这一特性,就可以实现快速查找编号对应的选手信息。你可能要说了,这个例子中蕴含的散列思想还不够明显,那我来改造一下这个例子。假设校长说,参赛编号不能设置得这么简单,要加上年级、班级这些更详细的信息,所以我们把编号的规则稍微修改了一下,用6位数字来表示。比如051167,其中,前两位05表示年级,中间两位11表示班级,最后两位还是原来的编号1到89。这个时候我们该如何存储选手信息,才能够支持通过编号来快速查找选手信息呢?思路还是跟前面类似。尽管我们不能直接把编号作为数组下标,但我们可以截取参赛编号的后两位作为数组下标,来存取选手信息数据。当通过参赛编号查询选手信息的时候,我们用同样的方法,取参赛编号的后两位,作为数组下标,来读取数组中的数据。这就是典型的散列思想。其中,参赛选手的编号我们叫作键(key)或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散列函数(或“Hash函数”“哈希函数”),而散列函数计算得到的值就叫作散列值(或“Hash值”“哈希值”)。www.bbcyw.com18|散列表(上):Word文档中的单词拼写检查功能是如何实现的?file:///F/temp/geektime/数据结构与算法之美/18散列表(上):Word文档中的单词拼写检查功能是如何实现的?.html[2019/1/15 15:35:41]通过这个例子,我们可以总结出这样的规律:散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是O(1)的特性。我们通过散列函数把元素的

发表评论

暂无评论,赶快抢占沙发吧。

紫竹****嫣

在线客服