Сортированная карта с уникальными ключами

Какую структуру использовать, когда нужно

  • упорядочение элементов с помощью ключа

  • способность удерживать не уникальные ключи

    Structure<Integer, String> struct = new Structure<Integer, String>;
struct.add(3,"...");
struct.add(1,"John");
struct.add(2,"Edwin");
struct.add(1,"Mary");
struct.toString() == {key-> value;} [1->"John",1->"Mary",2->"Edwin",3->"..."]

Ответы

Ответ 1

Если вы хотите использовать стандартный Java API, я бы выбрал TreeMap<Integer, Set<String>>.

  • Элементы упорядочиваются клавишами, так как это SortedMap. Из документов:

    Карта упорядочена в соответствии с естественным порядком ее ключей или компаратором, обычно предоставляемым на время сортировки карты. Этот порядок отражается при повторении сортированных видов коллекции карт (возвращаемых методами entrySet, keySet и значений).

  • Структура позволяет использовать не-уникальные ключи, поскольку вы можете позволить одной ключевой карте нескольким объектам.

Этот тип структуры называется отсортированным мульти-картой, и есть несколько реализаций, которые скрывают детали создания начальных наборов при вставке в первый раз и т.д. Посмотрите Guava или Apache Commons, например.

В зависимости от ваших потребностей вы также можете иметь SortedSet<Pair<Integer, String>>, где элементы сортируются по левому элементу в паре. (Обратите внимание, что вы сами должны были бы написать класс Pair, но это должно быть не более нескольких строк.)

Ответ 2

Похоже, вам понадобится Map<Integer, List<String>>, чтобы каждый ключ сопоставлялся с списком (или другой коллекцией) строк.

Apache Commons имеет MultiMap, который делает это без лишних хлопот, кодирующих его.

 MultiMap mhm = new MultiHashMap();
 mhm.put(key, "A");
 mhm.put(key, "B");
 mhm.put(key, "C");
 Collection coll = (Collection) mhm.get(key);

coll будет сборником, содержащим "A", "B", "C".

Google Collections предоставит что-то подобное, я подозреваю.

Ответ 3

Помимо использования реализаций multimap от Apache Commons или Guava или реализации класса Pair, как предложено другими ответами, вы можете просто использовать TreeMap<Integer,List<String>>. Вместо сопоставления клавиш с одним String он теперь сопоставляется с List, который может содержать несколько значений и, таким образом, эффективно работать, как мультимап.

Но я бы пошел с надлежащим multimap для производственного кода.