数组的顺序不敏感哈希函数

Question

我正在寻找一个哈希函数，它将为包含相同元素的无序序列产生相同的结果。

例如：

Array_1: [a, b, c]
Array_2: [b, a, c]
Array_3: [c, b, a]

哈希函数应该为每个数组返回相同的结果。

如何实现这一目标？

最流行的答案是按某种规则对元素进行排序，然后连接，然后进行哈希。

还有其他方法吗？

Answer 1

如果 a、b、c 是数字，您可以求和，然后根据总和构建哈希。你也可以乘法。但要注意零！对数字进行异或运算也是一种方法。

对于非常小的数字，您可以考虑设置由数字索引的位。这意味着构建一个长整型（64 位）作为哈希的输入仅允许 0-63 范围内的元素编号。

拥有的元素越多，发生的碰撞就越多。最后，您将m位的n 个元素（导致 2^(m*n) 范围）映射到k位的哈希值。通常 m 和 k 是常数，但 n 会变化。

请注意，通过哈希进行的任何访问都需要测试是否获得正确的元素。一般来说，哈希值不是唯一的。

否则对元素进行排序，然后按照建议进行散列

关于 CodesInChaos 的评论：

为了能够省略测试，散列的位数应远大于元素位数的总和。至少还要多说64位。一般情况下不会给出这种情况。

安全哈希/唯一 ID 的一种常见情况是 guid。这实际上意味着 128 位。文本字符的随机序列在 20-25 个字符内达到此位数。较长的文本很可能会产生冲突。这是否仍然可以接受取决于用例。