以顺序无关的方式散列一组整数
我希望散列一组整数，这样整数的顺序就不会对计算出来的哈希值产生影响。即H([32224,12232,564423]) == H([564423,32224,12232]).
独特集的数量将在几百万之间。速度是非常重要的，但是我需要知道与选择的方法碰撞的上限。
维基百科有一个很好的关于散列向量的章节，但我不理解它背后的数学原理，无法自信地在代码中实现它们。如果有人能解释一些代码所涉及的数学问题，我将不胜感激。理想情况下，我希望最后的散列为32位。如果它有什么用处的话--我将用Java实现它。
Update：我特别希望避免对集合中的整数进行排序，因为性能原因(在很多这样的集合上操作)。
回答 5
Stack Overflow用户
发布于 2013-08-02 16:22:23
一种简单的方法是将单个整数的散列添加到一起。xor和add是可交换的，因此满足顺序独立性。
因此：
int hc = 0;
for(int i = 0; i < n; i++) {
hc += a[i];
}
return hc;或
int hc = 0;
for(int i = 0; i < n; i++) {
hc ^= a[i];
}
return hc;因为int的散列代码无论如何都是它的值。
事实上，这正是HashSet.hashCode(使用add)所要做的。如果您的整数已经装箱，或者您可以处理装箱，这是一个内置的解决方案。
Stack Overflow用户
发布于 2013-08-02 16:15:05
您可以将所有的整数放在HashSet中并使用它的hashCode。
另一方面，java.util.Set确实在文档中指定了以下内容：
返回此集的哈希代码值。集合的哈希码被定义为集合中元素的哈希码的和，其中空元素的哈希码被定义为零。这可以确保s1.equals( s2 )意味着s1.hashCode()==s2.hashCode()用于任何两个集合( s1和s2)，这是Object.hashCode()的一般契约所要求的。
而Integer.hashCode()则是
此对象的哈希代码值，等于此Integer对象表示的基本int值。
因此，hashCode标准库中用于整数集的i1, i2, ... i_n是i1 + i2 + ... + i_n。
如果数字很小，你也可以把每个元素乘以一个适当大小的素数。Knuth使用了2654435761，这对于java int来说太大了，但是您可以使用它的2-补码-1640531527。因此，取C= -1640531527，然后您的代码是C*i1 + C*i2 + ... C*i_n。
private static final int C = -1640531527;
public static int calculateHash(int[] set) {
int code = 0;
for (int e: set) {
code += C * e;
}
return code;
}然而，这种思维存在着一个明显的缺陷。要使用hashCode，您需要能够证明两个集合确实相等，因此在任何情况下最简单的证明方法就是对元素排序。当然，如果有远少于数百万的集合，那么也不会有那么多的碰撞。
Stack Overflow用户
发布于 2013-08-02 16:39:07
假设您需要速度而不需要*Set类的开销，那么您可以编写H如下所示：
/**
* Hashes a set of integers.
*
* @param list to hash
* @return hash code
*/
public static int H(int list[]) {
// XOR all the integers together.
int hashcode = 0;
for (int val : list) {
hashcode ^= val;
}
return hashcode;
}不管顺序如何，它都是一样的，而且是相对有效的。
例如：
public static void main(String[] args) {
System.out.println(Integer.toHexString(H(new int[]{0xabcd,0x1234,0x1111})));
System.out.println(Integer.toHexString(H(new int[]{0x1234,0x1111,0xabcd})));
}显示：
a8e8
a8e8通过执行以下操作，可以将其推广到不仅仅是int：
/**
* Hashes a set of objects.
*
* @param list to hash
* @return hash code
*/
public static int H(Object list[]) {
// XOR all the hashes together.
int hashcode = 0;
for (Object val : list) {
hashcode ^= val.hashCode();
}
return hashcode;
}然后，main程序将不得不使用Integer数组而不是原始int。
添加数字应该是几乎一样快，并可能给您一个更好的分布在32位范围内。如果集合中的元素已经在范围内均匀分布，那么xor可能更好。
但是，使用这两种方法，您可以很容易地生成与整数的碰撞。例如，使用加法；
{1000, 1001, 1002}
{0, 1, 3002}这两个数组具有相同的H()。
用异或法；
{0x1010, 0x0101}
{0x1111, 0x0000}这两个都有相同的H()。
类似地，0元素也是有问题的，因为列表包含或不包含相同的散列。您可以通过在每次迭代中添加一个常量值来减轻这一点。例如：
...
hashcode += val.hashCode() + CONSTANT;
...或将元素数作为初始哈希代码：
...
// XOR all the hashes together.
int hashcode = list.length;
...https://stackoverflow.com/questions/18021643
复制相似问题
腾讯云开发者
