LinkedList и TreeMap: сравнить или равно? - PullRequest
Новая
       8

LinkedList и TreeMap: сравнить или равно?

0 голосов
/ 29 января 2019

Мне нужно разъяснение относительно использования TreeMap и LinkedList.Используют ли эти две структуры сравнение или равно?

В частности, TreeMap поддерживает порядок в ключах, я полагаю, используя метод CompareTo класса, определенного для ключей.Тем не менее, при использовании get они используют compareTo или equals, чтобы увидеть, содержится ли передаваемый ключ?

У меня есть те же сомнения в отношении содержимого и getIndex внутри LinkedList.

Ответы [ 2 ]

0 голосов
/ 29 января 2019

TreeMap использует compareTo, а документация предупреждает вас о проблемах, если compareTo не соответствует equals (то есть, что a.compareTo(b) == 0 <=> a.equals(b) должно быть истинным).

Обратите внимание, что порядок, поддерживаемый древовидной картой ... должен быть в соответствии с равным , если эта отсортированная карта предназначена для правильной реализации интерфейса карты.

LinkedList использует equals.

Причина, по которой TreeMap должен использовать порядок в соответствии с equals, заключается в том, что контракт Map определяет поведение в терминах equals.Например, containsKey определяется как:

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

Допустим, вы определили класс следующим образом: 

class Bad implements Comparable<Bad> {
  @Override public int compareTo(Bad other) { return 0; }
}

Если бы вы написали: 

Bad b1 = new Bad();
Bad b2 = new Bad();

Тогда: 

Map<Bad, String> hm = new HashMap<>();
hm.put(b1, "");
System.out.println(hm.containsKey(b2));  // false

, тогда как 

Map<Bad, String> tm = new TreeMap<>();
tm.put(b1, "");
System.out.println(tm.containsKey(b2));  // true

несмотря на то, что 

System.out.println(tm.keySet().stream().anyMatch(k -> k.equals(b2))); // false

Таким образом, TreeMap нарушает договор Map, поскольку Bad не реализует Comparable в соответствии сequals.

0 голосов
/ 29 января 2019

Javadoc TreeMap и LinkedList отвечает на это:

V java.util.TreeMap.get (ключ объекта)

Возвращаетзначение, которому сопоставлен указанный ключ, или ноль, если эта карта не содержит сопоставления для ключа.

Более формально, если эта карта содержит отображение ключа k на значение v, такое, что ключ сравнивается равным k согласно порядку карты, то этот метод возвращает v;в противном случае возвращается ноль.(Может быть не более одного такого сопоставления.)

и

логический java.util.LinkedList.contains (Объект o)

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

Итак, для TreeMap реализация Comparator \ Comparable используется для определения равенства ключей, а для LinkedList s equals используется.

...