用于唯一标识符(UUID)序列的哈希函数

Question

我正在将消息序列存储在数据库中，每个序列最多可以有N条消息。我想创建一个哈希函数，它将表示消息序列，并使其更快地检查消息序列是否存在。

每个消息都有一个区分大小写的字母数字通用唯一标识符(UUID)。考虑以下具有ID的消息(M1，M2，M3)- M1-a3RA0000000e0taBB M2-a3RA00033000e0taC M3-a3RA0787600e0taBB 消息序列可以是 Sequence-1:(M1,M2,M3) Sequence-2:(M1,M3,M2) Sequence-3:(M2,M1,M3) Sequence-4:(M1,M2) Sequence-5:(M2,M3) ...等等...

以下是存储消息序列的数据库结构示例。

给定消息序列，我们需要检查该消息序列是否存在于数据库中。例如，检查消息序列 M1 -> M2 -> M3，即使用 UID (a3RA0000000e0taBB -> a3RA00033000e0taC -> a3RA0787600e0taBB) 是否存在于数据库中。

我想创建一个哈希函数来代表消息序列的哈希值，而不是扫描表中的行。使用哈希值在表中进行查找应该更快。

我的简单哈希函数是- 我想知道存储消息序列哈希以进行更快速的存在检查的最佳哈希函数是什么。

- Anwar Shaikh

Answer 1

您不需要一个完整的加密哈希函数，只需要一个快速的哈希函数，因此建议您看一下FastHash：https://github.com/ZilongTan/Coding/tree/master/fast-hash。如果您认为32位或64位哈希值不足以避免冲突，那么可以使用更长的MurmurHash：https://en.wikipedia.org/wiki/MurmurHash（实际上，FastHash的作者也推荐这种方法）。

在维基百科上有更多算法的列表：https://en.wikipedia.org/wiki/List_of_hash_functions#Non-cryptographic_hash_functions。

无论如何，使用位运算（SHIFT、XOR等）的哈希函数应该比您的方法中的乘法更快，即使在现代计算机上也是如此。

- memo

---

他并没有要求最快的哈希函数 - 他要求的是更快的存在性检查。如果任何语言中的内置哈希函数比数据库查找慢，我会感到惊讶。 - Mohan

Answer 2

如何使用 MD5算法 为消息UID串联的字符串生成哈希值呢？

例如，考虑以下消息：

M1 - a3RA0000000e0taBB M2 - a3RA00033000e0taC M3 - a3RA0787600e0taBB

对于消息序列 M1->M2->M3，字符串将是 a3RA0000000e0taBB;a3RA00033000e0taC;a3RA0787600e0taBB，其MD5哈希值为 176B1CDE75EDFE1554888DAA863671C4。

根据 这个答案，MD5算法对抗碰撞具有强大的鲁棒性。在此给定的场景中，没有必要保证安全性，因此MD5算法可能足够。

- Anwar Shaikh

---

MD5比@memo答案中的哈希函数要慢得多，而且可能在避免碰撞方面并不比任何其他128位哈希函数更好，也可能不比您的简单哈希函数更好。 - President James K. Polk

@James 好的，我明白了。你认为“MD5比Memo答案中的哈希（Fast-Hash和MurMurHash3）要慢得多”的具体原因是什么呢？谢谢！ - Anwar Shaikh

仅仅是基于我对每个哈希函数步骤数量的理解所产生的直觉。 - President James K. Polk

Answer 3

过早优化是万恶之源。从你所选择的编程语言中内置的哈希函数开始，然后对列表(M1, M2)等进行哈希。然后进行性能分析，看看这是否是瓶颈，再考虑使用第三方哈希库。

我猜数据库查找会比哈希计算慢，所以使用哪种哈希都无所谓。

在Python中，您只需调用hash([m1, m2, m3])

在Java中，调用ArrayList上的hashCode方法。

- Mohan

---

在Python中 - 类型错误：不可哈希类型：'list' - pi314159

Answer 4

任何常规字符串哈希算法（比如，您选择的语言基础库字符串哈希）应用于消息UUID串联起来的结果即可，只要您通过该哈希选择所有消息并检查它们是否按正确顺序排列。这可能会有效，也可能不会，具体取决于通常有多少条消息在一个序列中（还要考虑最坏情况）。一般来说，无法保证无冲突哈希计算，因此您应该考虑在发生冲突时该怎么办。 现在，如果您想优化此过程以确保您的哈希是唯一的，某些情况下可能是可行的。一旦尝试插入数据就会知道是否存在冲突，因此您可以采取一些措施（例如，对序列应用盐或虚拟消息等方式修改哈希，并持续进行直到获得空位），但这将需要足够大的哈希和潜在的其他应用程序特定修改。

- vladich