《算法图解》第五章笔记与课后练习

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

相关文章

来自专栏积累沉淀

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

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

8275
来自专栏python3

python3--文件操作

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

2332
来自专栏欧阳大哥的轮子

iOS的MVC框架之控制层的构建(上)

在我前面的两篇文章里面分别对MVC框架中的M层的定义和构建方法进行了深入的介绍和探讨。这篇文章则是想深入的介绍一下我们应该如何去构建控制层。控制层是联系视图层和...

1182
来自专栏程序员宝库

JAVA 中异常处理的最佳实践

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

3168
来自专栏JAVA烂猪皮

BAT面试常的问题和最佳答案

客户端发出http请求,web服务器将请求转发到servlet容器,servlet容器解析url并根据web.xml找到相对应的servlet,并将reques...

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

php

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

2141
来自专栏*坤的Blog

Java分层概念(转)

8964
来自专栏信安之路

2017-NSCTF-PWN

这次比赛值得吐槽的地方很多,但是我要忍住,先讲正经的。 这次总结比赛的两道pwn,都是栈溢出类型的,比较简单。先放上题目链接:http://pan.baidu....

940
来自专栏小灰灰

SPI框架实现之旅一:背景介绍

SPI框架实现之旅一:背景介绍 SPI的全名为Service Provider Interface,简单的总结下java spi机制的思想。我们系统里抽象的各...

25910
来自专栏章鱼的慢慢技术路

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

1865

扫码关注云+社区

领取腾讯云代金券