LinkedList 和 TreeMap：compareTo 或 equals？

Question

我需要澄清有关 TreeMap 和 LinkedList 的使用。这两个结构是使用 compareTo 还是 equals？

特别是，TreeMap 保持键中的顺序，我想使用为键定义的 class 的 compareTo 方法。但是，在使用get的时候，他们是使用compareTo还是equals来查看你传递的key是否被包含？

我对LinkedList里面的contains和getIndex也有同样的疑问

Answer 1

TreeMap 和 LinkedList 的 Javadoc 回答了这个问题：

V java.util.TreeMap.get(Object key)

Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

More formally, if this map contains a mapping from a key k to a value v such that key compares equal to k according to the map's ordering, then this method returns v; otherwise it returns null. (There can be at most one such mapping.)

和

boolean java.util.LinkedList.contains(Object o)

Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e)).

因此，对于 TreeMap，Comparator\Comparable 实现用于确定键的相等性，而对于 LinkedLists，使用 equals。

Answer 2

TreeMap 使用 compareTo，如果 compareTo 与 equals 不一致（即 a.compareTo(b) == 0 <=> a.equals(b)应该是真的）。

Note that the ordering maintained by a tree map ... must be consistent with equals if this sorted map is to correctly implement the Map interface.

LinkedList 使用 equals.

TreeMap 必须使用与 equals 一致的顺序的原因是 Map 的合同根据 equals 定义了行为。例如，containsKey 定义为：

returns true if and only if this map contains a mapping for a key k such that (key==null ? k==null : key.equals(k))

假设您这样定义 class：

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 没有与 equals 一致地实施 Comparable。

LinkedList 和 TreeMap：compareTo 或 equals？

LinkedList and TreeMap: compareTo or equals?

java

linked-list

treemap