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

Question

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

我经常需要这个集合，而TreeMap不是一个选项，因为它不允许重复。所以现在是时候问这里了。正如在这里和这里的stackoverflow中指出的，有几个变通方法，即：

• PriorityQueue：缓慢更新（删除（对象）添加（对象）），基本键装箱
• 斐波那契堆：内存浪费（？）
• TreeMap

有人有更好的建议吗？或者我应该扮演我自己的分类数据结构（哪一个？）？另外，其他源代码（Java、开源、单元测试和小型DEP）也不错。

使现代化

目前关于我的用例的更多细节（尽管我上次也有类似的需求）。我有一个收藏（数以百万计）的参考资料，我希望能够

• 轮询或获取关于字段S的最小元素
• 并借助字段A更新字段S
• 字段S的相同值可能发生。字段A实际上是指向另一个数组的整数
• 我想要的唯一依赖是trove4j。如果需要的话，我可以使用不同的像驯象师的收藏品。但不是番石榴，因为尽管是一个不错的库，但这些集合并没有被调整为内存效率（装箱/取消装箱）。

因此，所有人都要求使用斐波那契堆，但我担心每个元素的开销太大-




Answer 1

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

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

Answer 2

番石榴呢？你想要的是：一个接受重复项的分类集合。但我对它的性能一无所知。

Answer 3

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

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