В этом уроке мы сосредоточимся на основных различиях между TreeMap и HashMap.
TreeMap и HashMap довольно похожи, оба являются коллекциями, реализующими интерфейс Map. Но у них также есть некоторые различия, которые делают один лучше другого в некоторых ситуациях. Давайте рассмотрим эти различия.
1. Различия между HashMap и TreeMap
Давайте обсудим некоторые основные различия между двумя картами.
1.1 Иерархия классов
Класс HashMap расширяет класс AbstractMap и реализует интерфейс Map, тогда как класс TreeMap расширяет класс AbstractMap и реализует интерфейс NavigableMap.
// HashMap class declarationpublic class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable// TreeMap class declarationpublic class TreeMap<K, V> extends AbstractMap<K, V> implements NavigableMap<K, V>, Cloneable, Serializable
1.2 Внутренние реализации
- HashMap внутренне использует HashTable и работает по принципу хеширования. Он содержит контейнеры в форме LinkedList, и когда в контейнере больше 8 записей, то LinkedList преобразуется в сбалансированное дерево(TreeNodes).
- TreeMap использует внутри себя красно-черное дерево — самобалансирующееся двоичное дерево поиска.
1.3.Нулевые ключи и значения
TreeMap не допускает нулевого ключа, но может содержать любое количество нулевых значений.
HashMap допускает один нулевой ключ(для других нулевых ключей существующее значение будет просто перезаписано новым значением) и любое количество нулевых значений.
// Putting null key in TreeMapTreeMap<String, String> map = new TreeMap<>();map.put(null, "value"); //Exception in thread "main" java.lang.NullPointerException
TreeMap внутренне использует методы compareTo() или compare() из интерфейсов Comparable и Comparator соответственно для поддержания порядка элементов в карте на основе ключей, а в случае нулевого ключа эти методы выдают исключение « NullPointerException ».
1.4 Функциональность
TreeMap богаче функциональностью по сравнению с HashMap. Наряду с обычными методами(get(), put(), remove()) интерфейса Map, он содержит методы из интерфейса NavigableMap, а также pollFirstEntry(), pollLastEntry(), tailMap(), firstKey(), lastKey() и т. д., которых нет у класса HashMap.
// Creating TreeMapTreeMap<String, String> map = new TreeMap<>();// Putting values in TreeMapmap.put("key1", "value1");map.put("key2", "value2");map.put("key3", "value3");// Printing mapSystem.out.println(map); // Prints {key1=value1, key2=value2, key3=value3}// Getting first key from mapSystem.out.println(map.firstKey()); // Prints key1// Getting last key from mapSystem.out.println(map.lastKey()); // Prints key3// Getting first entry from mapSystem.out.println(map.firstEntry()); // Prints key1=value1// Polling last entry from mapSystem.out.println(map.pollLastEntry()); // Prints key3=value3// Printing map againSystem.out.println(map); // Prints {key1=value1, key2=value2}1.5.Упорядочивание элементов
HashMap не сохраняет порядок своих элементов, т.е. не дает никаких гарантий, что элемент, вставленный первым в карту, будет выведен первым во время итерации карты.
TreeMap хранит элементы в порядке сортировки их ключей. Сортировка может быть естественным порядком сортировки по умолчанию(по возрастанию для чисел и по алфавиту для строк) или настраиваемой сортировкой на основе объекта Comparator, указанного при создании карты.
// Creating HashMapHashMap<Integer, String> map = new HashMap<>();// Putting values in the mapmap.put(10, "value1");map.put(2, "value2");map.put(13, "value3");map.put(5, "value4");map.put(25, "value5");// Printing mapSystem.out.println(map); //{2=value2, 5=value4, 25=value5, 10=value1, 13=value3} - No ordering// Creating TreeMap using normal TreeMap() constructor which sorts the elements// based on natural sorting order of keysTreeMap<Integer, String> map = new TreeMap<>();// Putting values in mapmap.put(10, "value1");map.put(2, "value2");map.put(13, "value3");map.put(5, "value4");map.put(25, "value5");// Printing mapSystem.out.println(map); //{2=value2, 5=value4, 10=value1, 13=value3, 25=value5}// Creating TreeMap using TreeMap(Comparator) constructor by specifying Comparator object// as Lambda expression which sorts the elements according to customized sorting of keysmap = new TreeMap<Integer,String>((I1,I2) ->(I1<I2) ? 1 :(I1>I2) ? -1 : 0);// Putting values in mapmap.put(10, "value1");map.put(2, "value2");map.put(13, "value3");map.put(5, "value4");map.put(25, "value5");// Printing mapSystem.out.println(map); //{25=value5, 13=value3, 10=value1, 5=value4, 2=value2}1.6 Сравнение производительности
- HashMap быстрее TreeMap и обеспечивает постоянную производительность O(1) для большинства базовых операций, таких как get(), put(), contains() и remove(), в лучшем случае без коллизий хэшей.
- В случае коллизий хэшей(два ключа имеют одинаковый хэш-код) HashMap обрабатывает их, используя LinkedList для хранения коллизионных элементов, и, следовательно, производительность в этом случае снижается до O(n).
- Чтобы улучшить производительность HashMap во время коллизий, LinkedList преобразуется в сбалансированное дерево в случае, если количество записей в корзине превышает 8, что улучшает производительность в наихудшем случае с O(n) до O(log(n)).
С другой стороны, TreeMap обеспечивает производительность O(log(n)) для большинства базовых операций, таких как get(), put(), contains() и remove().
1.7 Использование памяти
TreeMap имеет более высокую производительность в управлении памятью, поскольку не поддерживает внутренний массив для хранения пар ключ-значение.
В HashMap размер массива определяется при инициализации или изменении размера, что часто больше, чем нужно в данный момент. Это тратит память. С TreeMap такой проблемы нет.
1.8 Ключевые поисковые запросы
HashMap использует методы hashCode() и equals() при сравнении ключей карты, в то время как TreeMap использует методы compareTo() или compare() при сравнении ключей.
// Creating HashMapHashMap<Integer, String> hashMap = new HashMap<>();// Putting values in maphashMap.put(10, "value1");hashMap.put(10, "value2");System.out.println("HashMap: " + hashMap);// Creating TreeMapTreeMap<Integer, String> treeMap = new TreeMap<>();// Putting values in maptreeMap.put(10, "value1");treeMap.put(10, "value2");System.out.println("TreeMap: " + treeMap);Обратите внимание на вывод программы. Несмотря на то, что вывод одинаков для обоих случаев, внутренне HashMap использует equals() при сравнении ключей и отклоняет второй ключ, поскольку он является дубликатом. В то время как TreeMap использует compareTo() при сравнении ключей и, таким образом, отклоняет второй ключ.
Кроме того, обе карты обновляют предыдущую запись, и на карте остается одна запись.
HashMap: {10=значение2}Карта дерева: {10=значение2}2. Когда использовать HashMap и TreeMap
Мы должны использовать TreeMap, если нам нужно добавлять элементы(пары ключ-значение) в отсортированном порядке. Давайте рассмотрим пример создания словаря, где слова сортируются в алфавитном порядке. Поэтому мы можем легко реализовать это с помощью TreeMap.
TreeMap более эффективен в плане использования памяти, поэтому это хорошая реализация карты для нас, если мы не уверены в количестве элементов, которые следует сохранить в памяти.
HashMap — это скорее реализация карты общего назначения, и ее можно использовать там, где нам не нужна никакая сортировка данных, а записи могут храниться в любом порядке или последовательности. В высокопроизводительных приложениях мы можем предпочесть HashMap вместо TreeMap, поскольку он работает лучше по сравнению с TreeMap.
3. Заключение
В этой статье мы рассмотрели некоторые ключевые различия между HashMap и TreeMap, а также факторы, которые следует учитывать при выборе между ними при использовании их в нашем коде.