我必须处理数字序列,其中序列具有以下属性:
给定一个序列,我想知道这个序列是否已经发生,那就是我想要哈希序列.例如,
[2, 3, 6, 2, 13]
和
[6, 3, 2, 13, 2]
应具有相同的哈希值.
使用的编程语言是C.
我知道我可以先对序列进行排序,然后将它们存储在trie中,这绝对是一种选择.然而,为此目的,什么是适当的哈希函数？
将所有数字与序列的长度相乘，然后对某个相当大的数字取模怎么样？下面是一些显示计算结果的 Scala 代码：
val l = List(6, 3, 2, 13, 2)
(l.reduce(_ * _) * l.length) % 10000
结果是：4680。
显然，这并不能保证如果散列匹配，则序列是唯一的。（它甚至可能不是一个很好的近似值！）但是，如果散列不匹配，则可以保证序列不相同。