您的基本前提是错误的：彩虹表不仅仅是每个可能的哈希查找的压缩列表，您仍然需要即时进行一些哈希。相反，它是一种利用散列的性质来避免首先存储查找的方法，并最大限度地减少重新计算所需的数量。

维基百科有相当详细的解释，这里有一个很好的答案，但基本的想法是你创建一个这样的表：

1. 从特定的密码猜测开始
2. 哈希它
3. 将散列值作为下一个密码猜测（在应用一些可重现的变换之后）
4. 散列
5. 重复步骤 3 和 4 一定次数
6. 仅存储原始猜测和最终哈希。正是这一点使得彩虹表比完整的查找表更小。

从您存储的值中，您可以取回在步骤 3 中生成的所有猜测。从某种意义上说，每对 { first guess, last hash } “压缩”了整个生成的猜测链。

但诀窍是您不需要尝试所有链来反转哈希，因为如果您使用您正在攻击的哈希并从第 2 步开始，您最终将获得您存储的最终哈希之一（在步骤 6）。一旦你发现了这一点，你可以通过从第 1 步（存储的密码猜测）开始并生成所有中间猜测来重新创建（“解压缩”，如果你喜欢的话）那个链。

这与压缩之间的一个重要区别是，您可以通过使链更长的方式使存储的表尽可能小 - 您只需花费更长的时间重新生成哈希来选择一个链，并重新创建选择链。您可以拥有一百万个长度为 10 或 10 个长度为 100 万的链，将存储与 CPU 时间进行交易。

当然可以使用您喜欢的任何算法压缩结果数据。其中一些需要在搜索之前解压缩整个表，另一些可能会排列数据以便它仍然可以搜索但占用更少的空间。但是也可以将整个彩虹表存储为快速 SSD 上的排序列表，并且您仍然可以节省完整哈希表的空间，因为您只存储每个链的开始和结束，而不是每个可能的哈希。

不可以。压缩不像传统的 RLE 或 LZMA 风格的压缩那样工作。

彩虹表本质上是一个查找表，它允许您在给定哈希值的情况下查找字符串。它们的设计目的是在跨数十亿个条目的索引中查找哈希值时非常高效，同时最大限度地减少磁盘空间。

现在，假设您正在为大量字符串构建一个表。其中一些字符串的哈希值以相同的字节开头 - 例如，“StackExchange”、“ILikeWaffles9”、“ILikeWaffles13507”和“Decompression242”在使用 MD5 进行哈希处理时都以 0xF2 开头。您可以构建一个树状结构，使数据看起来像这样，而不是完全存储所有三个哈希：

• f2
  • 173dcd3c1a83febadc8ed1759c3ffc = "ILikeWaffles13507"
  • 17f4a64e4036025c07b24a96ec787a = "解压242"
  • 50514201b94be52c1ea16cd688384e =“ILikeWaffles9”
  • 5cb1c6953bb0c62c639f3d7a242ec4 =“堆栈交换”

请注意，哈希是按数字顺序排序的。

事实上，由于前两个字符串也共享相同的第二个字节（0x17），因此它们也可以链接起来：

• f2
  • 17
    • 3dcd3c1a83febadc8ed1759c3ffc = "ILikeWaffles13507"
    • f4a64e4036025c07b24a96ec787a = "解压242"
  • 50514201b94be52c1ea16cd688384e =“ILikeWaffles9”
  • 5cb1c6953bb0c62c639f3d7a242ec4 =“堆栈交换”

这也使您可以非常快速地执行查找 - 不必搜索整个表，您只需遍历树，然后搜索较小的哈希列表。由于哈希已排序，您可以执行二分查找，这也具有非常好的性能。

例如，如果我有 hash f217f4a64e4036025c07b24a96ec787a，我会查找第一个树节点f2，然后查看是否有第二个字节的子节点17。有，所以我继续往下。我检查是否有f4. 没有，所以我现在搜索f2 -> 17节点内的列表。我知道这f4可能会接近该列表的末尾，所以我从那里开始。我发现哈希与我正在搜索的哈希匹配，所以我现在知道明文是“Decompression242”。

当您拥有数百万或数十亿个哈希时，它也非常节省空间，因为您不会复制与其他明文共享的部分哈希。

编辑：对不起，我应该指出这并不是彩虹表的工作方式。这只是压缩在这方面如何工作的一个例子，不需要为每个明文实际保存一个完整的散列。我不是故意暗示其他的。IMSoP 的回答更好地描述了实际的工作原理。

要记住的关键是彩虹表仅在您想要对该哈希类型进行多次哈希搜索时才有用。您可以提前为特定的字符串列表或字符列表生成彩虹表，只需一次，然后您可以根据需要多次使用该生成的数据集。这是提前做大量工作的权衡，以便您以后的搜索非常快。

另一个关键是任何包含盐的散列系统都会自动使彩虹表无用，因为每个密码和盐组合应该（理想情况下）是唯一的并且足够长，以至于为每个可能的密码和散列组合构建彩虹表是不切实际的。