一个很好的 Java 排序列表

Question

我正在为 java 寻找一个好的排序列表。谷歌搜索给了我一些关于使用 TreeSet/TreeMap 的提示。但是这些组件缺少一件事：随机访问集合中的一个元素。例如，我想访问排序集中的第 n 个元素，但使用 TreeSet 时，我必须遍历其他 n-1 个元素才能到达那里。这将是一种浪费，因为我的 Set 中会有多达数千个元素。

基本上，我正在寻找类似于 .NET 中排序列表的东西，能够快速添加元素、快速删除元素以及随机访问列表中的任何元素。

这种排序列表在某处实现了吗？谢谢。

已编辑

我对 SortedList 的兴趣源于这个问题：我需要维护一个包含数千个对象的列表（并且可以增长到数十万个）。这些对象将被持久化到数据库中。我想从整个列表中随机选择几十个元素。因此，我试图维护一个单独的内存列表，其中包含所有对象的主键（长数字）。当从数据库中添加/删除对象时，我需要从列表中添加/删除键。我现在正在使用 ArrayList，但我担心当记录数量增加时 ArrayList 不适合它。 （想象一下，每次从数据库中删除一个对象时，您都必须迭代数十万个元素）。回到我做 .NET 编程的时候，然后我会使用一个排序列表（List 是一个 .NET 类，一旦 Sorted 属性设置为 true，将保持其元素的顺序，并提供有助于删除/插入元素的二进制搜索很快）。我希望我能从 java BCL 中找到类似的东西，但不幸的是，我没有找到合适的匹配项。

原文由 Phương Nguyễn 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

似乎您想要一个列表结构，该列表结构具有非常快速的删除和 按索引（而不是按键）时间随机访问。 ArrayList 给你后者和 HashMap 或 TreeMap 给你前者。

Apache Commons Collections 中有一种结构可能就是您正在寻找的，即 TreeList 。 JavaDoc 指定它针对列表中任何索引处的快速插入和删除进行了优化。但是，如果您还需要泛型，这对您没有帮助。

原文由 Kevin Brock 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是我正在使用的 SortedList 实现。也许这有助于解决您的问题：

 import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
/**
 * This class is a List implementation which sorts the elements using the
 * comparator specified when constructing a new instance.
 *
 * @param <T>
 */
public class SortedList<T> extends ArrayList<T> {
    /**
     * Needed for serialization.
     */
    private static final long serialVersionUID = 1L;
    /**
     * Comparator used to sort the list.
     */
    private Comparator<? super T> comparator = null;
    /**
     * Construct a new instance with the list elements sorted in their
     * {@link java.lang.Comparable} natural ordering.
     */
    public SortedList() {
    }
    /**
     * Construct a new instance using the given comparator.
     *
     * @param comparator
     */
    public SortedList(Comparator<? super T> comparator) {
        this.comparator = comparator;
    }
    /**
     * Construct a new instance containing the elements of the specified
     * collection with the list elements sorted in their
     * {@link java.lang.Comparable} natural ordering.
     *
     * @param collection
     */
    public SortedList(Collection<? extends T> collection) {
        addAll(collection);
    }
    /**
     * Construct a new instance containing the elements of the specified
     * collection with the list elements sorted using the given comparator.
     *
     * @param collection
     * @param comparator
     */
    public SortedList(Collection<? extends T> collection, Comparator<? super T> comparator) {
        this(comparator);
        addAll(collection);
    }
    /**
     * Add a new entry to the list. The insertion point is calculated using the
     * comparator.
     *
     * @param paramT
     * @return <code>true</code> if this collection changed as a result of the call.
     */
    @Override
    public boolean add(T paramT) {
        int initialSize = this.size();
        // Retrieves the position of an existing, equal element or the
        // insertion position for new elements (negative).
        int insertionPoint = Collections.binarySearch(this, paramT, comparator);
        super.add((insertionPoint > -1) ? insertionPoint : (-insertionPoint) - 1, paramT);
        return (this.size() != initialSize);
    }
    /**
     * Adds all elements in the specified collection to the list. Each element
     * will be inserted at the correct position to keep the list sorted.
     *
     * @param paramCollection
     * @return <code>true</code> if this collection changed as a result of the call.
     */
    @Override
    public boolean addAll(Collection<? extends T> paramCollection) {
        boolean result = false;
        if (paramCollection.size() > 4) {
            result = super.addAll(paramCollection);
            Collections.sort(this, comparator);
        }
        else {
            for (T paramT:paramCollection) {
                result |= add(paramT);
            }
        }
        return result;
    }
    /**
     * Check, if this list contains the given Element. This is faster than the
     * {@link #contains(Object)} method, since it is based on binary search.
     *
     * @param paramT
     * @return <code>true</code>, if the element is contained in this list;
     * <code>false</code>, otherwise.
     */
    public boolean containsElement(T paramT) {
        return (Collections.binarySearch(this, paramT, comparator) > -1);
    }
    /**
     * @return The comparator used for sorting this list.
     */
    public Comparator<? super T> getComparator() {
        return comparator;
    }
    /**
     * Assign a new comparator and sort the list using this new comparator.
     *
     * @param comparator
     */
    public void setComparator(Comparator<? super T> comparator) {
        this.comparator = comparator;
        Collections.sort(this, comparator);
    }
}

该解决方案非常灵活，并使用现有的 Java 函数：

• 完全基于泛型
• 使用 java.util.Collections 查找和插入列表元素
• 使用自定义比较器进行列表排序的选项

一些注意事项：

• 此排序列表 不同步，因为它继承自 java.util.ArrayList 。如果需要，请使用 Collections.synchronizedList （有关详细信息，请参阅 Java 文档 java.util.ArrayList ）。
• 最初的解决方案基于 java.util.LinkedList 。为了更好的性能，特别是为了找到插入点（Logan 的评论）和更快的 获取 操作（ https://dzone.com/articles/arraylist-vs-linkedlist-vs ），这已更改为 java.util.ArrayList .

原文由 Konrad Holl 发布，翻译遵循 CC BY-SA 3.0 许可协议