哈希表和彩虹表都存储预先计算的哈希值。与哈希表相比，彩虹表是计算能力与存储的权衡。使用它们是因为哈希表可以变得非常大，尤其是随着破解硬件的吞吐量提高。您可以暴力破解更多组合，但现在您需要存储更多。

我们在谈论多少空间？有数以千万计的已知密码的常见密码列表（取自以前的黑客攻击），这通常是破解者开始的地方。这可以通过这些弱密码的数亿排列来补充（如果有人使用密码 1111，其他人可能使用密码 2222）。最后，为了更好地衡量，可以通过对所有可能的密码组合进行详尽搜索来填补空白，直至达到一定长度。取 10 亿个密码，平均长度为 8 个字符，散列为 32 字节。那就是 40GB 的存储空间来存储哈希表。

彩虹表是一种使用更少空间存储相同信息的方法。尽管在计算中没有免费的午餐，但您总是可以用存储来换取计算能力，这就是您正在做的事情。要构建彩虹表，首先要构建传统的哈希表。从这些散列值开始，使用交替散列和归约函数构建散列链。归约函数将散列映射回列表中的不同密码。链的长度决定了使用了多少折衷（更长 = 节省更多空间，但执行搜索需要更多工作）。

只有链的开始和结束被保存，其余的被丢弃，因此决赛桌要小得多。定位匹配现在需要多次查找，这意味着它需要比哈希表更长的时间。

• 哈希表和彩虹表都用于保存预计算攻击的结果。
• 彩虹表中的查找速度较慢*，但存储给定数量密码的预先计算结果所需的空间更少。
• 在哈希表中查找更快*，但需要更多空间来存储给定数量密码的预先计算结果。
• 通过对每条记录使用伪随机盐，哈希表和彩虹表同样完全失败。

*这假设硬件响应时间相等，但情况可能并非如此（即彩虹表可以放入主存储器，但哈希表需要从较慢的磁盘读取，因为它太大而无法放入主存储器）。