Java эквивалент C ++ std :: map?

Question

Я ищу класс Java с характеристиками обычной реализации C ++ std :: map (насколько я понимаю, самобалансирующееся двоичное дерево поиска):

1. O (log n) производительность для вставки / удаления / поиска
2. Каждый элемент состоит из уникального ключа и сопоставленного значения
3. Ключи следуют строгому слабому порядку

Я ищу реализации с открытым исходным кодом или проектные документы; Я, вероятно, в итоге откажусь от своей собственной поддержки примитивных ключей / значений.

Стиль этого вопроса похож на: Java-эквивалент std :: deque , ответ которого был "ArrayDeque из Примитивных коллекций для Java".

Answer 1

ConcurrentSkipListMap - это отсортированная карта, подкрепленная пропущенным списком (самобалансирующаяся древовидная структура с производительностью O (log n)). Как правило, границы в CSLM более жесткие, чем TreeMap (который является самобалансирующимся красно-черным деревом), поэтому он, вероятно, будет работать лучше, с дополнительным преимуществом - поточно-ориентированным и параллельным, а TreeMap - нет. CSLM был добавлен в JDK 1.6.

Trove содержит набор коллекций для примитивных типов и некоторые другие интересные варианты общих типов коллекций Java.

Другие библиотеки коллекций, представляющие интерес, включают Библиотеки Google Collection и Apache Commons Collections .

Answer 2

Ближайшим классом к двоичному дереву в стандартных библиотеках Java является java.util.TreeMap, но он не поддерживает примитивные типы, за исключением упаковок (например, int упаковывается как Integer, double как Double и т. Д.).

java.util.HashMap, вероятно, даст лучшую производительность для больших карт. Теоретически это O (1), но его точные характеристики производительности зависят от алгоритма (ов) генерации хеш-кода для ключевого класса (классов).

Согласно Введение в коллекции : «Массивы ... являются единственной коллекцией, которая поддерживает хранение примитивных типов данных.»

Answer 3

Вы также можете взглянуть на общие коллекции FastTreeMap.

Я сомневаюсь, что вы найдете много коллекций, которые поддерживают примитивные типы без бокса, так что просто живите с этим. И это не обязательно нужно, потому что autoboxing .

Если вы действительно хотите использовать примитив (после выполнения тестов, которые показывают недостаточную производительность!), Вы можете увидеть источник FastTreeMap и добавить методы для обработки примитивов.