Java TreeMap против HashMap

1. Введение

В этой статье мы собираемся сравнить две реализации Map : TreeMap и HashMap .

Обе реализации составляют неотъемлемую часть Java Collections Framework и хранят данные в виде пар ключ-значение .

2. Отличия

2.1. Реализация

Сначала мы поговорим о HashMap , которая представляет собой реализацию на основе хеш-таблиц. Он расширяет класс AbstractMap и реализует интерфейс Map . HashMap работает по принципу хеширования .

Эта реализация Map обычно действует как хэш-таблица с сегментами , но когда сегменты становятся слишком большими, они преобразуются в узлы TreeNodes , каждый из которых структурирован аналогично узлам в java.util.TreeMap.

Вы можете узнать больше о внутренностях HashMap в статье, посвященной ему .

С другой стороны, TreeMap расширяет класс AbstractMap и реализует интерфейс NavigableMap . TreeMap хранит элементы карты в красно-черном дереве, которое является самобалансирующимся двоичным деревом поиска . ****

И вы также можете найти больше о внутренностях TreeMap в статье, посвященной этому здесь .

2.2. Заказ

HashMap не дает никаких гарантий относительно расположения элементов на карте .

Это означает, что мы не можем принимать какой-либо порядок при переборе ключей и значений HashMap :

@Test
public void whenInsertObjectsHashMap_thenRandomOrder() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(3, "TreeMap");
    hashmap.put(2, "vs");
    hashmap.put(1, "HashMap");
    
    assertThat(hashmap.keySet(), containsInAnyOrder(1, 2, 3));
}

Однако элементы в TreeMap сортируются в соответствии с их естественным порядком .

Если объекты TreeMap не могут быть отсортированы в соответствии с естественным порядком, мы можем использовать Comparator или Comparable , чтобы определить порядок, в котором элементы расположены на карте:

@Test
public void whenInsertObjectsTreeMap_thenNaturalOrder() {
    Map<Integer, String> treemap = new TreeMap<>();
    treemap.put(3, "TreeMap");
    treemap.put(2, "vs");
    treemap.put(1, "HashMap");
    
    assertThat(treemap.keySet(), contains(1, 2, 3));
}

2.3. Нулевые значения

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

Давайте посмотрим пример:

@Test
public void whenInsertNullInHashMap_thenInsertsNull() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(null, null);
    
    assertNull(hashmap.get(null));
}

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

Нулевой ключ не разрешен, потому что метод compareTo() или compare() создает исключение NullPointerException:

@Test(expected = NullPointerException.class)
public void whenInsertNullInTreeMap_thenException() {
    Map<Integer, String> treemap = new TreeMap<>();
    treemap.put(null, "NullPointerException");
}

Если мы используем TreeMap с определяемым пользователем Comparator , то способ обработки нулевых значений зависит от реализации метода compare () . ``

3. Анализ производительности

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

В этом разделе мы предоставим всесторонний анализ производительности для HashMap и TreeMap.

3.1. HashMap

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

HashMap обеспечивает ожидаемую производительность с постоянным временем O(1) для большинства операций, таких как add() , remove() и contains() . Следовательно, это значительно быстрее, чем TreeMap .

Среднее время поиска элемента при разумном предположении в хеш-таблице составляет O (1). Но неправильная реализация хеш-функции может привести к плохому распределению значений в сегментах, что приводит к:

• Накладные расходы памяти — многие сегменты остаются неиспользованными
• Ухудшение производительности — чем больше количество столкновений, тем ниже производительность.

До Java 8 раздельная цепочка была единственным предпочтительным способом обработки коллизий. Обычно это реализуется с использованием связанных списков, т . е. если есть какое-либо столкновение или два разных элемента имеют одинаковое хэш-значение, то сохраняйте оба элемента в одном и том же связанном списке.

Следовательно, поиск элемента в HashMap в худшем случае мог занять столько же времени, сколько поиск элемента в связанном списке, т.е. O(n) времени.

Однако с появлением JEP 180 произошли небольшие изменения в реализации способа расположения элементов в HashMap.

Согласно спецификации, когда сегменты становятся слишком большими и содержат достаточное количество узлов, они преобразуются в режимы TreeNodes , каждый из которых структурирован так же, как в TreeMap .

Следовательно, в случае коллизий с большим количеством хэшей производительность в наихудшем случае улучшится с O(n) до O(log n).

