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

Question

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

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

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

谁有更好的建议？或者我应该扮演我自己的排序数据结构(哪一个？)？其他来源(Java、开源、带有单元测试和小型 deps)也会很好。

---

更新

目前有关我的用例的更多详细信息(尽管我上次也有类似的需求)。我有一个集合(数百万)我希望能够使用的引用文献

• 轮询或获取有关字段 S 的最小元素
• 并在字段 A 的帮助下更新字段 S
• 可能会出现字段 S 的相同值。字段 A 实际上是一个指向另一个数组的整数
• 我想要的唯一依赖项是 trove4j。如果需要，我可以使用不同的 mahout 集合。但不是 Guava ，因为虽然是一个不错的库，但集合并没有调整为内存效率(装箱/拆箱)。

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

Answer 1

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

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