6

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

我在网上做了一些搜索，但找不到如何执行此操作的示例。

有人可以指出我使用链表实现哈希图的在线资源吗？

4

2 回答 2

8

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

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

避免（或更确切地说是最小化）冲突的唯一方法是创建一个散列函数，该函数在整个 HashMap 中创建最佳的值分布。根据 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;
  }
}
于 2012-07-30T18:58:58.910 回答
5

仅当您使用与objectkey 相同或object与具有相同哈希码和equals的 key 不同时才会发生冲突。

为了正确使用 HashMap，您应该在关键类中正确实现 hashCode 和 equals 方法。阅读 Object 文档和这篇文章。

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

这是一个简单的例子：

HashMap<Object, List<Object>> map = new HashMap<Object, List<Object>>();
map.put(key, new LinkedList<Object>);
map.get(key).add(object);
于 2012-07-30T19:02:29.537 回答