如果两个不同的对象具有相同的哈希码,会发生什么?
据我所知,两个不相等的对象可以具有相同的哈希码。 在从HashMap java添加或检索时如何处理?
它们将被添加到同一个桶中, equals()
将用于区分它们。 每个存储桶都可以包含具有相同哈希码的对象列表。
从理论上讲,您可以为给定类的任何对象返回与哈希代码相同的整数,但这意味着您将失去哈希映射的所有性能优势,并且实际上会将对象存储在列表中。
在HashMap中,键及其关联值存储在存储桶中的链接列表节点中,并且密钥基本上使用equals()方法而不是hashcode在hashmap中进行比较。
hm.put("a","aValue"); // Suppose hashcode created for key "a" is 209 hm.put("b","bValue"); // Here hashcode created for key "b" is 209 as well.
- 如果
a.equals(b)
返回true
,则bValue
将替换aValue
并返回bValue
。 - 如果
a.equals(b)
返回false
,则将在桶列表中创建另一个节点,因此当您调用get("b")
您将获得bValue
因为a.equals(b)
为false
。
HashMap正在研究散列和索引的概念。 内部HashMap将值存储在节点数组中。 每个节点都表现为LinkedList。
链表的每个节点都有4个值:
-
int hash
-
K key
-
V value
-
Node
next
HashMap内部结构:
在HashMap中插入值时,会生成Key的第一个哈希码,并根据某些算法计算索引。
因此,我们的值将存储在特定索引中,包含下一个元素的哈希码,键,值和地址。
从HashMap中检索值时,第一个哈希码将生成然后索引(与插入时的方式相同)。 从索引获取值时,首先它将检查哈希码,如果哈希码匹配,则只有它将使用equals方法从Node检查密钥。 如果key匹配则只返回值,否则它将检查具有相同哈希码的下一个Node。
在这种情况下,您可以使用IdentityHashMap,其中具有相同散列的不同对象根据其身份被视为不同。
当两个不相等的对象具有相同的哈希值时,这会导致哈希表中的冲突,因为两个对象都希望位于同一个槽中(有时称为桶)。 哈希算法必须解决此类冲突。 回到我大学算法课程的褪色记忆中,我记得三种基本方法:
- 查找哈希表中的下一个空槽并将对象放在那里。 优点:易于实现,缺点:可能导致对象聚集并降低性能,可能会超出容量
- 在发生冲突时使用辅助哈希函数:优点:通常很快,缺点:必须编写第二个哈希函数并且仍然可能发生冲突,并且可能会超出容量
- 从哈希表的冲突插槽中创建对象的链接列表。 优点/缺点:通常快速获得合适的散列函数和负载因子,但在最坏的情况下会降级为线性搜索
我认为Java哈希类使用第三种方法,但它们可能使用组合方法。 良好哈希的关键是确保哈希表具有足够大的容量并编写好的哈希函数。 只有与其持有的对象一样多的存储桶的哈希表可能会有冲突。 通常,您希望哈希表大约是它存储的对象数量的两倍。 Java的HashMap将根据需要增长,但如果需要,可以为其提供初始容量和加载因子。
哈希函数取决于程序员。 您可以为所有对象返回0,但这意味着散列(存储和检索)将变为O(n)而不是O(1)…或者在非专业术语中,它将是狗慢。
参考: http : //www.coderanch.com/t/540275/java/java/objects-hashcode-HashMap-retrieve-objects