c# 在不考虑顺序的情况下,对一个不重复整数列表进行哈希运算的最安全方法是什么?

kqhtkvqz  于 2022-12-20  发布在  C#
关注(0)|答案(2)|浏览(150)

我正在寻找一个散列函数,可以散列非重复整数列表,而忽略他们的顺序。

示例

我要那两份名单

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

具有相同的哈希值。

背景

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

可能的答案

现在我明白了

  • XOR或简单的和可能是答案。

不幸的是,在我看来,两者都提供了太多的潜在哈希冲突。

  • 效率不高的工作方法是对列表排序,然后使用这个排序后的列表与新列表(也是排序后的)进行比较。

其他想法

既然如此

  • 列表只包含整数。
  • 这些整数就是顶点索引,图可以有数十亿个顶点。
  • 列表中的整数是不重复的,它们的顺序无关紧要。
  • 这些列表可以包含2到100个条目(在某些情况下超过1000个条目)。
  • 不需要加密安全的随机性。

我觉得应该有一个相对容易和直截了当的答案,只是我还没有找到。

cvxl0en2

cvxl0en21#

使用乘积、和和^的组合。它们都是具有 unsigned 数学的交换式(顺序无关)。

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应为prime,以便有效地使用所有pre_hash位。
如果array_element_count为高,我会考虑p *= shift_right_until_odd(l[i]),否则p将经常变为0。

6psbrbz9

6psbrbz92#

我认为你必须发明一个来避免缓慢的排序选项。除了XOR和算术加法,还有位旋转和位掩码可以使用。如果你需要高抗冲突性,你可以只合并多个哈希函数。例如,假设d_i和算术是模块化的,比如uint32_t,

H_1 = sum_{i = 1 to n} d_i
H_2 = xor_{i = 1 to n} d_i
H_3 = xor_{i = 1 to n} (rotl(d_i, d_i & 0x1f) + c)

然后取H1H2H3作为12字节哈希。

相关问题