В частности, мне нужна коллекция, которая использует одно поле A для доступа и другое (поле S) для сортировки, но отсортированной коллекции, которая принимает дубликаты, было бы достаточно.

Я часто прихожу к тому моменту, когда мне нужна именно эта коллекция, а TreeMap не является опцией, так как не допускает дублирование. Так что теперь пришло время спросить здесь. Есть несколько обходных путей, как указано на stackoverflowВот а такжеВот - а именно:

PriorityQueue: slow update (remove(Object) + add(Object)), and boxing of primitive keys Fibonacci heap: memory waste (?) TreeMap<Field_S, List<Value>>: problem for me is the memory overhead of the list, and boxing of primitive keys sorted list or array: problem is the slow insert and remove -> should I implement one segmented sorted list? TreeMultimap from guava (docs): external dependency and probably memory inefficient (?)

Кто-нибудь с лучшими предложениями? Или я должен сыграть свою собственную отсортированную структуру данных (какую?)? Также были бы хороши другие источники (в Java, с открытым исходным кодом, с юнит-тестами и небольшими приложениями).

Update

Более подробная информация о моем случае использования на данный момент (хотя у меня аналогичный спрос в последний раз). У меня есть коллекция (с миллионами) ссылок, где я хочу иметь возможность

to poll or get the smallest element regarding field S and update field S with the help of field A identical values of field S can happen. field A is actually a integer pointing into another array the only dependency I want is trove4j. I could use a different like the mahout collections if that would be required. But not guava as although a nice lib the collections are not tuned to be memory efficient (boxing/unboxing).

Таким образом, все кричат о куче Фибоначчи, но я боюсь, что она имеет слишком много накладных расходов на элемент - & gt; По этой причине я подумал о более эффективном по памяти «отсортированном + сегментированном массиве». решение.