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

Карта Java с ключами без учета регистра

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

Задача: Сумма двух чисел

Напишите функцию twoSum. Которая получает массив целых чисел nums и целую сумму target, а возвращает индексы двух чисел, сумма которых равна target. Любой набор входных данных имеет ровно одно решение, и вы не можете использовать один и тот же элемент дважды. Ответ можно возвращать в любом порядке...

ANDROMEDA

1. Обзор

Карта — одна из наиболее распространенных структур данных в Java, а String — один из наиболее распространенных типов ключа карты. По умолчанию карта такого типа имеет ключи с учетом регистра.

В этом кратком руководстве мы рассмотрим различные реализации Map , которые принимают все варианты регистра String как один и тот же ключ .

2. Пристальный взгляд на карту с ключами без учета регистра

Давайте рассмотрим проблему, которую мы пытаемся решить, более подробно.

Предположим, у нас есть Map<String, Integer> с одной записью:

./12b54750f8674a2a9e4350b2cefcde59.png

Добавим следующую запись:

map.put("ABC", 2);

При работе с Map с ключами, чувствительными к регистру, мы получим две записи:

./591b1a6610c94c9e5f656a1756124408.png

Но при работе с Map с ключами без учета регистра содержимое будет таким:

./99366eac34880d05e8a10e12bc7625bf.png

В следующих примерах мы рассмотрим нечувствительные к регистру реализации некоторых популярных реализаций Map : TreeMap , HashMap и LinkedHashMap .

3. Древовидная карта

TreeMap — это реализация NavigableMap , что означает, что он всегда сортирует записи после вставки на основе заданного Comparator . Кроме того, TreeMap использует компаратор , чтобы определить, является ли вставленный ключ дубликатом или новым.

Следовательно, если мы предоставим нечувствительный к регистру String Comparator , мы получим нечувствительный к регистру TreeMap .

К счастью, String уже предоставляет этот статический компаратор :

public static final Comparator <String> CASE_INSENSITIVE_ORDER

который мы можем предоставить в конструкторе:

Map<String, Integer> treeMap = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
treeMap.put("abc", 1);
treeMap.put("ABC", 2);

И теперь, когда мы запускаем тесты, мы видим, что размер карты равен единице:

assertEquals(1, treeMap.size());

и значение обновляется до 2:

assertEquals(2, treeMap.get("aBc").intValue());
assertEquals(2, treeMap.get("ABc").intValue());

Теперь удалим запись, используя тот же String , но с другим регистром:

treeMap.remove("aBC");
assertEquals(0, treeMap.size());

Мы должны иметь в виду, что такие функции, как put и get , стоят в среднем O(log n) для TreeMap по сравнению с HashMap , который обеспечивает вставку и поиск O(1).

Также стоит отметить, что TreeMap не допускает нулевых ключей.

4. CaseInsensitiveMap Apache

Apache Commons-Collections — очень популярная библиотека Java, предоставляющая большое количество полезных классов , среди которых есть CaseInsensitiveMap .

CaseInsensitiveMap — это карта на основе хэша `` , которая преобразует ключи в нижний регистр перед их добавлением или извлечением. В отличие от TreeMap , CaseInsensitiveMap допускает вставку нулевого ключа.

Во- первых, нам нужно добавить зависимость commons -collections4 :

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

Теперь мы можем использовать CaseInsensitiveMap и добавить две записи:

Map<String, Integer> commonsHashMap = new CaseInsensitiveMap<>();
commonsHashMap.put("abc", 1);
commonsHashMap.put("ABC", 2);

Когда мы тестируем его, мы ожидаем тех же результатов, что и ранее:

assertEquals(1, commonsHashMap.size());
assertEquals(2, commonsHashMap.get("aBc").intValue());
assertEquals(2, commonsHashMap.get("ABc").intValue());

commonsHashMap.remove("aBC");
assertEquals(0, commonsHashMap.size());

5. Spring LinkedCaseInsensitiveMap

Spring Core — это модуль Spring Framework, который также предоставляет служебные классы, в том числе LinkedCaseInsensitiveMap .

LinkedCaseInsensitiveMap является оболочкой LinkedHashMap , которая представляет собой карту на основе хэш-таблицы и связанного списка. В отличие от LinkedHashMap , он не позволяет вставлять нулевой ключ. LinkedCaseInsensitiveMap сохраняет исходный порядок, а также исходный регистр ключей, позволяя вызывать такие функции, как получение и удаление с любым регистром.

Во-первых, давайте добавим зависимость spring -core :

<dependency>
<groupId>org.springframework</groupId>
<artifactId>spring-core</artifactId>
<version>5.2.5.RELEASE</version>
</dependency>

Теперь мы можем инициализировать новую LinkedCaseInsensitiveMap :

Map<String, Integer> linkedHashMap = new LinkedCaseInsensitiveMap<>();
linkedHashMap.put("abc", 1);
linkedHashMap.put("ABC", 2);

добавить проверить это:

assertEquals(1, linkedHashMap.size());
assertEquals(2, linkedHashMap.get("aBc").intValue());
assertEquals(2, linkedHashMap.get("ABc").intValue());

linkedHashMap.remove("aBC");
assertEquals(0, linkedHashMap.size());

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

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

Как всегда, код доступен на GitHub .