在不考虑顺序的情况下对非重复整数列表进行哈希处理的最安全方法是什么？

Question

我正在寻找一个哈希函数，它可以对非重复整数列表进行哈希处理，同时忽略它们的顺序。

例子

我想要这两个列表

l1 = [0, 1, 3, 7]
l2 = [7, 3, 1, 0]

具有相同的哈希值。

背景

我有一个算法可以找到图上的顶点列表。在无向图中，算法会以不同的顺序多次查找某些列表。以我目前对算法的理解，过滤掉重复项比重新发明算法更容易。出于性能原因，我知道对找到的顶点列表进行散列比比较整个列表更容易。

可能的答案

现在，我看到了

• 一个XOR或一个简单的总和可能就是答案。
  不幸的是，正如我所见，两者都提供了太多哈希冲突的可能性。
• 效率不高的工作方法是对列表进行排序，然后使用此排序列表与新列表（也已排序）进行比较。

其他想法

鉴于

• 这些列表仅包含整数。
• 整数将是顶点索引，并且该图可以有数十亿个顶点。
• 列表中的整数是不重复的，它们的顺序并不重要。
• 该列表可以并且将包含 2 到 100 个（并且在某些情况下 > 1000 个）条目。
• 不需要加密安全的随机性。

我有这种感觉，应该有一个相对简单直接的答案，只是我还没有找到。

Answer 1

使用乘积、总和 和 的组合^。所有这些都与无符号数学是可交流的（与顺序无关）。

unsigned long long product = 1;
unsigned sum = 0;  // Maybe unsigned long long
unsigned x = 0;
for (i=0; i < array_element_count; i++) {
  product *= l[i];
  sum += l[i];
  x ^= l[i];
}
unsigned long long pre_hash = product + sum + ((unsigned long long) x << 32));
unsigned hash = pre_hash % hash_table_size;

提示：hash_table_size应该是有效使用所有位的质数。pre_hash

如果array_element_count很高，我会考虑p *= shift_right_until_odd(l[i])，否则p经常会变成0。

如果l[i] == 0 p *= l[i] 值得一些不同的东西。一个简单的缓解措施是p *= l[i] | 1，但那是凭空而来的。

散列需要时间才能实现良好的设计，以上是 OP 的候选构建块。