我正在寻找一个散列函数,可以散列非重复整数列表,而忽略他们的顺序。
示例
我要那两份名单
l1 = [0, 1, 3, 7]
l2 = [7, 3, 1, 0]
具有相同的哈希值。
背景
我有一个算法可以在图中找到一系列顶点。在无向图中,该算法会以不同的顺序多次找到某些列表。以我目前对该算法的理解,过滤掉重复项比重新发明该算法更容易。出于性能原因,我认为对找到的顶点列表进行散列比比较整个列表更容易。
可能的答案
现在我明白了
XOR
或简单的和可能是答案。
不幸的是,在我看来,两者都提供了太多的潜在哈希冲突。
- 效率不高的工作方法是对列表排序,然后使用这个排序后的列表与新列表(也是排序后的)进行比较。
其他想法
既然如此
- 列表只包含整数。
- 这些整数就是顶点索引,图可以有数十亿个顶点。
- 列表中的整数是不重复的,它们的顺序无关紧要。
- 这些列表可以包含2到100个条目(在某些情况下超过1000个条目)。
- 不需要加密安全的随机性。
我觉得应该有一个相对容易和直截了当的答案,只是我还没有找到。
2条答案
按热度按时间cvxl0en21#
使用乘积、和和
^
的组合。它们都是具有 unsigned 数学的交换式(顺序无关)。提示:
hash_table_size
应为prime,以便有效地使用所有pre_hash
位。如果
array_element_count
为高,我会考虑p *= shift_right_until_odd(l[i])
,否则p
将经常变为0。6psbrbz92#
我认为你必须发明一个来避免缓慢的排序选项。除了XOR和算术加法,还有位旋转和位掩码可以使用。如果你需要高抗冲突性,你可以只合并多个哈希函数。例如,假设d_i和算术是模块化的,比如uint32_t,
然后取H1H2H3作为12字节哈希。