长度为76个字符的字符串的唯一哈希函数

Question

这是我的问题（我在用C语言编程）：

我有一些包含DNA序列的巨大文本文件（每个文件大约有6500万行，大小约为4-5GB）。这些文件中有许多重复项（还不知道有多少，但应该有很多百万个），我想返回一个仅包含独特值的输出文件。每个字符串都有一个关联的质量值，因此，例如，如果我有5个相同的字符串具有不同的质量值，我将保留最好的一个并丢弃其他4个。

尽可能减少内存需求和提高速度效率至关重要。 我的想法是使用哈希函数创建JudyHS数组，以将String DNA序列（长度为76个字符，并具有7个可能的字符）转换为整数，以减少内存使用（在许多百万个条目上，4或8个字节而不是76个字节应该是相当大的成就）。这样，我可以使用整数作为索引，并仅存储该索引的最佳质量值。问题是我找不到一个哈希函数，可以唯一地定义这么长的字符串并产生可以存储在整数甚至long long中的值！

我对哈希函数的第一个想法是类似于Java中默认字符串哈希函数的东西：s [0] * 31 ^（n-1）+ s [1] * 31 ^（n-2）+ ... + s [n-1]，但我可能会获得一个最大值为8.52 * 10 ^ 59..太大了。 那么将其存储在double中是否会使计算变得更慢？ 请注意，我想找到一种唯一定义字符串的方法，避免冲突（或者至少它们应该极其罕见，因为每次冲突我都必须访问磁盘，这是相当昂贵的操作...）。

- Alex

---

不是回答你的问题，而是希望解决你的问题：使用前缀树作为数据结构来紧凑地存储你的数据是否合适？ - Robᵩ

谢谢你的回答，但据我所理解，这几乎就是Judy数组，而且我也读到过它们更省空间的说法，所以我想尝试一下。 - Alex

Answer 1

您有7^76种可能的DNA序列，想将它们映射到2^32个哈希值而不发生冲突？这是不可能的。

您至少需要log2(7^76) = 214比特，大约27字节才能实现，否则会发生冲突。

如果您可以接受一些冲突，我建议使用CRC32或md5，而不是再次发明新轮子。

- Gunther Piez

---

有没有任何一种算法可以让我在这214位中编写那7^76种可能的值？ - Alex

@Alex：如果没有特殊的长整数算法，我会使用7^11组来编码，这可以在少于32位的情况下完成，并使用其中的7个32位整数。假设您序列中的值在0..6范围内：对于每组11个值，计算 (((v0*7 + v1)*7 + v2)*7 +v3)*7 ... + v10。这将小于1977326743并适合32位整数。为7个组计算此值，将最后一组中的v10设置为零。 - Gunther Piez

但我更愿意使用一个简单的哈希函数和足够长的密钥。正如Thomas所写，仅使用64位哈希将使碰撞变得非常不可能。请查看http://en.wikipedia.org/wiki/Birthday_problem：在您的情况下，表中发生碰撞的概率小于1/1000。 - Gunther Piez

碰撞问题的难点在于有可能丢弃一些不应该被丢弃的值，而为了效率起见，我不能丢弃任何一个字符串。我想我会实现你提出的7个组的想法，并添加使用Thomas的更高效（但略微不安全）建议的选项。谢谢你们两个！ - Alex

请注意，发生冲突的概率不是每次访问字符串就是千分之一，而是在整个6500万条目的表中。或者换句话说：如果您有1000个每个5 GByte的表，总共5 TByte的数据，很可能只有一个表会发生冲突，其他999个将不会发生冲突。 - Gunther Piez

Answer 2

获取一个针对 N 个元素无冲突哈希函数的“简单”方法是使用一个好的混合函数（比如，加密哈希函数），并截断大小，使得哈希结果生活在至少为 N² 的空间中。在这里，您有 6500 万行 - 这适合于 26 位（2²⁶ 接近 6500 万），因此 52 位“应该足够了”。

您可以尝试使用快速的加密哈希函数，即使是“破解”的哈希函数，因为这不是一个安全相关的问题。MD4、MD5、SHA-1... 然后将结果截断到第一个（或最后一个）64位，将其存储在 64 位整数类型中。很可能您不会在 6500 万行中获得 任何 冲突；如果您得到一些冲突，它们将非常罕见。

对于哈希函数的优化 C 实现，请查看 sphlib。使用提供的 sph_dec64le() 函数将一个 8 位序列“解码”为一个 64 位无符号整数值。

- Thomas Pornin

---

问题在于每次发生碰撞时，我需要区分是由重复引起的（因此丢弃它），还是由不同的值引起的（并保存它），而没有原始字符串存储在哈希表中。如果有某种算法可以让我做到这一点（但我无法想象如何实现），那么碰撞数量将几乎无关紧要。 - Alex