java - Java 中多重集的高效哈希码

Question

我已经定义了一个 java.util.Collection 的子接口(interface)，它实际上是一个多重集(又名包)。它可能不包含 null 元素，尽管这对我的问题并不重要。接口(interface)定义的 equals 契约如您所料:

• obj instanceof MyInterface
• obj 包含与 this 相同的元素(通过 equals)
• obj 包含每个元素相同数量的重复项
• 忽略元素的顺序

现在我想编写我的hashCode 方法。我最初的想法是:

int hashCode = 1;
for( Object o : this ) {
    hashCode += o.hashCode();
}

但是，我注意到 com.google.common.collect.Multiset(来自 Guava)定义哈希码如下:

int hashCode = 0;
for( Object o : elementSet() ) {
    hashCode += ((o == null) ? 0 : o.hashCode()) ^ count(o);
}

让我感到奇怪的是，一个空的 Multiset 会有哈希码 0，但更重要的是，我不明白 ^ count(o) 的好处，而不是简单地将每个的哈希码相加复制。也许是关于不要多次计算相同的哈希码，但为什么不 * count(o) 呢？

我的问题:什么是有效的哈希码计算？在我的例子中，不能保证元素的计数很便宜。

Answer 1

更新

Let's say, for example, in the case where we'd have an array that we want to treat as a multiset.

因此您必须在所有条目出现时对其进行处理，您不能使用 count，并且不能假定条目以已知顺序出现。

我会考虑的一般功能是

int hashCode() {
    int x = INITIAL_VALUE;
    for (Object o : this) {
        x = f(x, o==null ? NULL_HASH : g(o.hashCode()));
    }
    return h(x);
}

一些观察:

• 正如其他答案中所述，INITIAL_VALUE 并不重要。
• 我不会选择 NULL_HASH=0，因为这会忽略空值。
• 函数 g 可用于您希望成员的哈希值在一个小范围内的情况(这可能发生在它们是例如单个字符的情况下)。
• 函数 h 可用于改进结果，这不是很重要，因为这已经发生了，例如在 HashMap.hash(int) 中。
• 函数 f 是最重要的一个，不幸的是，它非常有限，因为它显然必须同时具有关联性和交换性。
• 函数 f 的两个参数都应该是双射的，否则会产生不必要的冲突。

在任何情况下我都不会推荐 f(x, y) = x^y 因为它会使一个元素的两次出现被抵消。使用加法更好。有点像

f(x, y) = x + (2*A*x + 1) * y

其中 A 是满足上述所有条件的常量。这可能是值得的。对于 A=0 它会退化为加法，使用偶数 A 并不好，因为它会将 x*y 的位移出。使用 A=1 很好，表达式 2*x+1 可以在 x86 架构上使用一条指令计算。如果成员的哈希值分布不均，使用更大的奇数 A 可能会更好。

如果您想要一个非平凡的hashCode()，您应该测试它是否能正常工作。您应该衡量程序的性能，也许您会发现简单的加法就足够了。否则，我会为 NULL_HASH=1、g=h=identity 和 A=1。

我的旧答案

可能是出于效率考虑。对于某些实现，调用 count 可能代价高昂，但可以使用 entrySet 代替。但它可能会更昂贵，我不能说。

我为 Guava 的 hashCode 和 Rinke 以及我自己的建议做了一个简单的碰撞基准测试:

enum HashCodeMethod {
    GUAVA {
        @Override
        public int hashCode(Multiset<?> multiset) {
            return multiset.hashCode();
        }
    },
    RINKE {
        @Override
        public int hashCode(Multiset<?> multiset) {
            int result = 0;
            for (final Object o : multiset.elementSet()) {
                result += (o==null ? 0 : o.hashCode()) * multiset.count(o);
            }
            return result;
        }
    },
    MAAARTIN {
        @Override
        public int hashCode(Multiset<?> multiset) {
            int result = 0;
            for (final Multiset.Entry<?> e : multiset.entrySet()) {
                result += (e.getElement()==null ? 0 : e.getElement().hashCode()) * (2*e.getCount()+123);
            }
            return result;
        }
    }
    ;
    public abstract int hashCode(Multiset<?> multiset);
}

碰撞计数代码如下:

private void countCollisions() throws Exception {
    final String letters1 = "abcdefgh";
    final String letters2 = "ABCDEFGH";
    final int total = letters1.length() * letters2.length();
    for (final HashCodeMethod hcm : HashCodeMethod.values()) {
        final Multiset<Integer> histogram = HashMultiset.create();
        for (final String s1 : Splitter.fixedLength(1).split(letters1)) {
            for (final String s2 : Splitter.fixedLength(1).split(letters2)) {
                histogram.add(hcm.hashCode(ImmutableMultiset.of(s1, s2, s2)));
            }
        }
        System.out.println("Collisions " + hcm + ": " + (total-histogram.elementSet().size()));
    }
}

打印

Collisions GUAVA: 45
Collisions RINKE: 42
Collisions MAAARTIN: 0

所以在这个简单的例子中，Guava 的 hashCode 表现得非常糟糕(63 次冲突中有 45 次冲突)。但是，我并不是说我的例子与现实生活有很大的相关性。