«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. Order

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 с определяемым пользователем Компаратором, то это зависит от реализация метода 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 хранит свои данные в иерархическом дереве с возможностью сортировки элементов с помощью специального компаратора.

Краткая информация о его производительности:

TreeMap обеспечивает производительность O(log(n)) для большинства операций, таких как add(), remove() и contains() Treemap может экономить память (по сравнению с 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, "Baeldung");
    treeMap.put(1, "Baeldung");

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

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

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

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

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

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

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

4.3. Fail-Fast Iterators

Итератор генерирует исключение 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, если мы отдаем предпочтение производительности над потреблением памяти. доступ к объектам, которые относительно близки друг к другу в соответствии с их естественным порядком. HashMap можно настроить с помощью initialCapacity и loadFactor, что невозможно для TreeMap.

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

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

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