8

我已经定义了一个java.util.Collection有效的子接口是一个多重集（又名包）。它可能不包含null元素，尽管这对我的问题并不重要。接口定义的 equals 契约如你所料：

  • obj instanceof MyInterface
  • objthis包含与(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)呢？

我的问题：什么是有效的哈希码计算？在我的情况下，一个元素的数量不能保证很便宜。

4

4 回答 4

2

如果计数很昂贵，请不要这样做。你知道它太贵了吗？您始终可以编写多个实现并使用您希望代表您的应用程序的数据来分析它们的性能。然后你会知道答案而不是猜测。

至于为什么要使用 XOR，请参阅 'Calculating Aggregate hashCodes with XOR'。

于 2011-09-16T00:25:05.107 回答
2

更新

例如，假设我们有一个想要作为多重集处理的数组。

因此，您必须在所有条目出现时对其进行处理，您不能使用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()东西，您应该测试它是否正常工作。你应该衡量你的程序的性能，也许你会发现简单的加法就足够了。否则，我会选择 for 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 次）。但是，我并不认为我的例子与现实生活有很大的相关性。

于 2011-09-16T18:23:50.330 回答
2

让我感到奇怪的是，一个空的 Multiset 的哈希码为 0

为什么？所有空集合可能都有哈希码 0。即使没有，它也必须是一个固定值（因为所有空集合都是相等的），那么 0 有什么问题呢？

什么是有效的哈希码计算？

你的效率更高（这意味着计算速度更快），在有效性方面也不算太差（这意味着产生效果很好的结果）。如果我理解正确，它会将所有元素的哈希码相加（重复元素被添加两次）。这正是常规 Set 所做的，因此如果您没有重复项，您将获得与 Set 相同的 hashCode，这可能是一个优势（如果您将空集修复为 hashCode 0，而不是 1）。

谷歌的版本有点复杂，我想是为了避免一些其他频繁的冲突。当然，它可能会导致其他一些被认为不太频繁发生的碰撞。

特别是，使用 XOR 将 hashCodes 分布在整个可用范围内，即使单个输入 hashCodes 没有（例如，对于有限范围内的 Integers 不这样做，这是一个常见的用例）。

考虑 Set [ 1, 2, 3] 的 hashCode。是 6。可能与相似的 Set 发生碰撞，例如 [6]、[4, 2]、[5, 1]。在那里投入一些 XOR 会有所帮助。如果它是必要的并且值得额外的成本是你必须做出的权衡。

于 2011-09-16T02:15:58.767 回答
1

我观察到 java.util.Map 使用或多或少相同的逻辑：java.util.Map.hashCode() 指定返回 map.entrySet().hashCode()，而 Map.Entry 指定其 hashCode() 是entry.getKey().hashCode() ^ entry.getValue().hashCode()。接受从 Multiset 到 Map 的类比，这正是您所期望的 hashCode 实现。

于 2011-09-27T22:28:13.197 回答