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

在之前我们已经学过了二分查找和简单查找,我们知道二分查找的运行时间为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,就该调整散列表的长度

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

原文发布于微信公众号 - 小白客(youcoding)

原文发表时间:2018-01-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【专业技术第十三讲】指针和内存泄露

存在问题: 指针是大家最为头痛的问题,也是程序bug中较难解决的错误,什么情况下会导致内存泄露? 解决方案: 引言 对于任何使用C语言的人,如果问他们C语言...

3538
来自专栏极客编程

ECMAScript 6教程 (一)

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出 原文连接,博客地址为 http://www.cnblogs.co...

892
来自专栏微信公众号:Java团长

图说Java —— 理解Java机制最受欢迎的8幅图

下面的8幅图来自于 Program Creek 的 Java教程 ,目前这是该网站最受欢迎的文章. 希望本文能帮你回顾你已经知道的那些知识。如果图片讲解的不够清...

903
来自专栏Albert陈凯

Stack and Heap 堆和栈的区别include

在和计算机内存打交道时,我们一定会碰到堆和栈,这两个东西很容易搞混,那么现在就来梳理一下二者的关系。 栈(Stack)是用来静态分配内存的而堆是动态分配内存的,...

2718
来自专栏Java学习网

Java 实现线程死锁

Java 实现线程死锁 概述 春节的时候去面试了一家公司,笔试题里面有一道是使用简单的代码实现线程的‘死锁’,当时没有想到这道题考的是Synchronized关...

2426
来自专栏我的博客

if和else匹配问题以及switch问题

$b = 1; $a = 2; if ($a > 1) { echo ‘1’; if ($b > 2) { echo ‘2’; } } else ...

35011
来自专栏魂祭心

原 Type System Overvie

3518
来自专栏每日一篇技术文章

Swift3.0 - 异常错误

811
来自专栏微信终端开发团队的专栏

C# 内存管理机制及 WP 内存泄漏定位方法

C#内存管理机制及WP内存泄漏定位方法 一、C#的内存管理机制 1. 托管资源与非托管资源 什么是托管资源?托管资源通俗的理解就是,把资源交给.net去管理,这...

3877
来自专栏猿人谷

腾讯2013年实习生笔试题目(附答案)

下面是我在参加2013年腾讯实习生招聘的笔试题目,当然啦,我个人不可能是完全的记住所有题目,部分是摘自网络的。同时,下面也有一些题目我不会的,希望大家一起商量解...

3658

扫码关注云+社区

领取腾讯云代金券