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

Question

Какая структура данных из коллекций может эффективно хранить сопоставления ключ-значение, сохранять порядок вставки и обеспечивать эффективный обратный обход? Структура данных должна исходить из исходных коллекций Java, поэтому об использовании библиотеки Apache Commons не может быть и речи.

В настоящее время я использую LinkedHashMap, который является идеальным, потому что он сохраняет порядок вставки, позволяет сопоставления значения ключа и имеет методы add() и remove(), которые работают за время O(1). Проблема, однако, заключается в том, что для обращения к LinkedHashMap мне нужно выполнять копирование набора при каждом добавлении нового ключа:

List<Integer> reverseKeys = new ArrayList<>(keys);
Collections.reverse(reverseKeys);

который становится очень дорогостоящим для больших наборов ключей (как было упомянуто здесь: перебор LinkedHashMap в обратном порядке).

В качестве альтернативы, я мог бы использовать TreeMap с пользовательским компаратором для сохранения порядка вставки, но это кажется пустой тратой, потому что add() и remove() будут выполняться за O(n) времени. Преимущество этого подхода заключается в том, что TreeMap имеет метод downndingKeySet(), который обеспечивает эффективный обратный обход.

Моя единственная другая мысль - использовать ArrayList объектов Entry, однако я не уверен, насколько это эффективно.

Какой из этих подходов лучше всего подойдет для нескольких тысяч сопоставлений ключ-значение? Есть ли какие-то подходы, которые я не перечислил, которые были бы лучшей альтернативой?

Answer 1

У вас должна быть только одна переменная? Распространенным подходом является многократное использование одних и тех же данных в разных структурах, если вы хотите часто их запрашивать.

Добавление / удаление стоит дороже, однако выбор может стоить намного дешевле.

В вашем случае вы можете иметь LinkedList в обратном порядке (добавление в нулевой позиции - O(1)) и LinkedHashMap.

В идеале вы должны создать свой собственный класс с этими двумя переменными и методами, такими как "добавить / удалить и т. Д.", Чтобы убедиться, что он согласован.