《算法图解》第五章笔记与课后练习_散列函数与散列表

软件环境:Python 3.7.0b4

一、散列函数

无论你给它什么数据,它都还你一个数字。它必须满足一些要求:

  • 它必须是一致的。例如,假设你输入apple时得到的是4,那么每次输入apple时,得到的都必须为4。
  • 它应将不同的输入映射到不同的数字。例如,如果一个散列函数不管输入是什么都返回1,那它就不是好的散列函数。最理想的情况是 将不同的输入映射到不同的数字。

使用函数dict来创建散列表

>>> book = dict()
>>> book["apple"] = 0.67  # 一个苹果的价格是67美分
>>> book["milk"] = 1.49
>>> book["avocado"] = 1.60
>>> print(book)
{'apple': 0.67, 'milk': 1.49, 'avocado': 1.6}
>>> print(book["milk"])
1.49   # 牛奶的价格

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

二、应用案例

1,将散列表用于查找

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

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

下面我们来使用散列表进行对电话簿的创建映射和查找。

2,防止重复

假如你负责管理一个投票站,每个人只能投一票,如何避免重复投票呢?

voted = {} # 创建一个散列表
def check_voter(name):
  if voted.get(name): # 检查他是否在散列表中
    print("kick them out!")
  else:
    voted[name] = True
    print("let them vote!")

3,将散列表用作缓存

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

缓存的优点:

  • 用户能够更快地看到网页。
  • 服务器需要做的工作很少。
cache = {}

def get_page(url):
    if cache.get(url):
        return cache[url] # 返回缓存的数据
    else:
        data = get_data_from_server(url)
        cache[url] = data # 先将数据保存到缓存中
        return data

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

三、小结

  • 可以结合散列函数和数组来创建散列表。
  • 散列表的查找、插入和删除的操作速度都非常快。
  • 散列表适合用于模拟映射的关系。
  • 散列表可用于缓存数据(例如在Web服务器上)。
  • 散列表非常适合用于防止重复。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏架构师之路

如何设计好的接口(Google分享)

本文源自Google工程师joshua bloch的经验分享,楼主进行了整理和总结。 一、好接口的特性 (1)易学 (2)易用,甚至不需要文档 (3)难于误用 ...

3466
来自专栏韩伟的专栏

架构实现利器:反射

假设我们希望开发一套通用型的软件框架,这个框架允许用户自定义大量不同的情况下的回调函数(方法),用来实现丰富多彩的业务逻辑功能,例如一个游戏脚本引擎,那么,其中...

4640
来自专栏CSDN技术头条

写出优质Java代码的4个技巧

我们平时的编程任务不外乎就是将相同的技术套件应用到不同的项目中去,对于大多数情况来说,这些技术都是可以满足目标的。然而,有的项目可能需要用到一些特别的技术,因此...

1857
来自专栏屈定‘s Blog

设计模式--模板方法模式的思考

模板方法同样也是一种很实用的方法,目的是提高代码复用,并且统一大体的算法流程,比如一个一台电脑主机,定义好放置CPU,硬盘,内存等空位后,就形成了一个骨架,那么...

1304
来自专栏有趣的django

21天打造分布式爬虫-urllib库(一)

urlparse和urlsplit都是用来对url的各个组成部分进行分割的,唯一不同的是urlsplit没有"params"这个属性.

773
来自专栏程序员互动联盟

【编程技巧】提高程序员技能的11招

1.清晰的分析问题 2.三思而后行如何解决这个问题 3.收集完整的需求。 花点时间,想好产品的目标形态和最终的用户群。在这个阶段思路清晰会给以后节省很多时间。 ...

3377
来自专栏葡萄城控件技术团队

当心那些有歧义的命名

关键点 “别人还能把这个名字理解成什么意思?”通过不断的问自己这个问题来积极检查每一个命名。 事实上,这种富有创造性的、不断尝试“错误理解”的方法,能够有...

1776
来自专栏编程

设计模式启示录(二)

设计模式启示录(二) 在【设计模式启示录 (一)】中,重点介绍了设计模式的精髓(抽象),设计模式的分类(按抽象的目的进行分类)。在本篇中,将按照前述的七大分类,...

1687
来自专栏码农阿宇

设计模式快速学习(一)

UML类图 ? 简单工厂模式 1.1类图 ? 策略模式 2.1策略模式结构图 ? 2.2策略模式解析 策略模式时一种定义一系列算法的方法,从概念上看,所有这...

2443
来自专栏算法修养

PHP 正则表达式抓取网页内容。

我想用php抓取爱奇艺生活类型视频网页里面的元素,应该如何去做呢? 首先我要非常熟悉正则表达式,关于正则表达式的学习,我会写一篇博客一直学习的。 直接举例子: ...

2756

扫码关注云+社区