Почему TreeSet считает дублирование элементов по значениям ключей HashSet, а не по самим ключам?

Question

[4eloBek]

В Java я новичек. Подтягиваю знания языка на codewars.com. Выполняя одно из заданий, столкнулся со странностью: хочу реализовать приоритетную очередь в алгоритме Дейкстры, и для оптимизации по времени выбрал такую структуру данных как TreeSet.

import java.util.*;

public class TestTreeSet {
  public static void main(String[] args) {
    int[][] arr = {{1, 2, 3, 4, 5, 6}, {4, 9, 1, 2, 6, 0}};
    HashMap<Integer, Integer> d = new HashMap<>();
    for (int i = 0; i < arr[0].length; i++)
      d.put(arr[0][i], arr[1][i]);
    
    TreeSet<Integer> s = new TreeSet<>(new Comparator() {
      public int compare(Object o1, Object o2) {
        return d.get((int) o1) - d.get((int) o2);
      }
    });
    for (int i = 1; i < 7; i++) s.add(i);
    System.out.println(s); // [6, 3, 4, 1, 5, 2]
    
    int k = 6;
    if (s.contains(k)) {
      s.remove(k);
      d.put(k, 2);
      System.out.println(s.add(k)); // false
    }
    System.out.println(s); // [3, 4, 1, 5, 2]
  }
}

Почему (в моей ситуации) TreeSet считает дублирование элементов по значениям ключей HashSet?
Возможно ли сделать классический запрет на дублирование элементов (ключей HashSet), но оставить сортировку по значению ключей? Заранее спасибо)

Answer 1

[Михаил]

Потому что вы так определили компаратор. Метод compare имеет следующий контракт:
возвращает

• отрицательное значение если o1 меньше o2
  
• положительное значение если o1 больше o2
  
• нуль если o1 равно o2.
  

Собственно никакого дублирования по ключам HashSet тут нет - это работа вашего компаратора.
А то что результат работы компаратора противоречит результату работы метода equals - это ошибка программиста, от которой Java никак не может предостеречь.
После выполнения вызова d.put(k, 2); вы сами сделали так, что compare(6, 3) == 0, то есть сами сформулировали утверждение что 3 == 6. И TreeSet, безусловно, в это верит, зачем ему вас перепроверять вызовом equals? Это же не хэшкод, который подвержен коллизиям - это компаратор, который по своей природе не должен допускать коллизий.

UPD: Что же касается вашей цели - реализации приоритетной очереди - то чем вам готовый класс PriorityQueue не угодил?

Comments

[4eloBek]

Понятно. Спасибо. Попробую PriorityQueue