10

我想散列一组整数，使整数的顺序对计算的散列值没有影响。即H([32224,12232,564423]) == H([564423,32224,12232])。

唯一集合的数量将在几百万的范围内。速度非常重要，但我需要知道所选方法的碰撞上限。

维基百科有一个关于散列向量的好部分，但我不理解它背后的数学，无法自信地在代码中实现它们。如果有人可以解释一些代码所涉及的数学，我将不胜感激。理想情况下，我希望最终散列为 32 位。如果它有任何用处 - 我将在 Java 中实现它。

更新：由于性能原因（在很多这样的集合上操作），我特别希望避免对集合中的整数进行排序。

4

5 回答 5

7

一种简单的方法是将单个整数的哈希值异或或相加。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<Integer>.hashCode使用 add）要做的。如果您的整数已经装箱，或者您可以处理装箱，这是一个内置的解决方案。

于 2013-08-02T16:22:23.293 回答
2

您可以将所有整数放入 Java HashSet 并使用其 hashCode。

另一方面，java.util.Set 确实在文档中指定了以下内容：

返回此集合的哈希码值。集合的哈希码定义为集合中元素的哈希码之和，其中空元素的哈希码定义为零。这确保了 s1.equals(s2) 意味着任何两个集合 s1 和 s2 的 s1.hashCode()==s2.hashCode()，这是 Object.hashCode() 的一般合同所要求的。

然后是 Integer.hashCode()

此对象的哈希码值，等于此 Integer 对象表示的原始 int 值。

i1, i2, ... i_n因此Java 标准库中整数集的 hashCode是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，您需要能够证明 2 个集合确实相等，因此无论如何最简单的证明方法是对元素进行排序。当然，如果集合的数量大大少于数百万，那么碰撞也不会那么多。

于 2013-08-02T16:15:05.667 回答
2

我更喜欢求和而不是异或，因为 1) sum 在Set's hashCode() 实现中使用，2) sum 作为有效 Java 中推荐的数组散列方法 3) 它不太容易发生冲突。我建议你看看openjdk的AbstractSet实现：http ://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/AbstractSet.java?av=f

120    public int hashCode() {
121        int h = 0;
122        Iterator<E> i = iterator();
123        while (i.hasNext()) {
124            E obj = i.next();
125            if (obj != null)
126                h += obj.hashCode();
127        }
128        return h;
129    }

我还建议制作 h long，然后返回(int) ((h & 0xffffffffL) & h >>> 32))

于 2013-08-02T17:12:56.207 回答
2

假设您需要速度而不需要*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

通过执行以下操作，这可以推广到不仅仅是ints：

/**
 * 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程序将不得不使用数组 ofInteger而不是原语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;
            ...
于 2013-08-02T16:39:07.693 回答
0

这绝不是微不足道的编程，但您可以从 DES 算法的 S-box 中获得灵感：通过这种方式，您可以实现一个很好的分散函数，将相似的整数映射到非常不同的整数。然后，对这些不同的整数进行异或运算不应再因碰撞而造成威胁。

于 2013-08-02T17:16:41.290 回答