CompareTo 可能返回 0，替代 TreeSet/TreeMap

Question

我需要一组已排序的对象，目前正在使用 TreeSet。我的问题是对象的 compareTo 通常会返回 0，这意味着这两个对象的顺序保持不变。 TreeMap（默认情况下由 TreeSet 使用）会将它们视为同一个对象，但事实并非如此。

我可以使用什么替代TreeMap？

---

用例：我有一组可显示对象。我想按 Y 坐标对它们进行排序，以便它们以正确的顺序呈现。当然，两个对象很可能具有相同的 Y 坐标。

Answer 1

您正在定义一个要比较的标准，但您需要添加额外的标准。

你说：

我有一组可显示的对象。我想按 Y 坐标对它们进行排序，以便它们以正确的顺序呈现。当然，两个对象很可能具有相同的 Y 坐标。

那么，如果两个元素具有相同的 Y 坐标，您首先放置什么？其他标准是什么？

它可能是创建时间，也可能是 x 坐标，您只需定义它：

Map<String,Thing> map = new TreeMap<String,Thing>(new Comparator<Thing>(){
     public int compare( Thing one, Thing two ) {
         int result = one.y - two.y;
         if( result == 0 ) { // same y coordinate use another criteria
             result = one.x - two.x;
             if( result == 0 ) { //still the same? Try another criteria ( maybe creation time
                 return one.creationTime - two.creationTime
             }
          }
          return result;
     }
});

您必须定义一个 Thing 何时高于/低于/等于/高于其他 Thing .如果其中一个属性与其他属性相同，您可能不应该移动它们。如果有其他属性可以比较，就使用它。

Answer 2

您遇到的问题是 compareTo 返回 0 意味着对象相等。同时，您将它们放入一个集合中，该集合不允许相同元素的多个副本。

要么重写您的compareTo，以便不相等的元素返回不同的值，要么使用类似于java.util.PriorityQueue的东西，它允许相等元素的多个副本。

Answer 3

我以前做过这个。它是一个有序的多重映射，它只是一个 List 对象的 TreeMap。像这样......

Map<KeyType, List<ValueType>> mmap = new TreeMap<KeyType, List<ValueType>>();

每次引入新键时，您都需要构造一个新的 LinkedList，因此将其包装在自定义容器类中可能会有所帮助。我会尝试找到一些东西。

---

因此，我快速地将这个自定义容器放在一起（完全未经测试），但这可能就是您正在寻找的。请记住，只有当您确实正在寻找值列表的有序映射时，才应该使用这种类型的容器。如果您的值存在某种自然顺序，您应该像其他人建议的那样使用 TreeSet。

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class MTreeMap<K, V> {

   private final Map<K, List<V>> mmap = new TreeMap<K, List<V>>();
   private int size = 0;

   public MTreeMap() {
   }

   public void clear() {
      mmap.clear();
      size=0;
   }

   public boolean containsKey(K key) {
      return mmap.containsKey(key);
   }

   public List<V> get(K key) {
      return mmap.get(key);
   }

   public boolean isEmpty() {
      return mmap.isEmpty();
   }

   public Set<K> keySet() {
      return mmap.keySet();
   }

   public Collection<List<V>> valueLists() {
      return mmap.values();
   }

   public void put(K key, V value) {

      List<V> vlist = mmap.get(key);
      if (null==vlist) {
         vlist = new LinkedList<V>();
         mmap.put(key, vlist);
      }
      vlist.add(value);
      ++size;
   }

   public List<V> remove(Object key) {
      List<V> vlist = mmap.remove(key);

      if (null!=vlist) { 
         size = size - vlist.size() ;
      }
      return vlist;
   }

   public int size() {
      return size;
   }

   public String toString() {
      return mmap.toString();
   }

}

---

这是一个基本测试：

public class TestAnything {

   public static void main(String[] args) {

      MTreeMap<Integer, String> mmap  = new MTreeMap<Integer, String>();

      mmap.put(1, "Value1");
      mmap.put(2, "Value2");
      mmap.put(3, "Value3");
      mmap.put(1, "Value4");
      mmap.put(3, "Value5");
      mmap.put(2, "Value6");
      mmap.put(2, "Value7");

      System.out.println("size (1) = " + mmap.get(1).size());
      System.out.println("size (2) = " + mmap.get(2).size());
      System.out.println("size (3) = " + mmap.get(3).size());
      System.out.println("Total size = " + mmap.size());

      System.out.println(mmap);
   }

}

输出如下：

size (1) = 2
size (2) = 3
size (3) = 2
Total size = 7
{1=[Value1, Value4], 2=[Value2, Value6, Value7], 3=[Value3, Value5]}

Answer 4

我有自己的一个想法，但这更多的是一种解决方法

int compare(Object a, Object b) {
   an = a.seq + (a.sortkey << 16); // allowing for 65k items in the set
   bn = b.seq + (a.sortKey << 16);
   return an - bn; // can never remember whether it's supposed to be this or b - a.
}

• sortKey = 对于排序真正重要的内容，例如 Y 坐标
• seq = 添加到集合时分配给对象的序列号

Answer 5

使用排序集（例如 TreeSet）时需要记住两件重要的事情：

1）它们是集合；同一集合中不允许有两个相等的元素

2) 相等必须与比较机制一致（比较器或可比较）

因此，在您的情况下，您应该通过添加一些辅助排序标准来“打破联系”。例如：首先使用 Y 轴，然后是 X 轴，然后是一些唯一的对象标识符。

另请参阅 http://eyalsch.wordpress.com/2009/11/23/comparators /