Java：排序集合允许重复，具有内存效率并提供快速插入和更新

具体来说，我需要一个集合，它使用一个字段A进行访问，使用另一个字段（字段S）进行排序，但是接受重复的已排序集合就足够了。

我经常到这一点，我需要这个集合，TreeMap不是一个选项，因为它不允许重复。 所以现在是时候问这里了。 stackoverflow 在这里和这里指出了几种解决方法 – 即：

• PriorityQueue ：缓慢更新（删除（对象）+添加（对象））和原始键的装箱
• 斐波纳契堆 ：内存浪费（？）
• TreeMap<Field_S, List> ：对我来说问题是列表的内存开销和原始键的装箱
• 排序列表或数组 ：问题是慢插入和删除 – >我应该实现一个分段排序列表？
• 来自guava（ docs ）的TreeMultimap ：外部依赖和可能内存效率低下（？）

谁有更好的建议？ 或者我应该扮演自己的排序数据结构（哪一个？）？ 其他来源（Java，开源，unit testing和小deps）也不错。

---

更新

目前关于我的用例的更多细节（虽然我上次有类似的需求）。 我有一个集合（有数百万）我想要的参考

• 轮询或获得关于字段S的最小元素
• 并在字段A的帮助下更新字段S.
• 字段S的相同值可以发生。 字段A实际上是指向另一个数组的整数
• 我想要的唯一依赖是trove4j。 如果需要，我可以使用不同的mahout集合。 但不是番石榴，因为虽然是一个很好的lib，但是这些集合并没有被调整为内存效率（装箱/拆箱）。

所以对于斐波那契堆的所有呼喊，但我担心每个元素的开销太多 – >这就是我考虑更高效的“排序+分段数组”解决方案的原因。

Answer 1

当您需要分类收集时，您应该仔细分析您的需求。
如果大多数操作是插入的 ，只有少数是要搜索然后使用已排序的集合，即保持元素在集合中不断排序，这将不是一个好的选择（由于保持元素在插入上排序的开销，这将是最常见的操作）。
在这种情况下，最好保留未分类的集合，并仅在需要时进行排序。 即在搜索之前。 你甚至可以使用一个简单的List并在需要时对它进行排序（使用Collections.sort即mergesort）。 但我谨慎地推荐这一点，因为这是有效的假设是你在处理大数据。 在非常小的数据中，甚至线性搜索也足够好。

如果大多数操作都在搜索，那么你可以使用一个排序的集合，从我的角度来看，有一些数据结构可供选择（你已经提到过），你可以通过基准测试来查看哪一个符合你的需求。

Answer 2

guava TreeMultiset怎么样 ？ 你要的是：一个接受重复的排序集合。 但是对它的表现一无所知。

Answer 3

您需要决定是否需要外部依赖项。 我不会为这样的事情推出自己的实现。

也就是说，你几乎没有告诉我们你使用它的原因，以及你打算用它做什么。 如果没有足够的数据，我们可以告诉您这么多 – 您是否真的需要以随机顺序访问元素？ 你对这个系列的期望有多大？ 我们实际上没有足够的数据来根据您的需求选择合适的数据结构。

也就是说，这里有一些我会考虑的选择。

• ArrayList或PriorityQueue ，具体取决于您是否确实需要支持remove(Object) 。 你做？ 你确定吗？ （即使您确实需要支持remove(Object) ，如果集合可能保持较小，我会选择此选项。）
• 不是您链接到的TreeList ，而是Apache Commons Collections TreeList 。 尽管名称，它实际上并没有维护排序顺序，但它的作用是支持O（log n）添加，删除和从列表中的任何位置获取。 使用二进制搜索，您可以根据值的排序部分实现添加，删除或查找的O（（log n）^ 2）时间。
• 你链接到的TreeList ，或者 – 如果你像我一样，关心List契约 – 一个自定义的Guava ListMultimap ，用Multimaps.newListMultimap(new TreeMap>, new Supplier>() { public List get() { return new ArrayList(); }})获得Multimaps.newListMultimap(new TreeMap>, new Supplier>() { public List get() { return new ArrayList(); }}) 。

如果你也关心原始拳击，或者不能容忍第三方依赖，你将别无选择，只能编写自己的数据结构。 我只是将上面的一个实现调整为你的原始类型，但这将是一个皇家的痛苦。

最后：我真的很想听听你的用例。 Guava对这样的事情没有任何支持，因为我们没有足够的需求，或者看到一个更复杂的数据结构非常合适的用例。

Answer 4

我决定推出自己的但不是最佳解决方案只是一个TreeMap变体。 如果我对这个有关内存的集合进行微调，我会保持更新。 速度已经比之前的PriorityQueue尝试要好得多，因为我需要collection.remove（Object）方法（用于更新条目）：

 package com.graphhopper.coll; import gnu.trove.iterator.TIntIterator; import gnu.trove.set.hash.TIntHashSet; import java.util.Map.Entry; import java.util.TreeMap; /** * A priority queue implemented by a treemap to allow fast key update. Or should we use a standard * b-tree? */ public class MySortedCollection { private int size; private int slidingMeanValue = 20; private TreeMap map; public MySortedCollection(int size) { map = new TreeMap(); } void remove(int key, int value) { TIntHashSet set = map.get(value); if (set == null || !set.remove(key)) throw new IllegalStateException("cannot remove key " + key + " with value " + value + " - did you insert " + key + "," + value + " before?"); size--; if (set.isEmpty()) map.remove(value); } public void update(int key, int oldValue, int value) { remove(key, oldValue); insert(key, value); } public void insert(int key, int value) { TIntHashSet set = map.get(value); if (set == null) map.put(value, set = new TIntHashSet(slidingMeanValue)); // else // slidingMeanValue = Math.max(5, (slidingMeanValue + set.size()) / 2); if (!set.add(key)) throw new IllegalStateException("use update if you want to update " + key); size++; } public int peekValue() { if (size == 0) throw new IllegalStateException("collection is already empty!?"); Entry e = map.firstEntry(); if (e.getValue().isEmpty()) throw new IllegalStateException("internal set is already empty!?"); return map.firstEntry().getKey(); } public int peekKey() { if (size == 0) throw new IllegalStateException("collection is already empty!?"); TIntHashSet set = map.firstEntry().getValue(); if (set.isEmpty()) throw new IllegalStateException("internal set is already empty!?"); return set.iterator().next(); } public int pollKey() { size--; if (size < 0) throw new IllegalStateException("collection is already empty!?"); Entry e = map.firstEntry(); TIntHashSet set = e.getValue(); TIntIterator iter = set.iterator(); if (set.isEmpty()) throw new IllegalStateException("internal set is already empty!?"); int val = iter.next(); iter.remove(); if (set.isEmpty()) map.remove(e.getKey()); return val; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public int getSlidingMeanValue() { return slidingMeanValue; } @Override public String toString() { return "size " + size + " min=(" + peekKey() + "=>" + peekValue() + ")"; } } 

Answer 5

我会选择skiplist – 比树更有效的内存，允许重复，为插入和删除提供O（logn）。 您甚至可以实现索引的跳转列表，它将允许您具有索引访问权限，这是树很难获得的。

Answer 6

我对TreeMultimap有很好的经验http://guava-libraries.googlecode.com/svn/tags/release05/javadoc/com/google/common/collect/TreeMultimap.html