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

data-structures java

2022-09-01 23:47:01

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

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

优先级队列：慢速更新（删除（对象）+ 添加（对象））和基元键的装箱
斐波那契堆：内存浪费（？
TreeMap<Field_S， List<Value>>：对我来说，问题是列表的内存开销，以及原始键的装箱
排序列表或数组：问题是插入和删除速度慢 ->我应该实现一个分段排序列表吗？
来自番石榴的树多头（文档）：外部依赖性，可能内存效率低下（？

有人有更好的建议吗？或者我应该扮演我自己的排序数据结构（哪一个？）？其他来源（在Java中，开源，带有单元测试和小dps）也会很好。

更新

目前有关我的用例的更多详细信息（尽管我上次有类似的需求）。我有一个集合（有数百万）参考资料，我希望能够

轮询或获取有关字段 S 的最小元素
并在字段 A 的帮助下更新字段 S
可能会发生字段 S 的相同值。字段 A 实际上是指向另一个数组的整数
我唯一想要的依赖关系是trove4j。如果需要，我可以使用不同的驯象师集合。但不是番石榴，因为虽然一个不错的lib，但收藏品没有被调整为内存效率（拳击/拆箱）。

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

答案 1

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

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

答案 2

番石榴树多呢？您要求的：接受重复项的已排序集合。虽然对它的性能一无所知。