Java中多集的高效哈希码

Question

我已经定义了一个子接口,java.util.Collection它实际上是一个multiset(又名包).它可能不包含null元素,尽管这对我的问题并不重要.接口定义的equals合同正如您所期望的那样:

• obj instanceof MyInterface
• obj包含与this(by 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

更新

举例来说，我们有一个数组，我们想将其视为多重集。

因此，您必须在所有条目出现时对其进行处理，您不能使用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 种）。然而，我并不认为我的例子与现实生活有很大关系。