Java中的排序集合

Question

我是Java的初学者，请建议在Java中用哪些集合（集合）来维护有序列表。我尝试过 Map 和 Set ，但它们不是我想要的。

- rohan

Answer 1

虽然有些晚，但JDK中有一个专门用于排序列表的类。它被命名为（与其他Sorted*接口略有不同）"java.util.PriorityQueue"。它可以使用Comparable<?>或使用Comparator进行排序。

与使用Collections.sort(...)排序的List的区别在于，PriorityQueue将始终保持部分顺序，并且通过使用堆数据结构具有O(log(n))的插入性能，而在已排序的ArrayList中插入将是O(n)（即使用二进制搜索和移动）。

但是，与List不同的是，PriorityQueue不支持索引访问（get(5)），访问堆中的项目的唯一方法是一个一个地取出（因此称为PriorityQueue）。

- Martin Probst

---

我认为这个答案应该得到更多的赞，因为它指出了在JDK中具有此功能的唯一集合。 - nimcap

来自Javadoc的内容：“在方法iterator()中提供的迭代器不能保证以任何特定顺序遍历PriorityQueue的元素。” - Christoffer Hammarström

@giraff: 优先队列就是一个非常高效的数据结构，可以很好地维护优先级。你可以从前面获取数据项并按排序顺序排列。然而，堆在内部不维护元素的完全顺序（这就是它们如此有效的原因），因此没有办法在不执行poll操作的情况下按顺序访问元素。 - Martin Probst

@chrispy 这有点取决于你想用数据结构实现什么。堆是一种有效的方式来维护项目列表，并在以后以有序的方式检索它们 - 使用迭代器不起作用，但如果你从中轮询，你将按顺序获取你的数据。检索是破坏性的，但在许多情况下仍然可以接受。所以我认为这个答案很好。 - Martin Probst

@MartinProbst，请纠正你的答案，清楚地表明该集合无法按预期顺序迭代。正如许多人所说，这极其具有误导性！ - Jorge Galvão

Answer 2

TreeMap 和 TreeSet 将以排序顺序迭代内容。或者您可以使用 ArrayList 并使用 Collections.sort() 进行排序。所有这些类都在 java.util 中。

- brazzy

---

然而，这种方法存在两个主要缺点，第一个是Set不能包含重复元素。第二个是，如果你使用列表和Collections.sort()，你往往需要不断地对大型列表进行排序，这会导致性能下降。虽然你可以使用“脏”标志，但效果并不完全一样。 - Jeach

这引出了一个问题，即在Java中是否有一种选项允许重复，并且提供类似于Set（平衡二叉树）的性能。 - mankadnandan

