《算法图解》读书笔记 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！