java - 实现 Map> 的正确方法

Question

我在面试时被问到这个问题。不能使用 Google Guava 或 MultiMap。我有课

public class Alpha
{
     String company;
     int local;
     String title;
}

我有很多此类的实例(以百万计)。我需要处理它们，最后找到唯一的和它们的重复项。例如

instance --> instance1, instance5, instance7 (instance1 has instance5 and instance7 as duplicates)
instance2 --> instance2 (no duplicates for instance 2)

我的代码运行良好

声明数据结构

HashMap<Alpha,ArrayList<Alpha>> hashmap = new HashMap<Alpha,ArrayList<Alpha>>();

添加实例

for (Alpha x : arr)
{
    ArrayList<Alpha> list = hashmap.get(x); ///<<<<---- doubt about this. comment#1
    if (list == null)
    {
        list = new ArrayList<Alpha>();
        hashmap.put(x, list);
    }
        list.add(x);
}

打印实例及其副本。

for (Alpha x : hashmap.keySet())
{
    ArrayList<Alpha> list = hashmap.get(x); //<<< doubt about this. comment#2
    System.out.println(x + "<---->");
    for(Alpha y : list)
    {
        System.out.print(y);
    }
    System.out.println();
}

问题:我的代码可以运行，但是为什么？当我执行 hashmap.get(x); (代码中的 comment#1)时。两个不同的实例可能具有相同的哈希码。在这种情况下，我会将 2 个不同的对象添加到同一个列表中。

当我检索时，我应该得到一个包含 2 个不同实例的列表。 (评论＃2)，当我迭代列表时，我应该看到至少一个实例，该实例与键不重复，但仍然存在于列表中。我不。为什么？。我尝试从我的 hashCode 函数返回常量值，它工作正常。

如果您想查看我的 equals 和 hashCode 实现，请告诉我。

额外问题:有什么方法可以优化它吗？

编辑:

@Override
    public boolean equals(Object obj) {
        if (obj==null || obj.getClass()!=this.getClass())
            return false;
        if (obj==this)
            return true;
        Alpha guest = (Alpha)obj;
        return guest.getLocal()==this.getLocal()
                && guest.getCompany()  == this.getCompany()
                && guest.getTitle() == this.getTitle();
    }

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + (title==null?0:title.hashCode());
    result = prime * result + local;
    result = prime * result + (company==null?0:company.hashCode());
    return result;
}

Answer 1

it is possible that two different instances might have same hashcode

是的，但是hashCode方法用于标识存储元素的索引。两个或多个 key 可以具有相同的 hashCode但这就是为什么它们也使用 equals 进行评估.

来自 Map#containsKey javadoc:

Returns true if this map contains a mapping for the specified key. More formally, returns true if and only if this map contains a mapping for a key k such that (key==null ? k==null : key.equals(k)). (There can be at most one such mapping.)

<小时/>

对当前代码的一些增强:

• Code oriented to interfaces 。使用Map并通过 HashMap 实例化它。类似于 List和ArrayList .

• 比较 String和 Object一般使用equals方法。 ==比较引用文献，equals比较 Object 中存储的数据取决于此方法的实现。因此，更改 Alpha#equals 中的代码:

  public boolean equals(Object obj) {
      if (obj==null || obj.getClass()!=this.getClass())
          return false;
      if (obj==this)
          return true;
      Alpha guest = (Alpha)obj;
      return guest.getLocal().equals(this.getLocal())
              && guest.getCompany().equals(this.getCompany())
              && guest.getTitle().equals(this.getTitle());
  }
  

• 成对浏览 map 的所有元素时，请使用 Map#entrySet 相反，您可以节省 Map#get 使用的时间(因为它应该是 O(1)，所以你不会节省那么多，但它更好):

  for (Map.Entry<Alpha, List<Alpha>> entry : hashmap.keySet()) {
      List<Alpha> list = entry.getValuee();
      System.out.println(entry.getKey() + "<---->");
      for(Alpha y : list) {
          System.out.print(y);
      }
      System.out.println();
  }