《图解算法》第5章 散列表

第5章 散列表

散列函数

散列函数：你给它什么数据，它都还你一个数字。散列函数将输入映射到数字

• 散列函数必须满足一些要求

1. 它必须是一致的。例如，假设你输入apple时得到的是3，那么每次输入apple时，得到的都必须为3
2. 它应将不同的输入映射到不同的数字

• 结合使用散列函数和数组创建了一种被称为散列表（hash table）的数据结构。它使用散列函数来确定元素的存储位置
• 在你将学习的复杂数据结构中，散列表可能是最有用的，也被称为散列映射、映射、字典和关联数组。散列表的速度很快！

应用案例

将散列表用于查找

手机都内置了方便的电话簿，其中每个姓名都有对应的电话号码

你在访问像http://adit.io这样的网站时，计算机必须将adit.io转换为IP地址

防止重复

使用散列表可以快速判断一个人是否投过票，速度非常快

将散列表用作缓存

如果你在网站工作，可能听说过进行缓存是一种不错的做法

小结

• 散列表适合用于

1. 模拟映射关系
2. 防止重复
3. 缓存数据

冲突

冲突：给两个键分配的位置相同。冲突很糟糕，必须要避免。处理冲突的方式很多，最简单办法如下：如果两个键映射了同一个位置，就在这个位置存储一个链表

• 这里的经验教训有两个

1. 散列函数很重要。最理想的情况是，散列函数将键均匀地映射到散列表的不同位置
2. 如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很好，这些链表就不会很长！

性能

在平均情况下，散列表执行各种操作的时间都为O（1）。O（1）被称为常量时间。你以前没有见过常量时间，它并不意味着马上，而是说不管散列表多大，所需的时间都相同

• 这意味着无论散列表包含一个元素还是10亿个元素，从其中获取数据所需的时间都相同
• 我们将散列表同数组和链表比较一下

• 在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但在最糟糕情况下，散列表的各种操作都很慢。因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有

1. 较低的填装因子
2. 良好的散列函数

填装因子

散列表的填装因子很容易计算

例如，下述散列表的填装因子为2/5，即0.4

• 一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度（resizing）。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度
• 平均而言，即便考虑到调整长度所需的时间，散列表操作所需的时间也为O（1）

良好的散列函数

• 良好的散列函数让数组中的值 呈均匀分布

可研究一下SHA函数。你可将它用作散列函数