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

[Anonymous]

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

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

ListverseKeys = new ArrayList(keys); Collections.reverse(reverseKeys); что становится очень затратным при использовании больших наборов ключей (как упоминалось здесь: Итерация по LinkedHashMap в обратном порядке).

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

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

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