在Java集合中缓存散列？ [英] Caching hashes in Java collections?

问题描述

当我实现一个集合，使用哈希优化访问，我应该缓存哈希值或假设一个有效的实现 hashCode（）？

$ b另一方面，当我实现一个覆盖 hashCode（）的类，我应该假设集合（即 HashSet ）缓存散列？

这个问题只是关于性能和内存开销。我知道一个对象的哈希值不应该改变。

澄清：
一个可变对象当然必须清除缓存的值，当它被改变，而集合依赖于对象不改变。

解决方案

设计Guava的 ImmutableSet 和 ImmutableMap 类，我们选择不来缓存哈希码。这样，当且仅当您足够自己进行缓存时，您将获得更好的散列码缓存性能。如果我们自己缓存，即使在您非常关心速度和空间的情况下，我们仍会花费更多的时间和记忆！

HashMap 是这样的缓存，但它是 HashMap 的作者（Josh Bloch）强烈建议我们不遵循先例！

编辑：哦，如果你的 hashCode（）很慢，该集合只解决了一半的问题，因为 hashCode（）仍然必须调用传递给 get（）无论是什么。

When I implement a collection that uses hashes for optimizing access, should I cache the hash values or assume an efficient implementation of hashCode()?

On the other hand, when I implement a class that overrides hashCode(), should I assume that the collection (i.e. HashSet) caches the hash?

This question is only about performance vs. memory overhead. I know that the hash value of an object should not change.

Clarification: A mutable object would of course have to clear the cached value when it is changed, whereas the collection relies on objects not changing. But this is not relevant for my question.

解决方案

When designing Guava's ImmutableSet and ImmutableMap classes, we opted not to cache hash codes. This way, you'll get better performance from hash code caching when and only when you care enough to do the caching yourself. If we cached them ourselves, we'd be costing you extra time and memory even in the case that you care deeply about speed and space!

It's true that HashMap does this caching, but it was HashMap's author (Josh Bloch) who strongly suggested we not follow that precedent!

Edit: oh, also, if your hashCode() is slow, the caching by the collection only addresses half of the problem anyway, as hashCode() still must be invoked on the object passed in to get() no matter what.

这篇关于在Java集合中缓存散列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！