SortedSet/TreeMap的另一个问题是，即使您的键是唯一的，但不同键的比较器值相同，它们也无法工作。例如，如果使用以下代码进行排序： TreeSet((UniqueKey1, UniqueKey2) -> Comparator.compare(otherValueLookup.get(key1), otherValueLookup.get(key2))当otherValue相同时，这将导致排序失败！结论：如果两个键根据比较器是不同但相等的，则TreeSet/TreeMap不会添加值。 - kisna

需要补充的是，我们仍然可以使用TreeSet/TreeMap，解决方法是如果键相同，则创建一个随机生成器：ThreadLocalRandom r = ThreadLocalRandom.current(); boolean randomBoolean = r.nextBoolean();if (key1.equals(key2)) { // ** 如果它们相等，请使用RANDOM比较器 ** return randomBoolean ? 1 : -1; } else { return key1.compareTo(key2); } - kisna

“随机比较器”是一个不好的想法，会导致奇怪的行为。您的比较器应该对于相同的实例是一致的。但是您可以基于UUID进行比较，请参见https://dev59.com/RMXsa4cB1Zd3GeqPYEaB - Ricola

Answer 3

使用Google Guava的TreeMultiset类。Guava拥有出色的集合API。

提供维护排序顺序的List实现的一个问题是JavaDocs中add()方法所做出的承诺。

- jtb

---

多重集建议值得赞扬 - darthtrevino

提到List必须始终在末尾添加的要求，给你点赞。 - Roland Illig

请注意，TreeMultiSet 仍不允许重复元素（compareTo（）返回 0 而不是 equals（）检查）。如果倾向于添加相同优先级的多个项，则仅增加第一个添加的项的计数，舍弃其他项，并有效地成为良好的计数袋实现。 - bekce

Answer 4

如果您希望维护一个排序的列表，并且您会经常对其进行修改（也就是说，这个结构不仅是有序的，而且允许重复，并且可以通过索引高效地引用其元素），那么请使用ArrayList。但是在需要插入元素时，始终要使用Collections.binarySearch()方法来确定索引，以添加给定的元素。后一种方法告诉您需要插入的索引，以使您的列表保持排序状态。

- Neil Coffey

---

插入n个元素的时间复杂度为O(n^2)。使用TreeSet可以让你的代码更简洁，并且时间复杂度为O(n log n)。但是，如果修改操作不频繁，使用数组进行二分查找将会更快，并且使用的内存更少（因此减少垃圾回收开销）。 - Tom Hawtin - tackline

在我看来，这是一个比最受欢迎的答案更好的回答，如果您可以接受@TomHawtin-tackline提到的警告。迭代器按预期工作对于大多数情况至关重要。 - DuneCat

顺便提一下，Tom 在特定行为上是正确的：树集将给您更有效的修改。但是树集不是列表（严格意义上具有由索引引用的元素并允许重复项），而发帖人说他们想要一个列表。 - Neil Coffey

谢谢你，尼尔，真是太棒了！ - vikingsteve

如果列表允许重复，则 Collections.binarySearch 不是非常可靠的 imo。 - nawfal

Answer 5

你需要的是SortedSet实现，即TreeSet。

- cletus

---

不一定；集合中不能有重复的值。这取决于发帖者的要求。 - Zach Langley

Answer 6

有几种选择。如果你不想要重复项并且插入的对象是可比较的，我建议使用TreeSet。

您也可以使用Collections类的静态方法来实现此目的。

有关更多信息，请参见Collections#sort(java.util.List)和TreeSet。

- BenM

Answer 7

如果你只需要对列表进行排序，可以使用任何类型的List并使用Collections.sort()。 如果你想确保列表中的元素是唯一且始终有序，请使用SortedSet。

- Guillaume

Answer 8

实现你想要的有序列表最有效的方法是实现可索引跳表，就像这里所示：维基百科：可索引跳表。它允许在O(log(n))时间内进行插入/删除操作，并同时允许索引访问。它还允许重复项。

跳表是一种非常有趣且被低估的数据结构。不幸的是，Java基本库中没有索引化的跳表实现，但您可以使用其中一个开源实现或自己实现。有常规的跳表实现，如ConcurrentSkipListSet和ConcurrentSkipListMap。

- vladich

Answer 9

我所做的是实现一个带有内部实例的列表，并委托所有方法。

 public class ContactList implements List<Contact>, Serializable {
    private static final long serialVersionUID = -1862666454644475565L;
    private final List<Contact> list;

public ContactList() {
    super();
    this.list = new ArrayList<Contact>();
}

public ContactList(List<Contact> list) {
    super();
    //copy and order list
    List<Contact>aux= new ArrayList(list);
    Collections.sort(aux);

    this.list = aux;
}

public void clear() {
    list.clear();
}

public boolean contains(Object object) {
    return list.contains(object);
}

我已经实现了一种新的方法"putOrdered"，如果元素不存在，则将其插入到适当的位置，如果存在，则进行替换。

public void putOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
        list.add(index, contact);
    }else{
        list.set(index, contact);
    }
}

如果你想允许重复的元素，只需实现 addOrdered 方法（或两者都实现）。

public void addOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
    }
    list.add(index, contact);
}

如果你想避免插入操作，也可以在“add”和“set”方法上抛出不支持的操作异常。

public boolean add(Contact object) {
    throw new UnsupportedOperationException("Use putOrdered instead");
}

...同时，您需要注意ListIterator方法可能会修改您的内部列表。在这种情况下，您可以返回内部列表的副本或再次引发异常。

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}

- Carlos Verdes

---

问题在于这违反了List契约。也许只实现Collection会更好。如果ContactList已排序，则可以使用binarySearch实现contains()以提高效率。 - Marcono1234

Answer 10

TreeSet无法使用，因为它们不允许重复的元素，并且它们没有提供获取特定位置元素的方法。PriorityQueue也无法使用，因为它不允许获取特定位置的元素，这是列表的基本要求之一。

我认为你需要在Java中实现自己的算法来维护一个排序列表，其插入时间为O（logn），除非你不需要重复的元素。也许一个解决方案是使用TreeMap，其中键是item子类，覆盖equals方法，以便允许重复的元素。

- Giuseppe