Java中的排序集合

Question

我是Java的初学者.请建议可以/应该使用哪些集合来维护Java中的排序列表.我曾尝试Map和Set,但他们不是我所期待的.

Answer 1

这来得很晚,但JDK中有一个类只是为了有一个排序列表.它被命名(与其他Sorted*接口有点不正常)" java.util.PriorityQueue".它可以对Comparable<?>s进行排序或使用a Comparator.

与使用List排序的差异Collections.sort(...)在于,这将通过使用堆数据结构始终保持部分顺序,具有O(log(n))插入性能,而在排序中插入ArrayList将是O(n)(即,使用二进制搜索和移动).

但是,与a不同List,PriorityQueue不支持索引访问(get(5)),访问堆中项目的唯一方法是将它们一次一个地取出(因此名称PriorityQueue).

Answer 2

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

Answer 3

如果你想维护一个你经常修改的排序列表(即除了排序之外,还允许重复并且索引可以有效引用其元素的结构),那么使用ArrayList但是当你需要插入一个元素时,始终使用Collections.binarySearch()来确定添加给定元素的索引.后一种方法告诉您需要插入的索引,以使列表按排序顺序排列.

Answer 4

使用Google Guava的TreeMultiset类.番石榴有一个壮观的收藏API.

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

Answer 5

您需要SortedSet实现,即TreeSet.

Answer 6

有几个选择.如果你不想重复,我建议使用TreeSet,你插入的对象是可比较的.

您还可以使用Collections类的静态方法执行此操作.

有关详细信息,请参阅集合#sort(java.util.List)和TreeSet.

Answer 7

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

Answer 8

我所做的是实现具有委托所有方法的内部实例的List.

 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();
}

Answer 9

实现所需排序列表的最有效方法是实现可索引的跳转列表，如下所示：Wikipedia：Indexable skiplist。这将允许在O（log（n））中进行插入/删除操作，并允许同时进行索引访问。而且它也允许重复。

跳过列表非常有趣，我想说的是低估的数据结构。不幸的是，Java基库中没有索引的跳过列表实现，但是您可以使用一种开源实现，也可以自己实现。有常规的Skiplist实现，例如ConcurrentSkipListSet和ConcurrentSkipListMap