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

软件环境: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 条评论
登录 后参与评论

相关文章

来自专栏python3

python3--文件操作

rb,只读,以bytes类型读取(非文字类的文件时,用rb,比如图片,音频文件等)

2352
来自专栏Java帮帮-微信公众号-技术文章全总结

Java并发编程,一定要有自己的理解【面试+工作】

编写优质的并发代码是一件难度极高的事情。Java语言从第一版本开始内置了对多线程的支持,这一点在当年是非常了不起的,但是当我们对并发编程有了更深刻的认识和更多的...

1597
来自专栏ChaMd5安全团队

HBCTF第一场2个pwn题的简单分析

【ChaMd5安全团队所有文章均来源实战,为保证厂商安全信息,文章内容以思路为主。 需要转载,请先联系ChaMd5安全团队授权。 未经授权请勿转载。】...

47410
来自专栏瓜大三哥

​UVM(九)之sequencej机制续1

UVM(九)之sequencej机制续1 当一个sequence启动起来之后,UVM会自动执行sequence的body任务,所以要产生各种和杨的激励,就要写好...

26510
来自专栏逢魔安全实验室

CVE-2018-2628 Weblogic反序列化POC重构详解

3925
来自专栏程序员宝库

JAVA 中异常处理的最佳实践

前言 异常处理的问题之一是知道何时以及如何去使用它。我会讨论一些异常处理的最佳实践,也会总结最近在异常处理上的一些争论。 作为程序员,我们想要写高质量的能够解决...

3168
来自专栏技术换美食换不换

php

htmllentitles()/unhtml()/urlencode()/urldecode/

2141
来自专栏Golang语言社区

Golang使用pprof监控性能及GC调优

作者:峰云就她了 链接:http://xiaorui.cc/?p=3000 來源:个人博客

4033
来自专栏*坤的Blog

Java分层概念(转)

9024
来自专栏积累沉淀

Python快速学习第十二天--生成器和协程

yield指令,可以暂停一个函数并返回中间结果。使用该指令的函数将保存执行环境,并且在必要时恢复。 生成器比迭代器更加强大也更加复杂,需要花点功夫好好理解贯...

8275

扫码关注云+社区

领取腾讯云代金券