学习
实践
活动
专区
工具
TVP
写文章

《算法图解》读书笔记 Chapter 5

阅读文本大概需要 4 分钟。

散列表

散列表的常见用途

冲突

性能

小结

在本章中,书中通过讲一个查找商品价格的例子来引入散列函数,表现出了它的优越性,还是很有意思的。

(1)在本子中查找商品价格

内容不按字母排序 —— 简单查找O(n)

内容按字母排序 —— 二分查找O(logn)

希望查找商品的时间变为O(1) —— 散列函数

散列函数必须满足的要求:

必须是一致的,同样的输入其输出要一致。

将不同输入映射到不同数字。

1. 散列表

也被称为散列映射、映射、字典和关联数组 。

数组和链表都被直接映射到内存,但散列表更复杂,它使用散列函数来确定元素的存储位置。

Python 提供的散列表实现为字典,你可使用函数 来创建散列表。

散列表由键和值组成。

在上面的散列表 book 中,键为商品名,值为商品价格,散列表将键映射到值。

2. 应用案例

查找手机中的电话簿中某个朋友的电话号码

将网址映射到 IP 地址

投票站,确认是否投过票,避免重复投票

散列表用作缓存

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

还可用作 Hash 加密算法,如 md5。

散列表适用于:

模拟映射关系;

防止重复;

缓存/记住数据,以免服务器再通过处理来生成它们。

其应用有:

缓存、保护数据、查找重复记录、错误更正、验证文件或消息的完整性、数字签名等。

3. 冲突

给两个键分配相同的位置,即不同输入被映射到了相同位置。

如果两个键映射到同一个位置,就在这个位置存储一个链表。

经验教训:

散列函数很重要,理想情况是,散列函数将建均匀映射到散列表的不同位置;

如果散列表存储的链表很长,散列表的速度将急剧下降。然而,如果使用的散列函数很好,这些链表就不会很长 。

4. 性能

将散列表同数组和链表比较一下:

因此,在使用散列表时,避开最糟情况至关重要。为此,需要避免冲突。而要避免冲突,需要有:

较低的填装因子(散列表包含的元素数/位置总数);

良好的散列函数。

5. 小结

可以结合散列函数和数组来创建散列表。

冲突很糟糕,应使用可以最大限度减少冲突的散列函数。

散列表的查找、插入和删除速度都非常快。

散列表适合用于模拟映射关系。

一旦填装因子超过0.7,就该调整散列表的长度。

散列表可用于缓存数据(例如,在Web服务器上)。

散列表非常适合用于防止重复。

END

一个好奇的探索者,

生命不息,折腾不止,Just do it!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180602G16QSG00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券