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

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

我经常来到这里，我确实需要这个集合，TreeMap不是一个选择，因为它不允许重复。所以现在是时候在这里问了。在stackoverflow here和here上指出了几种解决方法-即:

PriorityQueue :缓慢更新(删除(对象)+添加(对象))，以及对原始键

进行装箱

斐波那契堆:内存浪费(？)

TreeMap<Field_S, List<Value>> :对我来说，问题是列表的内存开销以及原始键

的装箱

排序列表或数组:问题是插入和删除速度很慢->我应该实现一个分段的排序列表吗？

Guava 中的

TreeMultimap(docs):外部依赖关系，可能是内存效率低下(？)

有人有更好的建议吗？还是应该扮演我自己的排序数据结构(哪个？)？另外，其他资源(在Java，开放源代码，单元测试和小型部门中)也不错。

更新

目前有关我的用例的更多细节(尽管上次我有类似的需求)。我希望能够收集(数百万个)引用文献

来轮询或获取关于字段S的最小元素

并借助字段A

更新字段S

字段S的值可能相同。字段A实际上是指向另一个数组

的整数

我想要的唯一依赖是trove4j。如果需要的话，我可以使用其他类似mahout的集合。但不是 Guava ，因为尽管一个不错的库，但集合并未调整为具有内存效率(装箱/拆箱)。

因此，所有人都为斐波那契堆哭泣，但我担心每个元素的开销都太大->这就是我考虑使用内存效率更高的“排序+分段数组”解决方案的原因。

最佳答案

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

如果大多数操作都在搜索中，那么您可以使用排序后的集合，从我的角度来看，有一些数据结构可供选择(您已经提到过)，并且可以进行基准测试以查看哪种数据结构满足您的需求。