Перейти к основному содержимому

Как сохранить повторяющиеся ключи на карте в Java?

· 4 мин. чтения

Задача: Сумма двух

Дано массив целых чисел и целая сумма. Нужно найти индексы двух чисел, сумма которых равна заданной ...

ANDROMEDA

1. Обзор​

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

2. Стандартные карты​

В Java есть несколько реализаций интерфейса Map , каждая из которых имеет свои особенности.

Однако ни одна из существующих реализаций Map ядра Java не позволяет Map обрабатывать несколько значений для одного ключа .

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

Он также будет возвращен (при каждой правильной реализации метода put(K key, V value) ):

Map<String, String> map = new HashMap<>();
assertThat(map.put("key1", "value1")).isEqualTo(null);
assertThat(map.put("key1", "value2")).isEqualTo("value1");
assertThat(map.get("key1")).isEqualTo("value2");

Как тогда мы можем добиться желаемого поведения?

3. Коллекция как ценность​

Очевидно, что использование коллекции для каждого значения нашей карты сделает эту работу:

Map<String, List<String>> map = new HashMap<>();
List<String> list = new ArrayList<>();
map.put("key1", list);
map.get("key1").add("value1");
map.get("key1").add("value2");
 
assertThat(map.get("key1").get(0)).isEqualTo("value1");
assertThat(map.get("key1").get(1)).isEqualTo("value2");

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

В Java 8 мы могли бы использовать методы calculate() и улучшить их:

Map<String, List<String>> map = new HashMap<>();
map.computeIfAbsent("key1", k -> new ArrayList<>()).add("value1");
map.computeIfAbsent("key1", k -> new ArrayList<>()).add("value2");

assertThat(map.get("key1").get(0)).isEqualTo("value1");
assertThat(map.get("key1").get(1)).isEqualTo("value2");

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

В противном случае, прежде чем писать собственную реализацию карты и изобретать колесо, нам следует выбрать один из нескольких вариантов, доступных «из коробки».

4. Коллекции Apache Commons​

Как обычно, у Apache есть решение нашей проблемы.

Начнем с импорта последней версии Common Collections (далее CC):

<dependency>
  <groupId>org.apache.commons</groupId>
  <artifactId>commons-collections4</artifactId>
  <version>4.1</version>
</dependency>

4.1. Мультикарта​

org.apache.commons.collections4 . Интерфейс MultiMap определяет карту, которая содержит набор значений для каждого ключа.

Он реализован org.apache.commons.collections4.map. Класс MultiValueMap , который автоматически обрабатывает большую часть шаблонного кода:

MultiMap<String, String> map = new MultiValueMap<>();
map.put("key1", "value1");
map.put("key1", "value2");
assertThat((Collection<String>) map.get("key1"))
  .contains("value1", "value2");

Хотя этот класс доступен, начиная с версии CC 3.2, он не является потокобезопасным и объявлен устаревшим в версии CC 4.1 . Мы должны использовать его только тогда, когда мы не можем перейти на более новую версию.

4.2. Многозначная карта​

Преемником MultiMap является org.apache.commons.collections4. Интерфейс MultiValuedMap . Он имеет несколько реализаций, готовых к использованию.

Давайте посмотрим, как сохранить несколько значений в ArrayList , который сохраняет дубликаты:

MultiValuedMap<String, String> map = new ArrayListValuedHashMap<>();
map.put("key1", "value1");
map.put("key1", "value2");
map.put("key1", "value2");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value1", "value2", "value2");

В качестве альтернативы мы могли бы использовать HashSet , который отбрасывает дубликаты:

MultiValuedMap<String, String> map = new HashSetValuedHashMap<>();
map.put("key1", "value1");
map.put("key1", "value1");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value1");

Обе приведенные выше реализации не являются потокобезопасными .

Давайте посмотрим, как мы можем использовать декоратор UnmodifiedMultiValuedMap , чтобы сделать их неизменяемыми:

@Test(expected = UnsupportedOperationException.class)
public void givenUnmodifiableMultiValuedMap_whenInserting_thenThrowingException() {
    MultiValuedMap<String, String> map = new ArrayListValuedHashMap<>();
    map.put("key1", "value1");
    map.put("key1", "value2");
    MultiValuedMap<String, String> immutableMap =
      MultiMapUtils.unmodifiableMultiValuedMap(map);
    immutableMap.put("key1", "value3");
}

5. Мультикарта гуавы​

Guava — это основные библиотеки Google для Java API.

Начнем с импорта Guava в наш проект:

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>31.0.1-jre</version>
</dependency>

Guava с самого начала следовала пути многочисленных реализаций.

Наиболее распространенным является com.google.common.collect. ArrayListMultimap , который использует HashMap , поддерживаемый ArrayList , для каждого значения:

Multimap<String, String> map = ArrayListMultimap.create();
map.put("key1", "value2");
map.put("key1", "value1");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value2", "value1");

Как всегда, мы должны предпочесть неизменяемые реализации интерфейса Multimap: com.google.common.collect. ImmutableListMultimap и com.google.common.collect. Иммутаблесетмультимап .

5.1. Общие реализации карт​

Когда нам нужна конкретная реализация Map , первое, что нужно сделать, это проверить, существует ли она, потому что, вероятно, Guava уже реализовала ее.

Например, мы можем использовать com.google.common.collect. LinkedHashMultimap , который сохраняет порядок вставки ключей и значений:

Multimap<String, String> map = LinkedHashMultimap.create();
map.put("key1", "value3");
map.put("key1", "value1");
map.put("key1", "value2");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value3", "value1", "value2");

В качестве альтернативы мы можем использовать com.google.common.collect. TreeMultimap , который перебирает ключи и значения в их естественном порядке:

Multimap<String, String> map = TreeMultimap.create();
map.put("key1", "value3");
map.put("key1", "value1");
map.put("key1", "value2");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value1", "value2", "value3");

5.2. Создание нашей пользовательской MultiMap​

Доступны многие другие реализации.

Однако мы можем захотеть украсить Карту и/или Список , которые еще не реализованы.

К счастью, в Guava есть фабричный метод, позволяющий нам это сделать: Multimap.newMultimap() .

6. Заключение​

Мы увидели, как хранить несколько значений для ключа на карте всеми основными существующими способами.

Мы изучили самые популярные реализации Apache Commons Collections и Guava, которые по возможности следует предпочесть пользовательским решениям.

Как всегда, полный исходный код доступен на Github .