当前位置:   article > 正文

【数据结构】哈希表(也称散列表)——入门这一篇就够了!_哈希表应用实例

哈希表应用实例

目录

1. 基础背景

2. 哈希函数(也称散列函数)

3. 应用案例

3.1 将散列表用于查找

3.2 防止重复

3.3 将散列表用作缓存

4. 冲突

5. 性能

5.1 填装因子

5.2 良好的散列函数


1. 基础背景

在讲散列表之前,我们先回顾总结下两种最基本数据结构——数组和链表的基本特点。

数组:寻址容易,插入和删除元素困难;

链表:寻址困难,插入和删除元素容易。

下面还是举例开始:

假设你在一家杂货铺上班。有顾客来买东西,你需要在一个单子上查找商品的价格。如果单子的内容是无序的,你可能会为了查找apple的价格而浏览每一行。这需要O(n)的时间。如果单子是有序的,则可以使用二分查找找出苹果的价格,运行时间为O(log n)。我们应该可以想象,运行时间O(n)与O(log n)之间存在着天壤之别。

 虽然二分查找已经非常快了,但是作为收银员,哪怕用于一个有序的表单,查找价格时,客人也会对你不满。理想情况下,是有一个知道所有商品价格的雇员,这样就无须查找,问她就能立刻知道答案,这位雇员(假设她叫Maggie)报出任何商品的价格的时间都是O(1),速度比二分查找还快。

下面从数据结构的角度来看看。前面介绍了两种数据结构:数组和链表(其实还有栈,但栈并不能用于查找)。你可使用数组来实现记录商品价格的本子。

这种数组包含两项内容:商品名称和价格。如果将这个数组按商品名进行排序,就可以使用二分查找来查找其中的商品价格。这样查找价格的时间将为O(log n)。然而,我们期望查找商品的时间为O(1),这时就是散列表起作用的场合了。

2. 哈希函数(也称散列函数)

散列函数是这样的函数,无论你给它什么数据,它都还你一个数据:

散列函数,即使“将输入映射到数字”。你可能你认为散列函数输出的数字没有什么规律,但散列函数必须满足一些基本要求:

  1. 必须是一致的。如果你输入Apple时得到的是4,那么每次输入Apple时,得到的都必须是4。如果不满足这一前提,散列表将一无是处。
  2. 应该将不同的输入相对地映射到不同的数字。例如,如果一个三类白哦不管输入是什么都返回1,它就不是好的函数。最理想的情况是,将不同的输入映射到不同的数字。

散列表将输入映射到数字,具体有什么用途呢?它可以用来打造运行时间为O(1)的“Maggie”。为此,首先创建一个空数组。

我们将在这数组中存储商品的价格。下面来将苹果的价格加入到这个数组中。为此,将Apple作为输入交给散列表。

 

散列函数的输出为3,因此我们将苹果的价格从存储到数组索引3处。

同理,将牛奶的价格存储到数组中。为此,将牛奶作为散列函数的输入。

散列函数输出为0,因此我们将牛奶的价格存储咋索引0处。

不断地重复这个过程,最终整个数组将填满价格。

现在,假设你要知道鳄梨(avocado)的价格,你无需在数组中查找,只需将鳄梨作为输入交给散列函数即可。

它将告诉你鳄梨的价格存储在索引4处。果然,你在那里找到了。

散列函数准确地指出了存储位置,你根本无需查找!之所以能够这样,具体原因如下:

  • 散列函数总是将同样的输入映射到相同的索引。每次输入avocado,得到的都是同一个数字。因此,你可以首先使用散列函数确定鳄梨价格存储在什么地方,并在以后使用它来确定鳄梨的价格存储在什么地方。
  • 散列函数将不同的输入映射到不同的索引。avocado映射到索引4,milk映射到索引0。每种商品都映射到数组的不同位置,让你能够将其价格存储到这个位置。
  • 散列函数知道数组有多大,只返回有效的索引。如果数组包含5个元素,散列函数就不会返回无效索引100。

刚才你就打造了一个“Maggie”,结合使用散列函数和数组创建一种被称为 散列表(hash table)  的数据结构。散列表是比较有代表的包含了额外逻辑的数据结构。数组和链表都被直接映射到内存,但散列表更复杂,它使用散列函数来确定元素的存储位置。

