唯一Ids序列的散列函数(UUID)

Question

我在数据库中存储消息序列，每个序列可以有高达N数量的消息。我想创建一个哈希函数，它将表示消息序列，并允许更快地检查消息序列是否存在。

每条消息都具有区分大小写的字母数字通用唯一id (UUID)。考虑以下带有ids的消息(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) ...etc...

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

​

​

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

我不想扫描表中的行，而是想创建一个散列函数，它用一个散列值表示消息序列。在表中使用散列值查找应该会更快。

我的简单散列函数是-

​

我想知道什么是存储消息序列散列的最佳散列函数，用于更快的存在检查。

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

在任何情况下，使用位操作的散列(移位、异或...)你的方法应该比乘法更快，即使在现代机器上也是如此。

Answer 2

如何使用MD5 algorithm为连接的messageUID字符串生成散列。

例如-考虑消息

M1 - a3RA0000000e0taBB M2 - a3RA00033000e0taC M3 - a3RA0787600e0taBB

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

根据this answer的说法，MD5对碰撞是健壮的。在给定的场景中，不需要安全性，因此MD5就足够了。

Answer 3

过早优化是万恶之源。从你选择的语言中内置的散列函数开始，然后对列表进行散列(M1, M2)，依此类推。然后在开始使用第三方哈希库之前对其进行分析，看看这是否是瓶颈。

我的猜测是，数据库查找将比散列计算慢，所以使用哪个散列都无关紧要。

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

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