首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每天学习一点儿算法--散列表

每天学习一点儿算法--散列表

作者头像
爱吃西瓜的番茄酱
发布2018-04-04 14:30:04
8960
发布2018-04-04 14:30:04
举报

在之前我们已经学过了二分查找和简单查找,我们知道二分查找的运行时间为O(㏒ n), 简单查找的运行时间为O(n)。除此之外,还有没有更快的查找算法呢?

可能有人会说数组的查找速度更快,查找速度为O(1)。没错,但是我们今天讲的是一种进化版的类似于数组的数据结构—散列表。

散列表的性能取决于散列函数,那什么是散列函数呢?

散列函数

散列函数是这样的函数,即无论你给它什么数据,它都还你一个数字。专业术语来描述就是:将输入映射到数字。

散列函数需要满足一些要求:

  • 它必须是一致性的,就是同样的输入必须映射到相同的数字。
  • 它应该将不同的输入映射到不同的数字。但绝大多数情况是达不到这种要求的,这就产生了冲突。关于冲突的介绍,后面再讲。

散列函数和数组结合在一起就创建了一种名为散列表的数据结构。散列表是一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存,但散列表更复杂,它使用散列函数来确定元素的存储位置。

几乎每种语言都提供了散列表的实现方式。Python提供的散列表实现为字典,我们可以使用函数dict()来创建散列表。

>>> book = dict()

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

>>> book = {}

以上两种方式是等效的。

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

>>> book = dict()
>>> book["apple"] = 8
>>> book["banana"] = 5
>>> book["milk"] = 4
>>> print(book)
{'apple': 8, 'banana': 5, 'milk': 4}

现在我们来查询香蕉的价格:

>>> print (book["banana"])
5

这就实现了一个简单的散列表。

散列表由键和值组成,散列函数将键映射到值。在Python中使用字典来实现散列表,如果对字典不太熟悉的同学,可以看我以前关于字典的文章:Python基础学习-字典

散列表的应用

将散列表用于查找

散列表被用于大海捞针式的查找。当我们访问一个网站的时候,我们输入类似于:www.baidu.com这样的域名,然后通过DNS解析到一个IP地址。这里将网站地址映射到IP地址,就是运用了散列表的功能。

将散列表用作缓存

缓存是一种常用了加速方式,它可以使用我们浏览网站更加快速,所有的大型网站都使用缓存,而缓存的数据则是存储在散列表中的。其基本原理是将页面url映射到页面数据。

冲突

由于大多数语言都提供了散列表的实现方式,所以我们可以不必深究散列表的内部实现原理,但我们必须要考虑散列表的性能。

关于散列表的性能我们首先要了解一个名为冲突的概念。理想的情况是散列函数总将不同的输入映射到数组的不同位置,但实际上,几乎没有这样的散列函数。我们来看一个示例,假设有一个数组,它包含了26个位置:

使用的散列函数非常简单,它按照字母表顺序分配数组的位置。先将苹果的价格存储到散列表中,分配给第一个位置:

接下来将香蕉的价格存储到散列表中,分配给第二个位置:

接下来再将杏仁的价格存储在散列表中,由于杏仁的英文单词为apricot,分配给它的又是第一个位置:

但是这个位置已经存储了苹果的价格,怎么办?这种情况被称为冲突:给两个键分配了相同的位置。

处理冲突的方式有很多,最简单的一种就是在发生冲突的位置存储一个链表:

所以,一个好的散列函数对于散列表的性能尤其重要。

性能

在平均情况下,散列表执行各项操作的时间都为O(1)。O(1)被称为常量时间。

简单查找的运行时间为线性时间:

二分查找的所需时间为对数时间:

在散列表中查找所花费的时间为常量时间:

在最糟情况下,散列表所有的操作的运行时间都为O(n)—线性时间。下面将散列表同数组和链表比较一下:

为了避免冲突,需要有:

  • 较低的填装因子
  • 良好的散列函数
填装因子

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

填装因子越低,发生冲突的可能性越小,散列表的性能越高,一个不错的经验是:一旦填装因子大于0.7,就调整散列表的长度。

良好的散列函数

良好的散列函数可以使数组中的值呈均匀分布。什么样散列函数是良好的呢,有兴趣的话,可以去研究一下SHA函数。这里不做介绍,因为我也不懂~

小结

  • 在Python中使用字典来实现散列表
  • 散列表的查找、插入和删除都很快
  • 散列表适合于模拟映射关系
  • 散列表可用于缓存数据
  • 一旦填装因子超过0.7,就该调整散列表的长度

每天学习一点点,每天进步一点点。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-01-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小白客 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 将散列表用于查找
  • 将散列表用作缓存
  • 填装因子
  • 良好的散列函数
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档