在复杂数据结构中,散列表可能是最有用的,也被称为散列映射、映射、字典和关联数组。散列表的速度非常快,因为散列表使用数组来存储数据,因此其获取元素的速度与数组一样快。

你可能根本不需要自己实现散列表,任何一种优秀的语言都会提供散列表实现。Python提供的散列表实现为字典, 你可以使用dict来创建散列表。

>>> book = dict()

创建散列表book后,在其中添加一些商品的价格。

  1. >>> book["apple"] = 0.67
  2. >>> book["milk"] = 1.49
  3. >>> book["avocado"] = 1.49
  4. >>> print book
  5. {'avocado': 1.49, 'apple': 0.67, 'milk': 1.49}

 非常简单,现在即可快速查询鳄梨的价格。

  1. >>> print book["avocado"]
  2. 1.49

散列表由键和值组成。在前面的散列表book中,键为商品名,值为商品价格。散列表将键映射到值。

3. 应用案例

3.1 将散列表用于查找

手机内都内置了方便的电话簿,其中每个名字都有对应的电话号码。

假设你要创建一个类似这样的电话簿,将姓名映射到电话号码。该电话薄需要提供如下功能:

  • 添加联系人及其电话号码
  • 通过输入联系人来获悉其电话号码

这就非常适合使用散列表来实现!在下述情况下,使用散列表是很不错的选择。

  • 创建映射;
  • 查找。

创建电话簿非常容易。首先,新建一个散列表。

>>> phone_book = dict()

Pyhton还提供了一种创建散列表的快捷方式——使用一对大括号。

>>> phone_book = {}    #与 phone_book=dict() 等效

下面在这个电话薄中添加一些联系人的电话号码。

  1. >>> phone_book["jenny"] = 8675309
  2. >>> phone_book["emergency"] = 911