Код, выполняющий это преобразование, показан ниже:

if(binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);
}

Значение для TREEIFY_THRESHOLD равно восьми, что эффективно обозначает пороговое значение для использования дерева, а не связанного списка для корзины.

Очевидно, что:

• HashMap требует гораздо больше памяти, чем необходимо для хранения его данных .
• HashMap не должен быть заполнен более чем на 70–75%. Если он приближается, его размер изменяется, а записи перефразируются.
• Повторное хеширование требует n операций, что является дорогостоящим, при этом наша вставка с постоянным временем становится порядка O (n)
• Алгоритм хеширования определяет порядок вставки объектов в HashMap .

Производительность HashMap можно настроить, установив пользовательскую начальную емкость и коэффициент загрузки во время самого создания объекта HashMap .

Однако мы должны выбрать HashMap , если:

• мы примерно знаем, сколько предметов оставить в нашей коллекции
• мы не хотим извлекать элементы в естественном порядке

В описанных выше обстоятельствах HashMap — наш лучший выбор, поскольку он предлагает вставку, поиск и удаление с постоянным временем.

3.2. ДеревоКарта

TreeMap хранит свои данные в иерархическом дереве с возможностью сортировки элементов с помощью пользовательского компаратора.

Краткое изложение его производительности:

• TreeMap обеспечивает производительность O(log(n)) для большинства операций, таких как add() , remove() и contains() .
• Карта дерева может экономить память (по сравнению с HashMap) , потому что она использует только объем памяти, необходимый для хранения своих элементов, в отличие от HashMap , который использует непрерывную область памяти.
• Дерево должно поддерживать свой баланс, чтобы сохранить предполагаемую производительность, это требует значительных усилий и, следовательно, усложняет реализацию.

Мы должны использовать TreeMap всякий раз, когда:

• необходимо учитывать ограничения памяти
• мы не знаем, сколько элементов должно храниться в памяти
• мы хотим извлечь объекты в естественном порядке
• если элементы будут последовательно добавляться и удаляться
• мы готовы принять время поиска O(log n)

4. Сходства

4.1. Уникальные элементы

И TreeMap , и HashMap не поддерживают повторяющиеся ключи. Если он добавлен, он переопределяет предыдущий элемент (без ошибки или исключения):

@Test
public void givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique() {
    Map<Integer, String> treeMap = new HashMap<>();
    treeMap.put(1, "ForEach");
    treeMap.put(1, "ForEach");

    assertTrue(treeMap.size() == 1);

    Map<Integer, String> treeMap2 = new TreeMap<>();
    treeMap2.put(1, "ForEach");
    treeMap2.put(1, "ForEach");

    assertTrue(treeMap2.size() == 1);
}

4.2. Параллельный доступ

Обе реализации Map не синхронизированы , и нам нужно самостоятельно управлять одновременным доступом.

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

Мы должны явно использовать Collections.synchronizedMap(mapName) для получения синхронизированного представления предоставленной карты.

4.3. Отказоустойчивые итераторы

Итератор генерирует исключение ConcurrentModificationException , если карта изменяется каким-либо образом и в любое время после создания итератора.

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

Давайте посмотрим пример:

@Test
public void whenModifyMapDuringIteration_thenThrowExecption() {
    Map<Integer, String> hashmap = new HashMap<>();
    hashmap.put(1, "One");
    hashmap.put(2, "Two");
    
    Executable executable = () -> hashmap
      .forEach((key,value) -> hashmap.remove(1));
 
    assertThrows(ConcurrentModificationException.class, executable);
}

5. Какую реализацию использовать?

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

Резюмируя:

• Мы должны использовать TreeMap , если мы хотим, чтобы наши записи были отсортированы .
• Мы должны использовать HashMap , если мы отдаем приоритет производительности потреблению памяти .
• Поскольку TreeMap имеет более важное местоположение, мы могли бы рассмотреть его, если хотим получить доступ к объектам, которые относительно близки друг к другу в соответствии с их естественным порядком.
• HashMap можно настроить с помощью initialCapacity и loadFactor , что невозможно для TreeMap .
• Мы можем использовать LinkedHashMap , если мы хотим сохранить порядок вставки, получая при этом доступ к постоянному времени.

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

В этой статье мы показали сходства и различия между TreeMap и HashMap .

Как всегда, примеры кода для этой статьи доступны на GitHub .