在Java中的有序集的任何实现？

如果有人熟悉Objective-C，那么有一个名为NSOrderedSet的集合，它充当Set ，其项目可以作为Array的访问。

在Java中有这样的东西吗？

我听说有一个名为LinkedHashMap的集合，但是我没有发现任何类似的集合。

Answer 1

看看LinkedHashSet类

Answer 2

每个集合都有一个迭代器（）。 正常的HashSet的迭代器是非常随机的，TreeSet按照sorting顺序执行， LinkedHashSet迭代器按插入顺序迭代。

但是，您无法replaceLinkedHashSet中的元素。 您可以删除一个并添加另一个，但新元素将不在原始位置。 在LinkedHashMap中，可以replace现有密钥的值，然后这些值仍将按原始顺序排列。

另外，您不能在某个位置插入。

也许你最好使用一个明确的检查来避免插入重复的ArrayList。

Answer 3

看看Java标准API文档 。 在LinkedHashMap旁边，有一个LinkedHashSet 。 但请注意，这些顺序是插入顺序，而不是元素的自然顺序。 你只能按顺序迭代，而不能进行随机访问（除了计算迭代步骤）。

还有一个由TreeSet和ConcurrentSkipListSet实现的接口SortedSet 。 两者都允许以元素或Comparator的自然顺序迭代，但不允许随机访问或插入顺序。

对于既有索引高效访问又能有效实现集合标准的数据结构，你需要一个跳过列表 ，但在Java Standard API中没有实现这个function，但我确信很容易find一个在网上。

Answer 4

TreeSet是有序的。

http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

Answer 5

尝试使用实现SortedSet java.util.TreeSet 。

引用文档：

“元素是按照自然顺序sorting的，或者是在创build集合时提供的比较器，具体取决于使用哪个构造函数”

请注意，添加，删除和包含的时间成本log（n）。

如果您想以数组的forms访问该组的内容，则可以将其转换为：

 YourType[] array = someSet.toArray(new YourType[yourSet.size()]); 

这个数组将按照与TreeSet（自然或比较器）相同的标准进行sorting，在很多情况下，这将有一个优势，而不是做一个Arrays.sort（）

Answer 6

treeset是一个有序集合，但不能通过项目索引访问，只需遍历或者转到开始/结束。

Answer 7

如果我们谈论跳过列表的廉价实现，我想知道大O，这个操作的成本是多less：

YourType [] array = someSet.toArray（new YourType [yourSet.size（）]）;

我的意思是它总是陷入一个完整的数组创build，所以它是O（n）：

 java.util.Arrays#copyOf 

Answer 8

Indexed -tree-map项目的IndexedTreeSet提供了这个function（按索引列表式访问的有序/sorting集）。

Answer 9

您也可以从双向映射中获得一些实用的function，例如Google Guava的BiMap

使用BiMap ，您可以非常高效地将Integer（用于随机索引访问）映射到任何其他对象types。 BiMap是一对一的，所以任何给定的整数至多有一个与它关联的元素，任何元素都有一个关联的整数。 它由两个HashTable实例巧妙地支撑，所以它使用的内存几乎是双倍，但是就处理而言，它比自定义List更有效，因为contains() （当添加项目以检查它是否已经存在时会被调用）是一个像HashSet一样的常量并行HashSet的操作，而List的实现是一个很慢的操作。

Answer 10

我有一个类似的问题。 我不太需要一个有序的集合，但更多的是一个快速indexOf / contains的列表。 因为我没有find任何东西，所以我自己实现了一个。 这里是代码，它实现了Set和List ，尽pipe不是所有的批量列表操作都和ArrayList版本一样快。

免责声明：未经testing

 import java.util.ArrayList; import java.util.HashMap; import java.util.Set; import java.util.Collection; import java.util.Comparator; import java.util.function.Predicate; import java.util.function.UnaryOperator; import static java.util.Objects.requireNonNull; /** * An ArrayList that keeps an index of its content so that contains()/indexOf() are fast. Duplicate entries are * ignored as most other java Set's do. */ public class IndexedArraySet<E> extends ArrayList<E> implements Set<E> { public IndexedArraySet() { super(); } public IndexedArraySet(Iterable<E> c) { super(); addAll(c); } private HashMap<E, Integer> indexMap = new HashMap<>(); private void reindex() { indexMap.clear(); int idx = 0; for (E item: this) { addToIndex(item, idx++); } } private E addToIndex(E e, int idx) { indexMap.putIfAbsent(requireNonNull(e), idx); return e; } @Override public boolean add(E e) { if(indexMap.putIfAbsent(requireNonNull(e), size()) != null) return false; super.add(e); return true; } @Override public boolean addAll(Collection<? extends E> c) { return addAll((Iterable<? extends E>) c); } public boolean addAll(Iterable<? extends E> c) { boolean rv = false; for (E item: c) { rv |= add(item); } return rv; } @Override public boolean contains(Object e) { return indexMap.containsKey(e); } @Override public int indexOf(Object e) { if (e == null) return -1; Integer i = indexMap.get(e); return (i == null) ? -1 : i; } @Override public int lastIndexOf(Object e) { return indexOf(e); } @Override @SuppressWarnings("unchecked") public Object clone() { IndexedArraySet clone = (IndexedArraySet) super.clone(); clone.indexMap = (HashMap) indexMap.clone(); return clone; } @Override public void add(int idx, E e) { if(indexMap.putIfAbsent(requireNonNull(e), -1) != null) return; super.add(idx, e); reindex(); } @Override public boolean remove(Object e) { boolean rv; try { rv = super.remove(e); } finally { reindex(); } return rv; } @Override public void clear() { super.clear(); indexMap.clear(); } @Override public boolean addAll(int idx, Collection<? extends E> c) { boolean rv; try { for(E item : c) { // check uniqueness addToIndex(item, -1); } rv = super.addAll(idx, c); } finally { reindex(); } return rv; } @Override public boolean removeAll(Collection<?> c) { boolean rv; try { rv = super.removeAll(c); } finally { reindex(); } return rv; } @Override public boolean retainAll(Collection<?> c) { boolean rv; try { rv = super.retainAll(c); } finally { reindex(); } return rv; } @Override public boolean removeIf(Predicate<? super E> filter) { boolean rv; try { rv = super.removeIf(filter); } finally { reindex(); } return rv; } @Override public void replaceAll(final UnaryOperator<E> operator) { indexMap.clear(); try { int duplicates = 0; for (int i = 0; i < size(); i++) { E newval = requireNonNull(operator.apply(this.get(i))); if(indexMap.putIfAbsent(newval, i-duplicates) == null) { super.set(i-duplicates, newval); } else { duplicates++; } } removeRange(size()-duplicates, size()); } catch (Exception ex) { // If there's an exception the indexMap will be inconsistent reindex(); throw ex; } } @Override public void sort(Comparator<? super E> c) { try { super.sort(c); } finally { reindex(); } } }