Глубокое понимание разницы между HashMap и TreeMap

Java

Глубокое понимание разницы между HashMap и TreeMap

Введение

HashMap и TreeMap — два очень часто используемых класса в семействе Map.В чем разница между этими двумя классами в использовании и в природе? В этой статье мы проведем углубленное обсуждение этих двух аспектов, надеясь раскрыть их суть.

Существенная разница между HashMap и TreeMap

Сначала посмотрите на определение HashMap:

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

Посмотрите на определение TreeMap:

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

Из определения класса и HashMap, и TreeMap наследуют от AbstractMap, разница в том, что HashMap реализует интерфейс Map, а TreeMap реализует интерфейс NavigableMap. NavigableMap — разновидность SortedMap, реализующая сортировку ключей в Map.

Итак, первое различие между ними проявляется: TreeMap отсортирован, а HashMap — нет.

Давайте посмотрим на разницу между конструкторами HashMap и TreeMap.

public HashMap(int initialCapacity, float loadFactor)

В дополнение к конструктору без аргументов по умолчанию, HashMap также может принимать два параметра initialCapacity и loadFactor.

Базовая структура HashMap представляет собой массив узлов:

transient Node<K,V>[] table

initialCapacity — начальная емкость таблицы. Если вы не передаете initialCapacity, HashMap предоставляет значение по умолчанию:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

Когда в HashMap хранится слишком много данных, массив таблицы будет заполнен, и в это время требуется расширение, расширение HashMap осуществляется кратно 2. И loadFactor указывает, когда требуется операция расширения. Значение loadFactor по умолчанию равно 0,75.

static final float DEFAULT_LOAD_FACTOR = 0.75f;

Давайте рассмотрим еще несколько интересных переменных:

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

Какие три переменные выше? До Java 8 метод разрешения конфликтов хэш-кода для HashMap был в форме связанного списка.Для повышения эффективности Java 8 преобразовала его в TreeNode. Когда будет отправлено это преобразование?

Это время зависит от двух переменных TREEIFY_THRESHOLD и UNTREEIFY_THRESHOLD.

Некоторые учащиеся могут найти, почему TREEIFY_THRESHOLD BRIDER 2? На самом деле я не знаю этой проблемы, но когда вы видите исходный код, используйте Untreeify_threshold, это = Treeify_threshold - 1, так что эти две переменные по сути одинаковы .

MIN_TREEIFY_CAPACITY указывает, что TREENODE разрешено, когда Таблица преобразует наименьшую емкость Treenode, разрешается преобразовывать только Capacity> = min_treeify_capacity.

Разница между TreeMap и HashMap заключается в том, что нижний слой TreeMap — это Entry:

private transient Entry<K,V> root

Его реализация — красно-черное дерево, удобное для обхода и поиска.

Конструктор TreeMap может передавать Comparator для реализации пользовательского метода сравнения.

public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

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

Сортировать разницу

После того, как мы поговорили о природе двух сортировок, давайте рассмотрим пример и посмотрим на разницу между двумя сортировками:

    @Test
    public void withOrder(){
        Map<String, String> books = new HashMap<>();
        books.put("bob", "books");
        books.put("c", "concurrent");
        books.put("a", "a lock");
        log.info("{}",books);
    }

    @Test
    public void withOrder(){
        Map<String, String> books = new TreeMap<>();
        books.put("bob", "books");
        books.put("c", "concurrent");
        books.put("a", "a lock");
        log.info("{}",books);
    }

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

Разница между нулевыми значениями

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

    @Test
    public void withNull() {
        Map<String, String> hashmap = new HashMap<>();
        hashmap.put(null, null);
        log.info("{}",hashmap);
    }

    @Test
    public void withNull() {
        Map<String, String> hashmap = new TreeMap<>();
        hashmap.put(null, null);
        log.info("{}",hashmap);
    }

HashMap сообщит: NullPointerException.

Разница в производительности

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

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

Если в HashMap есть конфликт хэшей, эффективность будет хуже, но после того, как Java 8 выполнит преобразование TreeNode, эффективность значительно повысится.

TreeMap будет переупорядочиваться при добавлении и удалении узлов, что повлияет на производительность.

точки соприкосновения

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

Примеры этой статьиGitHub.com/Dadean2009/приходите…

Добро пожаловать, обратите внимание на мой публичный номер: вас ждут самые интересные вещи о программе! Для получения дополнительной информации, пожалуйста, посетитеwww.flydean.com

Категории