Правильный способ реализации Map<MyObject,ArrayList<MyObject>>

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); (комментарий №1 в коде).возможно, что два разных экземпляра могут иметь один и тот же хэш-код.В этом случае я добавлю два разных объекта в один список.

Когда я получаю информацию, я должен получить список, который имеет два разных экземпляра.(комментарий №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

возможно, что два разных экземпляра могут иметь одинаковый хэш-код

Да, но hashCode Метод используется для определения индекса для хранения элемента.Два или более ключей могут иметь одинаковые hashCode но именно поэтому они также оцениваются с использованием equals.

От Map#containsKey Javaдокумент:

Возврат true если эта карта содержит сопоставление для указанного ключа.Более формально, возвращает true тогда и только тогда, когда это отображение содержит отображение для ключа k такое, что (key==null ? k==null : key.equals(k)).(Такое отображение может быть не более одного.)

---

Некоторые улучшения вашего текущего кода:

• Код, ориентированный на интерфейсы.Использовать 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#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();
  }
  

Answer 2

Использовать equals вместе с hashCode для решения состояния столкновения.

Шаги:

• Сначала сравните на основе названия в hashCode()
• Если заголовок такой же, посмотрите equals() на основе названия компании для разрешения состояния коллизии.

Образец кода

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

    public Alpha(String company, int local, String title) {
        this.company = company;
        this.local = local;
        this.title = title;
    }

    @Override
    public int hashCode() {
        return title.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Alpha) {
            return this.company.equals(((Alpha) obj).company);
        }
        return false;
    }
}

...

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

hashmap.put(new Alpha("a", 1, "t1"), new ArrayList<Alpha>());
hashmap.put(new Alpha("b", 2, "t1"), new ArrayList<Alpha>());
hashmap.put(new Alpha("a", 3, "t1"), new ArrayList<Alpha>());

System.out.println("Size : "+hashmap.size());

Выход

Size : 2