这时散列表就创建完成了,现在你要查找Jenny的电话号码只需要向散列表传入相应的键。

  1. >>> print(phone_book["jenny"]
  2. 8675309

散列表可以轻松地模拟映射关系。散列表常被用于大海捞针式的查找。例如,你在访问像http://www.cc98.org这样的网站时,计算机必须将www.cc98.org转换为IP地址。当然,无论访问哪个网站,其网站都必须转换为IP地址。

 这不是将网址映射到IP地址吗?好像非常适合使用散列表!这个过程被称为DNS解析( DNS resolution) ,散列表是提供这种功能的方式之一。

3.2 防止重复

假设你负责管理一个投票站。显然,每人只能投一票,但如何避免重复投票呢?有人来投票,询问他的全名,并将其与已投票者名单进行对比。

如果名字在名单中,就说明这个人投过票了,因此将他拒之门外!否则,就将他的姓名加入到名单中,并让他投票。现在假设有很多人来投过了票,因此名单很长。

每次有人来投票时,你都得浏览这个长长的名单,以确定他是否投过票。但有一种更好的办法,那就是使用散列表!

为此,首先创建一个散列表,用于记录已投票的人。

>>> voted = {}

有人来投票时,检查他是否在散列表中。

>>> value = voted.get("tom")

如果“tom”在列表中,函数get将返回它;否则返回None。你可使用这个函数检查来投票的人是否投过票。

 代码如下:

  1. voted = {}
  2. def check_voter(name):
  3. if voted.get(name):
  4. print "kick them out!"
  5. else:
  6. voted[name] = True
  7. print "let them vote!"

然后测试几次:

  1. >>> check_voter("tom")
  2. let them vote!
  3. >>> check_voter("mike")
  4. let them vote!
  5. >>> check_voter("mike")
  6. kick them out!

如果你将已投票者的姓名存储在列表中,这个函数的速度将变得非常慢,因为它必须使用简单查找搜索整个列表。但是这里将它们存储在散列表中,而散列表让你能够迅速知道来投票的人是否投过票。使用散列表来检查是否重复,速度非常快。

3.3 将散列表用作缓存

如果你在网站工作,可能听说过进行缓存是一种不错的做法。下面简要地介绍其中的原理。假设你访问网站Facebook.com。

  1. 你向Facebook的服务器发出请求;
  2. 服务器做些处理,生成一个网页并将其发送给你;
  3. 你获得了一个网页。

 例如,Facebbok的服务器可能搜索你朋友的最近活动,以便向你显示这些信息,这需要几秒钟的时间。作为用户的你,可能感觉这几秒钟很久,进而认为Facebook怎么这么慢!另一方面,Facebook的服务器必须为数以百万的用户提供服务,每个人的几秒钟累积起来就相当多了。为服务好所有用户,Facebook的服务器实际上在很努力的工作。有没有办法让Facebook的服务器少做些工作,从而提高Facebook网站的访问速度呢?

假设你有一个侄女,总是问你有关星球的问题。红星离地球有多远?月球呢?木星呢?每次你都得在谷歌搜索再告诉她答案。这需要几分钟的时间。假设她老是问你月球的距离,很快你就记住了月球离地球238900英里。因此不必去谷歌搜索,你就直接告诉她答案。这就是缓存的工作原理:网站将数据记住,而不再重新计算。

如果你登录了Facebook,你看到的所有内容都是为你定制的。你每次访问faceboo.com,其服务器都需考虑你感兴趣的是什么内容。但如果你没有登录,看到的将是登录页面。每个人看到的登录页面都相同。Facebook被反复要求做同样的事情:“当我注销时,请向我显示主页”。有鉴于此,它不让服务器去生成主页,而是将主页存储起来,并在需要时将其直接发给用户。

 这就是缓存,具有如下两个优点。

  1. 用户能够更快地看到网页,就像你记住了月球与地球之间的距离时一样。下次你侄女问你时,你就不需要谷歌搜索了,立刻就可以告诉她答案;
  2. Facebook需要做的工作更少。

缓存是一种常用的加速方式,所有的大型网站都使用缓存,而缓存的数据则存储在散列表中!

Facebook不仅缓存主页,还缓存about页面、contact页面、terms and conditions页面等众多其他的页面。因此,它需要将页面URL映射到页面数据。

当你访问Facebook页面时,它首先检查散列表是否存储了该页面。

具体的代码如下:

  1. cache = {}
  2. def get_page(url):
  3. if cache.get(url):
  4. return cache[url] #返回缓存的数据
  5. else:
  6. data = get_data_from_server(url)
  7. cache[url] = data
  8. return data #先将数据保存到缓存中

仅当URL不在缓冲中,你才让服务器做些处理,并将处理生成的数据存储到缓存中,再返回它。这样,当下次有人请求该URL时,你就可以直接发送缓存中的数据,而不用再让服务器进行处理了。


4. 冲突

前面说过,大多数语言都提供了散列表实现,你不用知道如何实现它们。有鉴于此,我就不再过多地讨论散列表的内部细节,但你依然需要考虑性能!要明白散列表的性能,你得先搞清楚什么是冲突。

前面为了简化问题,散列函数总是将不同的键值映射到数组的不同位置。

而实际上,几乎不可能编写出这样的散列函数。我们来看一个简单的示例。假设你有一个数组,它包含26个位置。

而你使用的散列函数也非常简单,它按照字母顺序分配数组的位置。

你可能已经看出了问题。如果你要将苹果的价格存储到散列表中,分配给你的是第一个位置。

接下来,你要将香蕉的价格存储在散列表中,分配给你的是第二个位置。

看似一切顺利,但现在你要将鳄梨的价格存储在散列表中,分配给你的又是第一个位置。

不好,这个位置已经存储了苹果的价格。这种情况叫做 冲突(collision):给两个键分配的位置相同。这是一个问题。如果你直接将鳄梨的价格存储到这个位置,安静覆盖苹果的价格,以后查询苹果价格时,得到的将是鳄梨的价格!冲突就很糟糕,必须要避免。处理冲突的方式很多,最简单的办法如下:如果两个键映射到了同一个位置,就在这个位置存储一个链表。

在这个例子中,Apple和avocado映射到了同一位置,因此在这个位置存储一个链表。在需要查询香蕉价格时,速度依然很快。但在需要查询苹果的价格时,速度要慢些:你必须在相应的链表中找到Apple。如果这个链表很短,也没什么大不了——只需搜索三四个元素。但是,假设你工作的杂货铺只销售以A大头的商品。

这是,除了第一个位置,整个散列表都是空的,而第一个位置包含一个很长的列表!换言之,这个散列表中的所有元素都在这个链表中,这与一开始就将所有元素存储到一个链表中一样糟糕:散列表的速度会变得很慢。

这里的经验教训有两个:

  1. 散列函数非常重要。前面的散列函数将所有的键都映射到了一个位置,而最理想的情况是。散列函数将键均匀地映射到散列表的不同位置。
  2. 如果散列表存储的链表很长,散列表的速度将急剧下降。然而,如果使用的散列函数很好,这些链表就不会很长!

散列函数非常重要,好的散列函数会很少导致冲突。那么,如何选择好的散列函数呢?

5. 性能

开头我们假设你在杂货店工作。你想打造一个让你能迅速获悉商品价格的工具,而散列表的速度确实很快。

在平均情况下,散列表执行各种操作的时间都是O(1)。O(1)被称为 常量时间 。你以前可能没有见过常量时间,它并不意味着马上,而是说不管散列表多大,所需的时间都相同。例如,你知道的,简单查找的运行时间为线性时间。二分查找的速度更快,所需时间为对数时间。在散列表中查找所花费的时间为常量时间。

散列表中查找所需时间为一条直线!这意味着无论散列表包含一个元素还是10亿个元素,从中获取数据所需的时间都相同。实际上,你以前肯定也见过常数时间——从数组中获取一个元素所需的时间就是固定的:不管数组多大,从中获取一个元素所需的时间都是相同的。在平均情况下,散列表的速度确实很快。

在最糟糕情况下,散列表所有操作的运行时间都为O(n)——线性时间,这真的很慢。我们来将散列表同数组和链表比较一下。

在平均情况下,散列表的查找(获取给定索引处的值)速度应该和数组一样快,而插入和删除速度与链表一样快,即它兼具了两者的优点!但在最糟糕情况下,散列表的各种操作的速度都很慢。因此,在使用散列表时,避开最糟糕情况至关重要!为此,需要避免冲突,需要有:

  1. 较低的填装因子(后面会说);
  2. 良好的散列函数

5.1 填装因子

散列表的填装因子很容易计算:

散列表使用数组来存储数据,因此你需要计算数组中被占用的位置数。例如,下述散列表的填装因子为2/5,即0.4.

下面这个散列表的填装因子为多少呢?

 

如果你觉得时1/3,那么就对了。填装因子度量的是散列中有多少位置是空的。 假设你要在散列表中存储100种商品的价格,而该散列表包含100个位置。那么在最佳情况下,每个商品都将有自己的位置。

这个散列表的填装因子就是1 。如果这个散列表只有50个位置呢?填装因子将为2.不可能让每种商品都有自己的位置,因此没有足够的位置!填装因子大于1意味着商品数量超过了数组的位置数。一旦填装因子开始增大,你就需要在散列表中添加位置,这被称为 调整长度(resizing)

 例如,假设有一个像下面这样相当满的散列表。

这就需要调整它的长度。为此,你首先创建一个更长的新数组:通常将数组增长一倍。

接下来,你需要使用函数hash将所有元素都插入到这个新的散列表中。

 这个新散列表的填装因子为3/8,比原来的低多了!填装因子越低,发生冲突的可能性就越小,散列表的性能越高,一个不错的经验规则是:一旦填装因子大于0.7,就调整列表的长度。

你可能在想,调整散列表长度的工作需要很长时间!你说的没错,调整长度的开销很大,因此你不会希望频繁地这样做。但平均而言,即便考虑到调整长度所需的时间,散列表操作所需的时间也为O(1)。

5.2 良好的散列函数

良好的散列函数让数组中的值呈均匀分布。

糟糕的散列函数让值扎堆,导致大量的冲突。

什么样的散列函数又是良好的呢?你根本不用操心——大佬会解决这样的问题。如果你好奇,可以研究下SHA函数,它可以用作散列函数。

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/959928
推荐阅读
相关标签
  

闽ICP备14008679号