我使用的是HashMap
,我还不能直接回答get()
方法在冲突情况下是如何工作的。
假设n > 1
对象被放置在同一个key中。它们是否存储在LinkedList
中?它们是否被覆盖,以便只有放置在该key中的最后一个对象存在于那里?它们是否使用了其他碰撞方法?
如果它们放在LinkedList
中,是否有办法检索整个列表?如果没有,是否有其他内置的JavaMap,我可以在其中执行此操作?
就我的目的而言,独立链接是理想的,因为如果有冲突,我需要能够浏览列表并获得其中所有对象的信息。在Java中,实现这一点的最佳方法是什么?
谢谢你的帮助!
6条答案
按热度按时间00jrzges1#
它们是否被覆盖,以便只有最后放置在该键中的对象才存在?
是的,假设您将多个值放入同一个键(根据
Object.equals
,而不是Object.hashCode
),这在Map.put
javadoc中指定:如果Map以前包含键的Map,则旧值将替换为指定值。
如果您想将一个键Map到多个值,最好使用Guava的
ListMultimap
,具体来说就是ArrayListMultimap
,它将键Map到值列表。如果您不能容忍第三方库,那么实际上您必须有一个Map<Key, List<Value>>
,尽管这可能有点笨拙。gt0wga4j2#
Hashmap.put()的文档明确指出,“将指定的值与此Map中的指定键关联。如果Map以前包含键的Map,则替换旧值”
如果您希望拥有一个与键关联的对象列表,则将列表存储为值。
请注意,“冲突”通常指HashMap的内部工作,其中两个键具有相同的哈希值,而不是对两个不同的值使用相同的键。
lsmepo6l3#
假设有n〉1个对象被放置在同一个键中,它们是否被存储在一个链表中?它们是否被覆盖,使得只有最后放置在该键中的对象才存在?它们是否使用了其他的碰撞方法?
同一个键可能有一个示例,因此最后一个会覆盖前一个
链接出现在为不同的键转换相同的散列的地方
参见
brqmpdu14#
所以我最后会提供答案:每当HashMap实现遇到冲突时(当两个或多个key对象返回相同的hash()值时),它会将这些键-值对(节点)链接起来,从而通过其结构产生一个LinkedList。因此,每当您使用以前导致与其他对象冲突的key调用“get(key)”时,它将:
1.找一个桶;
1.遍历该bucket所引用的链表以找到确切的key对象;
1.它将在迭代过程中使用LinkedList中Key对象的方法“equals()”,以最终获得所需的Key,并作为结果-您正在寻找的Value。
注意:* 要解决冲突,您应该为Key对象类提供“equals()”和“hashcode()”实现。*
参与HashMap组合的所有类型都应该为它们提供显式实现(equals和hashcode)。
为此,请遵循下一个约定:
-------等于--------
主要条件:[任何内容!= null]
·自反性:x.等于(x)=真。
·对称:x等于(y)== y等于(x)。
·传递性:x.等于(y)== y.等于(z)== x.等于(z)。
·持续:x.equals(y)的多次调用一致地仅返回真或仅返回假(equals中使用的数据不应改变)。
·不可为空:x.等于(空)=假。
-------散列代码----------
·内部一致性:仅当Equals()中的属性更改时,HashCode()才会更改。
·等于一致性:对象x.equals(y)= true必须返回相同的哈希代码。
·碰撞:不相等的对象可以具有相同的HashCode。
rqcrx0a65#
引用:“假设n〉1个对象被放置在同一个键中。它们被存储在一个链表中吗?它们被覆盖了吗?这样只有最后一个被放置在那个键中的对象存在了吗?它们使用了其他的碰撞方法吗?”
是的,如果散列表在这个键下包含了一些东西,它将覆盖它。
您可以实现自己的类来处理这个问题,或者更简单地使用一个HashMap〉,其中K是您的Key对象,V是对象值。请记住,当您执行Map时,使用上一个解决方案,get(K)将检索您选择的List或实现(即:ArrayList),所以这个实现的所有方法都是可用的,也许能满足你的要求。例如,如果你使用Arraylist,你有size,trimToSize,removeRange等。
0md85ypi6#
在java中,哈希的冲突解决不是基于链接的。据我所知,JDK使用双哈希,这是开放寻址的最佳方式之一。所以没有列表会与哈希槽相关联。
您可以将哈希函数解析为相同键的对象放入列表中,并且可以在表/Map中更新此列表。
在上面的代码中,我展示了两个不同的东西.
情况1 -两个不同的示例解析为相同的散列键情况2 -两个相同的示例充当两个不同条目的键。
动物示例,a1和a2解析到相同的键。但是它们不能被覆盖。哈希机制通过哈希槽进行探测,并将条目放置在不同的槽中。
在第二种情况下,键解析为相同的散列键,并且equals方法也满足。2因此重写发生。
如果在动物类中我用这种方法重写equals方法-
覆盖发生了。行为就像使用相同的示例。因为a1和a2在同一个桶中,并且等于也返回true。