Хэш-карта и карта деревьев в Java: различия и сходства

Автор оригинала: Guest Contributor.

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

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

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

Что такое карта

Интерфейс Map<Ключ, значение> является частью платформы сбора Java. Вы можете представить карту как своего рода словарь, где каждый элемент представляет пару ключ-значение. И ключи, и значения являются объектами. Карта позволяет искать объект по заданному ключу. Объект, связанный с ключом, является значением. Все ключи уникальны, в то время как значения могут быть продублированы. Некоторые реализации карты допускают нулевые ключи и нулевые значения. Основными операциями любой карты являются вставка, удаление и поиск элементов.

Итак, ключ-это уникальный идентификатор объекта на Карте. Например, Map<Строка, Студент> содержит ключ в виде строки — уникальный идентификатор студента, который связан с каким-либо объектом Студент .

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

Что такое HashMap

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

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

Принцип хэширования

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

Каждый объект Java имеет хэш-код. Обычно это число, и оно вычисляется с помощью метода хэш-кода класса объектов. Хорошая идея состоит в том, чтобы переопределить этот метод для ваших собственных классов вместе с связанным с ним методом equals .

Хэш-коды помогают программам работать быстрее. Предположим, мы сравниваем объекты объема s1 и s2 типа Студент и объявляем, что операция s1.равно(s2) занимает около 500 мс. В этом случае сравнение хэш-кодов s1.hashCode().hashCode() занимает около 20 мс.

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

Основные правила работы с хэш – кодами:

• Конкретный объект всегда имеет один и тот же хэш-код.
• Если объекты равны, их хэш-коды одинаковы, но не наоборот.
• Если хэш-коды разные, то объекты определенно не равны.
• Разные объекты могут (хотя и очень маловероятно) иметь одинаковые хэш-коды. Хорошо… здесь мы обнаружили потерю данных! Эта ситуация называется столкновением. “Хороший” хэш-код должен минимизировать вероятность столкновений.

Внутри хэш-карты

HashMap позволяет нам хранить ключи по принципу хеширования. Существует два основных метода — put(ключ, значение) и get(ключ) для хранения и извлечения объектов из HashMap. Пары ключ-значение хранятся в так называемых “корзинах”, все корзины вместе представляют собой “таблицу”, своего рода внутренний массив связанных списков .

Таким образом, первый элемент связанного списка хранится в корзине. Этот связанный список представляет собой цепочку объектов, и каждый из них имеет ссылку на следующий объект из цепочки. Следовательно, имея первый элемент, вы можете попасть в цепочку всех элементов списка. Элемент связанного списка-это объект класса Запись , содержащий ключ, значение и ссылку на следующую Запись .

Когда мы вызываем put(ключ, значение) , HashMap вызывает Хэш-код метод для ключа объекта. Затем он применяет хэш-код, который мы получили, в свою собственную функцию хэширования, которая помогает найти место для хранения объекта Записи . HashMap хранит ключ и значение объекты как Map.Запись в корзине.

Что такое карта деревьев

Java TreeMap-это структура данных, которая реализует Map<Ключ,значение> интерфейс и основана на красно-черной структуре данных дерева.

Красно-Черное Дерево

Дерево – это иерархическая структура данных, состоящая из “узлов” и линий, соединяющих узлы (“ветви”). “Корневой” узел находится в верхней части дерева, и от корня могут отходить ветви и узлы (“дочерние” корни). У каждого дочернего узла также могут быть свои собственные дочерние узлы (узлы, расположенные ниже). Узлы без дочерних элементов называются “конечными узлами”, “конечными узлами” или “листьями”.

В двоичном дереве у каждого узла есть ноль, один или два дочерних элемента. Каждый внутренний узел дерева двоичного поиска хранит ключ (а иногда и связанное с ним значение) и имеет два выделенных поддерева, обычно обозначаемых “слева” и “справа”. Вы можете представить это дерево как реализацию алгоритма бинарного поиска|/.

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

