我正在寻找一个哈希函数,它将为包含相同元素的无序序列产生相同的结果。
例如:
Array_1: [a, b, c]
Array_2: [b, a, c]
Array_3: [c, b, a]
散列函数应该为这些数组中的每一个返回相同的结果。
如何实现这一目标?
最流行的答案是按某种规则对元素进行排序,然后连接,然后取散列。
有没有其他方法?
最佳答案
如果 a,b,c 是数字,你可以求和然后在总和上建立一个散列。
你也可以倍增。
但要注意零!
异或数也是一种方法。
对于非常小的数字,您可以考虑设置由数字索引的位。这意味着构建一个 long(64 位)作为散列的输入只允许 0-63 范围内的元素编号。
您拥有的元素越多,您将获得的碰撞就越多。
最后你图 带有 的元素米 位(导致 2^(m*n) 范围)到具有 的哈希值k 位。
通常 m 和 k 是一个常数,但 n 是变化的。
请注意,通过哈希进行的任何访问都需要测试是否获得正确的元素。一般来说,散列不是唯一的。
否则对元素进行排序,然后按照建议进行散列
关于 CodesInChaos 的评论:
为了能够省略测试,散列的位数应该远大于元素位的总和。至少多说 64 位。一般情况下不会给出这种情况。
安全散列/唯一 id 的一种常见情况是 guid。这意味着有效的 128 位。
文本字符的随机序列在 20-25 个字符内达到此位数。
较长的文本很可能会产生冲突。这是否仍然可以接受取决于用例。
关于arrays - 数组的顺序不敏感哈希函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13847924/