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

Question

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

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

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

谁有更好的建议？或者我应该对自己的排序数据结构(哪一个？)起作用？其他来源(Java,开源,单元测试和小deps)也不错.

---

更新

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

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

所以对于斐波那契堆的所有呼声,但我担心它每个元素的开销太多 - >这就是我考虑更高效的"排序+分段数组"解决方案的原因.

Answer 1

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

如果大多数操作是搜索，那么您可以使用排序集合，从我的角度来看，有可供选择的数据结构（您已经提到了一些），并且您可以进行基准测试以查看哪个适合您的需求。

Answer 2

我决定推出自己的解决方案，但不是最佳解决方案，只是 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<Integer, TIntHashSet> map;

    public MySortedCollection(int size) {
        map = new TreeMap<Integer, TIntHashSet>();
    }

    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<Integer, TIntHashSet> 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<Integer, TIntHashSet> 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() + ")";
    }
}