有序集在 Java 中的实现吗？

小开

Treeset 是一个有序的集合，但是您不能通过条目索引访问，只能遍历或者访问 start/end。

小开

每个集合都有一个迭代器()。普通 HashSet 的迭代器是相当随机的，TreeSet 是按照排序顺序进行迭代的，LinkedHashSet迭代器是按照插入顺序进行迭代的。

但是，您不能替换 LinkedHashSet 中的元素。您可以删除一个元素并添加另一个元素，但是新元素将不会位于原始元素的位置。在 LinkedHashMap 中，可以替换现有键的值，然后这些值仍然保持原始顺序。

而且，你不能插入到某个特定的位置。

也许您最好使用带有显式检查的 ArrayList 来避免插入重复项。

小开

TreeSet已下令。

Http://docs.oracle.com/javase/6/docs/api/java/util/treeset.html

小开

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

引用医生的话:

元素使用它们的自然顺序进行排序，或者使用在设定创建时提供的比较器进行排序，这取决于使用哪个构造函数

请注意，add、 delete 和 include 有一个时间成本日志(n)。

如果你想以 Array 的形式访问集合的内容，你可以这样做:

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

这个数组将使用与 TreeSet 相同的条件进行排序(自然排序或比较器排序) ，在许多情况下，这样做比使用 Arrays.sort ()更有优势

小开

看看 Java 标准 API 文档。就在 LinkedHashMap旁边，有一个 LinkedHashSet。但是请注意，这些元素的顺序是插入顺序，而不是元素的自然顺序。而且您只能按照这个顺序迭代，不能进行随机访问(除非通过计算迭代步骤)。

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

对于一个既可以高效地通过索引访问又可以高效地实现集合标准的数据结构，您需要一个跳过清单，但是在 Java Standard API 中没有具备这种功能的实现，尽管我确信在互联网上很容易找到一个。

小开

最佳答案

看看 LinkedHashSet课程

来自 Java 文档 :

Set 接口的哈希表和链表实现，具有可预测的 迭代次序。此实现与 HashSet 的不同之处在于，它维护一个贯穿其所有条目的双链表。这个链表定义了迭代顺序 这是元素插入集合的顺序(插入顺序)。注意，如果将元素重新插入到集合中，则插入顺序不受影响.(如果 s.add (e)被调用，则 e 元素将重新插入集合 s 中，而 s.include (e)将在调用之前立即返回 true。).

小开

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

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

我的意思是它总是陷入整个数组的创建中，所以它是 O (n) :

java.util.Arrays#copyOf

小开

来自索引树状图索引树状图索引树状图项目的 IndexedTreeSet 提供了这种功能(按索引进行排序/排序，并具有列表式访问)。

小开

您还可以从双向映射(如谷歌番石榴的 BiMap)中获得一些实用工具

使用 BiMap，您可以非常有效地将 Integer (用于随机索引访问)映射到任何其他对象类型。BiMap是一对一的，所以任何给定的整数最多只有一个相关的元素，而任何元素都有一个相关的整数。它巧妙地由两个 HashTable实例支撑，所以它使用了几乎两倍的内存，但是它在处理方面比定制的 List要高效得多，因为 contains()(当添加一个项目以检查它是否已经存在时调用它)是一个常量时间和并行友好的操作，就像 HashSet一样，而 List的实现要慢得多。

小开

我也有过类似的问题。我不太需要一个有序集，但更多的是一个快速 indexOf/contains列表。因为我在那里什么也没找到，所以我自己实施了一个。下面是代码，它同时实现了 Set和 List，尽管并非所有批量列表操作都像 ArrayList版本那样快。

免责声明: 未经测试

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

小开

我自己的 MapTreeAVL(其实现位于该接口旁边的 mtAvl包之下)既提供了获取 SortedSet的方法，也提供了基于索引的访问方法(在这种情况下，一些所谓的 Optimizations，如 MinMaxIndexIteration，可能是首选的)。

(注意: 因为我的 repo 是打开的，所以你可以直接下载所需要的文件，但是我建议你检查同一个超级包 dataStructure中的其他类是否需要/使用/导入)