是否使用哈希码来加速集合中的对象查找? [英] Is hashcode used to speed up object lookups in collections?

问题描述

IIUC它可以将相同类型的两个不同对象存储在HashSet中，即使在调用 hashCode()时两个对象返回相同的值.例如，根据此文章"Aa"和"BB"返回相同的 hashcode (2112)，但显然我可以将这两个字符串都放在 HashSet 中，并且它们都将包含在 Set 中，而不会用"Aa"覆盖"BB".

IIUC it two different objects of the same type can be stored in a HashSet even though both objects return the same value when hashCode() is called. For example according to this article "Aa" and "BB" return the same hashcode (2112), but obviously I can put both of these Strings in a HashSet and they will both be contained in the Set without "Aa" overwriting "BB".

那么， hashCode()的主要目的是更快地在Set或一般的collections中查找实例吗?这也暗示着，如果我们为 hashCode()返回一个常数，这将减慢存储此类对象的集合的性能(在

So is the primary purpose then of hashCode() to make finding an instance in a Set, or collections in general, faster? Also does this imply that if we return a constant for hashCode() that this will slow down the performance of a collections that store such objects (Within a JPA context as suggested by this linked article for example)?

推荐答案

是.任何基于存储桶的算法的基础都是要使元素均匀分布在N个存储桶中，其中 N<<|所有元素| .具有恒定的hashCode将迫使所有元素进入同一个存储桶，从而减少所有查找/包含操作仅使用基础(每个存储桶)结构(可能是List或类似结构)运行.

Yes. The basics of any bucket-based algorithm is that you want to have your elements spread evenly across N buckets, where N << |all elements|. Having a constant hashCode would force all elements into the same bucket, reducing all find/contains operations to run using only underlying (the per-bucket) structure, that could be a List or somesuch.

请参见 https://en.wikipedia.org/wiki/Hash_table#Choosing_a_hash_function进行一般性说明.目前，Java HashSet 仅由 HashMap (来自Javadoc)支持( https://en.wikipedia.org/wiki/Hash_table#Sets ).

See https://en.wikipedia.org/wiki/Hash_table#Choosing_a_hash_function for generic explaination. Right now Java HashSet is just backed by HashMap (from Javadoc) (https://en.wikipedia.org/wiki/Hash_table#Sets).

这篇关于是否使用哈希码来加速集合中的对象查找?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！