Красно-черное дерево является сбалансированным двоичным деревом со следующими свойствами:

• Каждый узел либо красный, либо черный
• Корень всегда черный
• Каждый лист-это НУЛЕВОЙ узел, и он черный
• Если узел красный, то оба его дочерних элемента черные. Следовательно, у красного узла не может быть красного ребенка.
• Каждый простой путь от анода к листу-потомку содержит одинаковое количество черных узлов.

Ознакомьтесь с этой статьей для получения дополнительной информации о Красно-черных деревьях

Карта деревьев

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

“Круто”, – можете подумать вы… “Теперь я могу вызвать метод toString и отсортировать все объекты или повторить их естественным способом”, и вы будете правы. Однако это не главное преимущество реализации древовидной карты. Самое замечательное в этом то, что вы можете найти некоторые объекты, используя различные фильтры и условия.

Например, давайте выберем всех кошек от букв “b” до “s” из коллекции кошек. Для этого мы собираемся использовать метод subMap () .

public class Solution {
    public static void main(String[] args) throws Exception {
        String[] cats = new String[]{"Fluffy", "Abby", "Boris", "Ginger", "Grey", "Snowy", "Boss", "Waldo", "Tom", "Garfield"};

        TreeMap treeMap = addCatsToTreeMap(cats);
        System.out.println(treeMap.subMap("Boris", true,"Snowy",true));
    }

    public static TreeMap addCatsToTreeMap(String[] cats) {
        TreeMap myCats = new TreeMap();
        for (int i = 0; i < cats.length; i++) {
            Cat cat = new Cat(cats[i]);
            myCats.put(cat.name, cat);
        }
        return myCats;
    }

    public static class Cat {
        String name;

        public Cat(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return name != null ? name.toUpperCase() : null;
        }
    }
}

Вывод:

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

{Boris=BORIS, Boss=BOSS, Fluffy=FLUFFY, Garfield=GARFIELD, Ginger=GINGER, Grey=GREY, Snowy=SNOWY}

Здесь мы рассортировали всех Кошек от Бориса до Снежинки в алфавитном порядке. Конечно, мы можем сделать то же самое с хэш-картой, но мы должны закодировать всю логику сортировки и так далее.

Хэш-карта против карты деревьев: основные различия

Заказ

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

Древовидная карта, которая реализует не только карту, но и Навигационную карту автоматически сортирует пары по их естественным порядкам ключей (в соответствии с их методом compareTo() или внешним Компаратором ).

Пример. Давайте создадим две карты, хэш-карту и карту деревьев, где ключами являются имена кошек из строкового массива.

import java.util.HashMap;
import java.util.TreeMap;

public class Test {
    public static void main(String[] args) throws Exception {
        String[] cats = new String[]{"Fluffy", "Abby", "Boris", "Ginger", "Grey", "Snowy", "Boss", "Waldo", "Tom", "Garfield"};
        Integer age;
        HashMap hMap = new HashMap<>();
        for (int i = 0; i < cats.length; i++) {
            hMap.put(cats[i], i);
        }
        System.out.println("HashMap ordered by hash:");
        System.out.println(hMap);
        System.out.println();

        TreeMap tMap = new TreeMap<>();
        for (int i = 0; i < cats.length; i++) {
            tMap.put(cats[i], i);
        }
        System.out.println("TreeMap ordered by keys (alphabetical order of the cats' names:");
        System.out.println(tMap);

    }
}

Вывод:

HashMap ordered by hash:
{Fluffy=0, Boss=6, Snowy=5, Tom=8, Garfield=9, Abby=1, Boris=2, Waldo=7, Ginger=3, Grey=4}

Карта деревьев, упорядоченная по клавишам (алфавитный порядок имен кошек):

{Abby=1, Boris=2, Boss=6, Fluffy=0, Garfield=9, Ginger=3, Grey=4, Snowy=5, Tom=8, Waldo=7}

Представление

