Multi key, связанный хеш

Question

У меня есть набор элементов с двумя свойствами: имя (строка, не уникальная) и идентификатор (целое число, уникальное). Все элементы с одинаковыми именами хранятся вместе, сортируются по некоторым критериям.

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

Производительность - главное требование к структуре данных. Я думал, что многопользовательская, связанная структура данных или смешанный hashmap / стек будут идеальными, но я знаю, что нет. Некоторые варианты, которые я рассмотрел, следующие: - Таблицы Guava (несколько клавиш), но они не имеют поведения push/pop. - LinkedHashMaps, но у них только один ключ.

Конечно, я могу использовать LinkedHasMaps и выполнять итерацию для удаления в тех случаях, когда мне нужно удалить элемент на основе идентификатора. Я просто хочу знать, есть ли что-то уже реализованное с высокой производительностью.

Какие-либо предложения?

Спасибо всем

Answer 1

Использовать Map<String, TreeSet<Integer>>, Это позволит вам хранить несколько элементов под одним ключом и сохранять целочисленные значения отсортированными.

---

Идея состоит в том, что у вас есть единая ключевая карта для структуры данных, которая может содержать несколько значений. Чтобы вставить name, value пара, вы можете сделать что-то вроде:

private Map<String, TreeSet<Integer>> map = new HashMap<>();

public void insert(String name, int value)
{
    if (! map.containsKey(name))
    {
        map.put(name, new TreeSet<Integer>());
    }
    map.get(name).add(value);
}

---

LinkedHashMap просто отслеживает порядок вставки ключей и выполняет итерацию в этом порядке - это не улучшит производительность по сравнению с использованием HashMap,