HashMap Java示例避免冲突

Question

我HashMap在java中使用存储密钥和Object <Key,Object>.我读到了关于hashmap的冲突,我试图通过使用链表来避免它.

我在网上做了一些搜索,但我找不到一个如何做到这一点的例子.

有人可以指向一个实现带有链表的hashmap的在线资源吗？

Answer 1

Java HashMap已经以这种方式为您处理冲突.您需要做的就是确保覆盖并实现密钥hashCode()和equals()方法.

每个都hash code将映射到特定的"桶".每个桶包含一个用于冲突情况的链表.

避免(或最小化)冲突的唯一方法是创建一个哈希函数,在整个HashMap中创建最佳的值分布.根据HashMap的密度和您的质量hash code,碰撞几乎是不可避免的,因此需要覆盖这两种方法.

编辑:OP问了一个例子

要覆盖这两种方法:

public class MyObject {
  String var1;
  int var2;

  //...
  public boolean equals(Object obj) {
    if(obj == null) return false;
    if(this == obj) return true;      // Reference equality
    if(!(obj instanceof MyObject)) return false;
    MyObject myObj = MyObject(obj);
    return (var1.equals(myObj.var1)) && (var2 == myObj.var2); 
  }
  public int hashCode {
     return var1.hashCode() ^ var2;
  }
}

Answer 2

仅当您使用与objectkey 相同或object与哈希码相同且等于equals的 key时，才会发生冲突。

为了正确使用HashMap，您应该在键类中正确实现hashCode and equals方法。阅读对象文档和本文。

如果要通过键存储多个对象，则应创建一个列表的HashMap。

这是一个简单的示例：

HashMap<Object, List<Object>> map = new HashMap<Object, List<Object>>();
map.put(key, new LinkedList<Object>);
map.get(key).add(object);