Эффективно упорядоченная структура данных, поддерживающая дубликаты ключей

Question

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

Структура данных должна позволять дублировать ключи, поскольку конкретное значение пригодности может встречаться вразные люди.Это проблема, потому что, например, структура данных TreeMap не позволяет дублировать ключи.Я бы предпочел использовать этот тип древовидной структуры из-за ее эффективности O (log N).

Если бы я вставил людей в упорядоченный список, эффективность упала бы до O (n), и сортировкалюди после того, как они были вставлены, также не будут очень эффективными.

Существует ли эффективная структура данных, позволяющая упорядочивать отдельных лиц и поддерживающая дубликаты ключей?

Я буду добавлять и удалять записи очень часто после создания структуры данных, поэтому сортировкаобъекты после создания структуры будут очень дорогими.

Answer 1

Оба Apache Commons и Гуава поддерживают мультикарты, которые вам нужны.

В качестве альтернативы, в зависимости от вашего варианта использования, вы можете собрать элементы в ArrayList и затем отсортировать их в O ( n lg n ) общего времени.

Или вы можете определить сравнение, которое сначала проверяет пригодность и другие отличительные свойства предметов, если пригодность сравнивается равным.

Answer 2

В классической информатике искомая структура данных называется Priority Queue .

Так получилось, что начиная с java 1.5 стандартная библиотека классов java имеет реализацию: java.util.PriorityQueue .

Я бы использовал его.

Answer 3

Если вы хотите использовать обычный TreeMap, вы можете сделать так, чтобы он хранил упаковщики значений вместо самих значений.Эти обертки будут хранить несколько с одним и тем же ключом.

В противном случае вы можете использовать некую сортированную структуру списка, основанную на двоичном дереве поиска.Недавно я написал одно, которое доступно здесь: http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/, но я уверен, что существует больше стандартных реализаций.Преимущество такого рода структуры заключается в том, что метод contains(Object) выполняется в логарифмическом, а не линейном времени.

Answer 4

Если вы заботитесь о заказе только после того, как все люди были добавлены, и не добавляете никаких новых людей после этого, сортировка ArrayList, вероятно, является самым быстрым вариантом.

Иначе, вы можете использоватьTreeSet, и иметь компаратор, который сравнивает сначала по пригодности, а затем по хэш-коду идентичности , если пригодность равна (или по любому другому отличному свойству).Таким образом, все ваши объекты будут разными, но они будут отсортированы по пригодности.