HashMap работает быстрее и обеспечивает среднюю производительность за постоянное время O(1) для основных операций get() и put() , если хэш-функция правильно распределяет элементы по сегментам. Обычно это работает как есть, но на самом деле иногда случаются столкновения. В этом случае HashMap обрабатывает столкновение, используя связанный список для хранения столкнувшихся элементов, и производительность снижается до O(n) .

Для повышения производительности в случае частых столкновений в JDK 8 используется сбалансированное дерево вместо связанного списка. JDK8 переключается на сбалансированное дерево в случае более 8 записей в одном ведре, это улучшает производительность в худшем случае с O(n) до O(log (n)) .

Согласно своей структуре, HashMap требует больше памяти, чем просто для хранения своих элементов. Производительность хэш — карты зависит от двух параметров- начальной емкости и коэффициента загрузки. Начальная емкость – это количество сегментов новой созданной хэш-карты. Коэффициент нагрузки измеряет процент наполненности. Начальная емкость по умолчанию составляет 16, а коэффициент загрузки по умолчанию равен 0,75. Мы можем изменить эти значения.

Древовидная карта основана на двоичном дереве, которое обеспечивает производительность по времени O(log(n)) .

Таким образом, HashMap почти всегда работает быстрее, чем TreeMap. Чем больше объект, который хранится, тем быстрее будет хэш-карта по сравнению с картой деревьев. Однако древовидная карта использует оптимальный объем памяти для хранения своих элементов, в отличие от хэш-карты.

Пустые ключи и пустые значения

Хэш-карта позволяет хранить один нулевой ключ и несколько нулевых значений. Он сохраняет запись с нулевым ключом в индексе[0] внутреннего блока. HashMap также позволяет хранить множество нулевых значений. Пример:

import java.util.HashMap;

public class Test {
    public static void main(String[] args) throws Exception {

        HashMap hashMap = new HashMap<>();
        hashMap.put(null, null);
        hashMap.put ("Fluffy", 7);
        hashMap.put("Kid", null);

        System.out.println(hashMap);
    }
}

На выходе мы получим хэш-карту с тремя элементами, первый из которых имеет нулевой ключ и значение, второй – “обычный”, а третий также имеет нулевое значение.

{null=null, Fluffy=7, Kid=null}

Что, если мы попытаемся добавить еще один элемент с нулевым ключом?

import java.util.HashMap;

public class Test {
    public static void main(String[] args) throws Exception {

        HashMap hashMap = new HashMap<>();
        hashMap.put(null, null);
        hashMap.put(null, 5);
        hashMap.put ("Fluffy", 7);
        hashMap.put("Kid", null);

        System.out.println(hashMap);
    }
}

Новая запись сохраняется в индексе[0] внутреннего блока, поэтому она будет перезаписана:

{null=5, Fluffy=7, Kid=null}

Древовидная карта сортирует элементы в естественном порядке и не допускает нулевых ключей, потому что compareTo() метод выдает Исключение NullPointerException при сравнении с null.

Поэтому, если мы попытаемся запустить следующий код:

TreeMap treeMap = new TreeMap<>();
treeMap.put(null, 5);
treeMap.put ("Fluffy", 7);
treeMap.put("Kid", null);

System.out.println(treeMap);

У нас есть java.lang.Исключение NullPointerException .

Если вы используете древовидную карту с определяемым пользователем Компаратором , работа с нулевыми записями зависит от реализации метода compare () .

Что у вас общего?

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

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

Выводы

HashMap-это реализация карты общего назначения. Он обеспечивает производительность O(1) , в то время как карта дерева обеспечивает производительность O(log(n)) для добавления, поиска и удаления элементов. Следовательно, HashMap обычно работает быстрее.

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

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

Об авторе

Джон Селавски-старший разработчик Java и преподаватель Java на международных курсах программирования Learning Tree. Посетите его личный Средний блог , чтобы прочитать больше мыслей и советов Джона по Java.