我面临着反转 4 个任意字节的 md5 哈希的任务。也就是说，换句话说，我需要从 1 个方法编写服务 - 该方法在输入处接收 16 个字节的散列并在输出处返回 4 个字节。
因为，据我所知，单独反转散列是不可行的，所以我决定另辟蹊径，为所有可能的值生成散列。我已经隔离了一个实体，我们称之为它запись，它由 16 个字节的哈希（我们称之为ключ）和 4 个字节的值组成。由于值是4字节~4mld，那么我得到4mld记录，每20字节大小为80GB数据。
作为第一个近似值，我生成了 80 个 gig，分为排序的段（每个段是一个单独的文件），并根据合并排序原则实现文件的合并。因此，最后，我将得到一个 80 gig 的大文件，其中将有 4 条按 key 排序的 mld 记录。我计划为这么大的文件创建第二个文件 - 一个可以轻松放入 RAM 的索引文件。之后，通过键搜索记录看起来就像在大文件上进行二分搜索，需要一点索引文件的帮助。搜索时间通常应该是对数的，限制为最多 32 跳。
该解决方案的优点：
- 易于部署。我刚刚部署了服务，等待初始化，一切正常。
缺点：
- 生成文件需要很长时间。时间以小时为单位。
- 生成的数据占用大量空间 - 80 gig
基于这些缺点，我提出了一些想法：
首先，当然是将数据存储在数据库中。它们立即被索引并在那里压缩。我已经尝试过 MongoDB 和 SQL Server，但是两个插入都很慢，以至于我厌倦了等待，而且它们显然比生成文件要慢。也就是说，我不想为了 1 服务而设置数据库服务，事实证明这对我没有多大帮助。
第二个是试图弄清楚如何最好地压缩数据。老实说，哈希压缩在我看来并不是什么基本的东西，它也无法压缩值，因为在那里使用了完整的值集。有一个想法是将一个大文件拆分为类似 trie 的文件 - 然后每个 trie 级别将为我节省大约 4 GB + 省略值中无关紧要的零 \u200b\u200b（但这会使搜索变得非常复杂）
在我的情况下选择最具体的问题对我来说是相当困难的，但我会尝试：是否有更普遍接受的方法来解决这样的问题？我有一种强烈的感觉，我做错了什么。
UPD所以，让我总结一下目前的结果。
已经尝试了几种方法。
1. 我的原始版本是将所有 16 字节的哈希值连同初始 ID 一起生成到一个文件中，然后在文件中查找哈希值。
生成时间：大约3-4小时。搜索速度：未测试。内存 - 80GB
2. 第二种方法是即使前 4 个字节取自 16 字节散列，也很少有冲突。因此，可以生成一个大 ID 文件（按哈希排序）+一个小索引文件。搜索看起来像这样：我们得到传入的哈希，从中取出前 3 个字节，在索引文件中的这个地址（也可以加载到内存中）是大文件中的初始偏移量。使用这个偏移量，我们读取了 400 个 ID——其中一个就是我们正在寻找的那个。我们统计 400 个哈希，找到需要的 id，返回结果。
生成时间：大约 2 小时（还没有做任何优化）。索引文件 - 70mb，ID 文件 - 16gb。搜索速度：大约每秒 75-100 个请求。
3. 第三种方法是生成散列链。该方法的本质是哈希链只能由初始值和最终值表示。对于我的任务，它看起来像这样：
我们取一个 4 字节的 id，从中生成一个散列H（我们取前 4 个字节），我们得到类似id->H. 散列是 4 个字节，这意味着某处有这样的id，所以我可以从散列中获取散列并构建一个像 id->H1->H2->Hn. 只有链的开头和结尾可以写入文件。开始是需要恢复链，结束是通过哈希搜索一个值。
搜索本身看起来像这样：在输入处我们有一个 hash h。我们正在寻找一个有结束的链h- 如果我们找到它，然后我们恢复链，它包含所需的id. 如果没有这样的链，那么我们从我们的 hash 中获取一个 hash h1，并寻找一个带有 end 的链h1。所以我们重复，直到有一条链。
该方法有几个优点 - 似乎您可以将数据表示为一组长链（仅在内存中保留开头和结尾）。第一个问题在于“长”这个词。我将进一步解释。
所以缺点：
- 显然，如果一条链遇到
id已经在另一个链中的链，那么这些链将开始复制信息。
它看起来像这样：
id1->H1->H2->H3->H4
id2->H5->H1->H2->H3
如您所见，如果您保持链的长度不变（这将增加文件生成时间），则会出现重复信息。
- 为了消除重复，我在内存中分配了 2 ^ 32 位 (~ 500 mb)，并标记了已处理的 ID。因此，1 个 ID 仅在 1 个链中。然后链条长度的问题浮出水面。底线是，为了使链真正长且有用，其中所有生成的哈希值必须等于那些尚未处理的 ID。当您开始计算这些链条时（我数了链条，直到遇到一个已经处理过的链条
id），它们的平均长度为 200 节。但这个数字正在迅速减少。
举个例子：假设10%所有的ID都已经处理完毕，正在生成一条新的链。假设散列函数具有均匀分布，那么第一个散列是id尚未处理的散列的可能性为0,9. 第二个哈希是 -0,9*0,9=0,81的可能性，依此类推，以及链中至少有10应用元素的可能性0.35。这是处理的时候10%。处理后，链80%中至少有2元素（不包括第一个元素id）的机会是0,64. 处理时99%——人们可能会说，长链的机会不存在，典型的链将由初始链id及其散列组成。这也是我学到的。
总共生成时间大约一个小时，文件大小为16GB。我什至没有尝试测试搜索速度。
4. 第四种方法是彩虹表（感谢@AlexanderPetrov 的提示）。
彩虹表本质上是哈希链的一种变体。与链的不同之处在于，这里使用散列函数与使用不同的函数（归约函数）交替使用。我举个例子：
id -> H1=H(id) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
该示例显示散列函数与不同的归约函数交错。这种方法的优点是，即使某个值在 2 条链中相同，也只有从链的开头开始值相同时才会出现重复，例如
id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
id2 -> H6=H(id2) -> H7=R1(H6) -> H3=H(H7) -> H4=R2(H3) -> H5=H(H4)
但是如果这个值在链的不同位置，那么它会给出不同的结果，因为它会被不同的归约函数处理
id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
id2 -> H6=H(id2) -> H7=R1(H6) -> H2=H(H7) -> H8=R2(H2) -> H9=H(H8)
一切似乎都很好，您可以生成任意长度的链。所以我想当我开始生成长度为 3000 个元素的链时。我很快数完了30%所有的值。我数了数可以忍受的时间50%。但是这里的规则与我在前面的例子中描述的概率论相同。想象一下，我计算95%了所有的 ID。因此，一个新的元素链3000将包含150新元素和2850那些已经计数的元素。因此，计算链的速度急剧下降，因此在每个新链中，95%元素都被认为是空的。我等了大约30 个小时，无法忍受，停止了这种疯狂 - 大约98%所有 Id 占用了大约240兆字节。但我对准确性并不满意98%，当然我需要100%。
由于引入了约简功能，id哈希搜索与之前版本的搜索略有不同。如果在之前的版本中我只是从一个哈希中取出一个哈希，那么在这里，我们需要根据传入的哈希来构建一个新的链。示例：假设有一条链
id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
我们在入口处得到了一个哈希H1。我们没有以 结尾的链H1，因此我们考虑：
H(H1) - нет совпадений
R2(H(H1)) - нет совпадений
H(R2(H(H1))) - нет совпадений
R1(H(R2(H(H1)))) - на этом этапе результат выражения будет равен H5 элементу цепочки.
找到链后，我们将其还原并找到所需的id. 从实践中 - 我通过哈希等待至少 1 个 id 大约 10 分钟，我没有等待。但我怀疑这与算法无关，而我只是一个杂工。我完全承认，如果您需要使用某种错误来反转哈希，那么原则上该选项是有效的。
总的来说，生成时间很长，30小时98%，98%被认为是5-6小时，文件大小为240mb。搜索速度不适用。
作为目前的结果，到目前为止，我已经确定了选项 2) - 16 gig 文件 + 索引。我怀疑这个选项将是最快的。但其他选项也一样，我不会注销。
UPD 2 发布了我的磨难的来源。第二种方法完全实现，整个生成耗时 25 分钟，一次搜索 1 个 key - 大约每秒 180 个请求，搜索来自真实程序的一组传入真实数据 - 每秒约 1000 个请求（检查 75千可用哈希）。
谢谢大家的帮助！
让我们估计一个可能的索引的最小大小。使用任何索引方法，键都应该占用我们 4 个字节的 value。要自己存储值，需要 16 GB。考虑到索引中的值是按key的顺序排列的，我们可以将它们视为一组充分利用所有可能位的随机数据。没有算法能够无损压缩此类数据。
根本不需要额外的索引！！！我们只需要一个 16 GB 的字典，它本身将包含所需的值，并按照它们的 MD5 哈希值排序。搜索时，根据散列的前 4 个字节，我们估计所需值应位于的文件的大致区域。在建立字典并收集统计数据后，我们设法确定可以读取 128Kb 大小的块，并且其中肯定会有所需的值。文件中块的准确坐标如下：
读完这个块后，我们涌向它的中间，根据找到的值计算 MD5并将其与我们要查找的值进行比较。然后，我们通过二分查找，而不是存储的数据，而是通过动态计算的和 MD5，在字典的区域中向一个方向或另一个方向跳跃。我们将在最多 20 次“跳跃”中达到所需的值。
附录：在内存不足的情况下构建字典的算法
如果您的可用内存少于 4 GB，甚至无法立即计算 4 字节密钥的数量，那么以下是一个相当快速的解决方案：
所有处理分为两个阶段。在第一阶段，我们打开从 00 到 FF 的 256 个文件。我们计算所有可能数字的 MD5，并写入与哈希的第一个字节的数字、值本身（4 个字节）和哈希的 4 个字节相匹配的文件，从第二个开始（因为我们知道第一个来自文件）。在分配 1 兆字节的写入缓冲区时，此阶段的程序需要大约 280 MB 的 RAM。对我来说，在 C# 中实现的阶段，没有太多优化，在 1 个核心上工作大约需要 2.5 小时。一直以来，它都需要对 MD5 进行实际计算，如果不使用多个内核或 GPU，您将无法摆脱这一点。
第二阶段是分别对每个文件进行排序并合并值将它们放入最终的字典文件中。在这种情况下，我们按文件编号的顺序排列，因此数据最初按哈希的第一个字节自行排序。文件之间不需要行比较，读取文件，排序，写入输出，继续下一步。我不知道我使用的排序方法的名称是什么，但它的工作原理是这样的：我们将所有 128 MB 的文件读入内存。我们创建了一个 64 MB 的输出缓冲区、一个 64 MB 的输出密钥缓冲区、一个 16 MB 的密钥计数器字节数组、一个 64 MB 的偏移量数组，以及块中另一个当前偏移量的工作数组。该程序总共需要大约 370 MB 的内存。我们分两遍排序，首先我们计算每个 3 字节密钥的出现次数（一个密钥最多重复 11 次，因为密钥的第 4 字节与文件名中的相同）。基于此，我们通过加法计算并将每个值列表的开头写入偏移数组。接下来，我们通过输入数组进行第二次传递，同时重写值到值和键的数组中成一个单独的数组。当在每个键可能有超过 1 个值的点插入元素时，我们使用插入排序，即 我们找到一个大于给定值的值并将其和所有后续值移回。考虑到一个列表中只有 11 个值（然后每个文件大约有 20 个这样的情况，即在 1600 万个中） - 这很快。如果文件中密钥的所有 4 个字节（加上文件名中的第 5 个字节）都相同，那么现在算法重新计算 MD5 并比较完整的哈希值。对于 1600 万条记录，大约有 32,000 种此类情况。如果这个地方比较慢，可以在第一阶段保存大部分key（但是文件会变大，需要更多的内存和更多的磁盘I/O）。这一步花了我 25 分钟。同样，完全缺乏优化。
最终代码。请不要踢太多，我是第一次用 C# 编写（我可能很快需要它，这个任务作为“Hellow World”很方便），我可能不知道基本的东西。意见、建议等 （特别是：“这更容易完成”）欢迎:)
附录 2：自定义 MD5 计算
通过重做本文中计算 MD5 块的过程的 C 源代码。通过对 4 个字节的哈希计算进行严格的锐化版本。相反，按照 MD5 算法的要求，考虑了 64 字节的最小块，但在完成的块中只有 4 个初始字节发生变化。我收到以下内容。该算法的阶段 1 计算 40 亿个 MD5 和的时间已从 2 小时 40 分钟减少到 17 分钟（但对于一个 Core i7-2600 核心）。并且在引入多线程之后，应用程序开始进入磁盘速度，而阶段 1 需要 10 分钟，阶段 2 需要 12 分钟。总而言之，构建一个可供搜索的字典的总时间是 22 分钟。
如果问题的本质是减小数据文件的大小，那么最简单的选择就是根本不存储数据，只存储索引。
按照 Mike 的想法，我们取每个 hash 的前 2 个字节——并以这种形式写入文件。该文件可以以两级方式组织：在文件的开头，一个包含 65,536 个单元格的表格（每个单元格对应于前两个字节的某种组合），在每个单元格中 - 写入数据的偏移量以及该单元格中的命中数。如果我们为每个值占用 8 个字节，那么这个表总共将占用 1 MB，这是相当多的。
原则上，如果你在服务启动时生成一个文件，那么这部分可以保存在内存中，而不需要写入磁盘。顺便说一句，要构建这样的索引，您可以使用不需要额外内存的两遍算法：首先，我们查找所有哈希并计算每个单元格中的命中数，然后找到部分和 - 这些将是抵消。那么，在第二次通过时，我们再次计算哈希值并填充磁盘上的文件。
文件的第二部分将包含导致该单元格的所有数据散列。它们总共将是 16 GB。
好吧，通过搜索，一切都很简单：我们获取哈希的前两个字节，并使用它们来确定可能的候选者列表。我们用通常的线性搜索遍历这个列表，重新计算所有的哈希值来寻找精确匹配。
顺便说一句，在 64 位系统上，您可以使用内存映射文件来加快工作速度。但是在 32 位系统上，这种方法的优势就丧失了：您将无法将整个文件映射到内存中。
选项之一：
我们将文件存储在具有以下结构的目录中：
(первые 3 символа hex(md5))/(следующие 2 символа hex(md5)).db因此，将有 4096 个文件夹，文件夹中有 256 个文件，总共 1048576 个节点。使用这些设置，文件系统不会变慢。该文件将包含平均 4096 个哈希值。
文件本身 - 16 字节哈希 + 4 字节的记录 - 被搜索，一个接一个地定位。在最初的生成过程中，文件只是简单地补充了记录，然后每个文件中的记录都需要进行哈希排序。
因此，将有可能在最短的时间内到达所需的文件并执行二进制搜索，打开文件并读取 20 个字节的偏移量不超过 12 次迭代。