Хэш карты что это
Структуры данных в картинках. HashMap
Приветствую вас, хабрачитатели!
Продолжаю попытки визуализировать структуры данных в Java. В предыдущих сериях мы уже ознакомились с ArrayList и LinkedList, сегодня же рассмотрим HashMap.
HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек.
Создание объекта
Вы можете указать свои емкость и коэффициент загрузки, используя конструкторы HashMap(capacity) и HashMap(capacity, loadFactor). Максимальная емкость, которую вы сможете установить, равна половине максимального значения int (1073741824).
Добавление элементов
Комментарий из исходников объясняет, каких результатов стоит ожидать — метод hash(key) гарантирует что полученные хэш-коды, будут иметь только ограниченное количество коллизий (примерно 8, при дефолтном значении коэффициента загрузки).
В моем случае, для ключа со значением »0» метод hashCode() вернул значение 48, в итоге:
При значении хэша 51 и размере таблице 16, мы получаем индекс в массиве:
Для того чтобы продемонстрировать, как заполняется HashMap, добавим еще несколько элементов.
Footprint
Object size: 376 bytes
Footprint
Object size: 496 bytes
Resize и Transfer
Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов. Как вы сами можете убедиться, ничего сложного в методах resize(capacity) и transfer(newTable) нет.
Метод transfer() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.
Если в исходный hashmap добавить, скажем, еще 15 элементов, то в результате размер будет увеличен и распределение элементов изменится.
Удаление элементов
У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается. И если в ArrayList предусмотрен метод trimToSize(), то в HashMap таких методов нет (хотя, как сказал один мой коллега — «А может оно и не надо?«).
Небольшой тест, для демонстрации того что написано выше. Исходный объект занимает 496 байт. Добавим, например, 150 элементов.
Теперь удалим те же 150 элементов, и снова замерим.
Как видно, размер даже близко не вернулся к исходному. Если есть желание/потребность исправить ситуацию, можно, например, воспользоваться конструктором HashMap(Map).
Итераторы
HashMap имеет встроенные итераторы, такие, что вы можете получить список всех ключей keySet(), всех значений values() или же все пары ключ/значение entrySet(). Ниже представлены некоторые варианты для перебора элементов:
Стоит помнить, что если в ходе работы итератора HashMap был изменен (без использования собственным методов итератора), то результат перебора элементов будет непредсказуемым.
Итоги
— Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки;
— Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии. Среднее же время работы будет Θ(1 + α), где α — коэффициент загрузки. В самом худшем случае, время выполнения может составить Θ(n) (все элементы в одной цепочке);
— Ключи и значения могут быть любых типов, в том числе и null. Для хранения примитивных типов используются соответствующие классы-оберки;
— Не синхронизирован.
Ссылки
Инструменты для замеров — memory-measurer и Guava (Google Core Libraries).
Чудеса хеширования
Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, защиту файлов и даже обнаружение зловредного ПО. Как они работают и где применяются?
Криптографические хеш-функции — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, проверку целостности данных, защиту файлов и даже обнаружение зловредного ПО. Существует масса алгоритмов хеширования, отличающихся криптостойкостью, сложностью, разрядностью и другими свойствами. Считается, что идея хеширования принадлежит сотруднику IBM, появилась около 50 лет назад и с тех пор не претерпела принципиальных изменений. Зато в наши дни хеширование обрело массу новых свойств и используется в очень многих областях информационных технологий.
Что такое хеш?
Если коротко, то криптографическая хеш-функция, чаще называемая просто хешем, — это математический алгоритм, преобразовывающий произвольный массив данных в состоящую из букв и цифр строку фиксированной длины. Причем при условии использования того же типа хеша длина эта будет оставаться неизменной, вне зависимости от объема вводных данных. Криптостойкой хеш-функция может быть только в том случае, если выполняются главные требования: стойкость к восстановлению хешируемых данных и стойкость к коллизиям, то есть образованию из двух разных массивов данных двух одинаковых значений хеша. Интересно, что под данные требования формально не подпадает ни один из существующих алгоритмов, поскольку нахождение обратного хешу значения — вопрос лишь вычислительных мощностей. По факту же в случае с некоторыми особо продвинутыми алгоритмами этот процесс может занимать чудовищно много времени.
Как работает хеш?
Например, мое имя — Brian — после преобразования хеш-функцией SHA-1 (одной из самых распространенных наряду с MD5 и SHA-2) при помощи онлайн-генератора будет выглядеть так: 75c450c3f963befb912ee79f0b63e563652780f0. Как вам скажет, наверное, любой другой Брайан, данное имя нередко пишут с ошибкой, что в итоге превращает его в слово brain (мозг). Это настолько частая опечатка, что однажды я даже получил настоящие водительские права, на которых вместо моего имени красовалось Brain Donohue. Впрочем, это уже другая история. Так вот, если снова воспользоваться алгоритмом SHA-1, то слово Brain трансформируется в строку 97fb724268c2de1e6432d3816239463a6aaf8450. Как видите, результаты значительно отличаются друг от друга, даже несмотря на то, что разница между моим именем и названием органа центральной нервной системы заключается лишь в последовательности написания двух гласных. Более того, если я преобразую тем же алгоритмом собственное имя, но написанное уже со строчной буквы, то результат все равно не будет иметь ничего общего с двумя предыдущими: 760e7dab2836853c63805033e514668301fa9c47.
Впрочем, кое-что общее у них все же есть: каждая строка имеет длину ровно 40 символов. Казалось бы, ничего удивительного, ведь все введенные мною слова также имели одинаковую длину — 5 букв. Однако если вы захешируете весь предыдущий абзац целиком, то все равно получите последовательность, состоящую ровно из 40 символов: c5e7346089419bb4ab47aaa61ef3755d122826e2. То есть 1128 символов, включая пробелы, были ужаты до строки той же длины, что и пятибуквенное слово. То же самое произойдет даже с полным собранием сочинений Уильяма Шекспира: на выходе вы получите строку из 40 букв и цифр. При всем этом не может существовать двух разных массивов данных, которые преобразовывались бы в одинаковый хеш.
Вот как это выглядит, если изобразить все вышесказанное в виде схемы:
Для чего используется хеш?
Отличный вопрос. Однако ответ не так прост, поскольку криптохеши используются для огромного количества вещей.
Для нас с вами, простых пользователей, наиболее распространенная область применения хеширования — хранение паролей. К примеру, если вы забыли пароль к какому-либо онлайн-сервису, скорее всего, придется воспользоваться функцией восстановления пароля. В этом случае вы, впрочем, не получите свой старый пароль, поскольку онлайн-сервис на самом деле не хранит пользовательские пароли в виде обычного текста. Вместо этого он хранит их в виде хеш-значений. То есть даже сам сервис не может знать, как в действительности выглядит ваш пароль. Исключение составляют только те случаи, когда пароль очень прост и его хеш-значение широко известно в кругах взломщиков. Таким образом, если вы, воспользовавшись функцией восстановления, вдруг получили старый пароль в открытом виде, то можете быть уверены: используемый вами сервис не хеширует пользовательские пароли, что очень плохо.
Вы даже можете провести простой эксперимент: попробуйте при помощи специального сайта произвести преобразование какого-нибудь простого пароля вроде «123456» или «password» из их хеш-значений (созданных алгоритмом MD5) обратно в текст. Вероятность того, что в базе хешей найдутся данные о введенных вами простых паролях, очень высока. В моем случае хеши слов «brain» (8b373710bcf876edd91f281e50ed58ab) и «Brian» (4d236810821e8e83a025f2a83ea31820) успешно распознались, а вот хеш предыдущего абзаца — нет. Отличный пример, как раз для тех, кто все еще использует простые пароли.
Еще один пример, покруче. Не так давно по тематическим сайтам прокатилась новость о том, что популярный облачный сервис Dropbox заблокировал одного из своих пользователей за распространение контента, защищенного авторскими правами. Герой истории тут же написал об этом в твиттере, запустив волну негодования среди пользователей сервиса, ринувшихся обвинять Dropbox в том, что он якобы позволяет себе просматривать содержимое клиентских аккаунтов, хотя не имеет права этого делать.
Впрочем, необходимости в этом все равно не было. Дело в том, что владелец защищенного копирайтом контента имел на руках хеш-коды определенных аудио- и видеофайлов, запрещенных к распространению, и занес их в список блокируемых хешей. Когда пользователь предпринял попытку незаконно распространить некий контент, автоматические сканеры Dropbox засекли файлы, чьи хеши оказались в пресловутом списке, и заблокировали возможность их распространения.
Где еще можно использовать хеш-функции помимо систем хранения паролей и защиты медиафайлов? На самом деле задач, где используется хеширование, гораздо больше, чем я знаю и тем более могу описать в одной статье. Однако есть одна особенная область применения хешей, особо близкая нам как сотрудникам «Лаборатории Касперского»: хеширование широко используется для детектирования зловредных программ защитным ПО, в том числе и тем, что выпускается нашей компанией.
Как при помощи хеша ловить вирусы?
Примерно так же, как звукозаписывающие лейблы и кинопрокатные компании защищают свой контент, сообщество создает списки зловредов (многие из них доступны публично), а точнее, списки их хешей. Причем это может быть хеш не всего зловреда целиком, а лишь какого-либо его специфического и хорошо узнаваемого компонента. С одной стороны, это позволяет пользователю, обнаружившему подозрительный файл, тут же внести его хеш-код в одну из подобных открытых баз данных и проверить, не является ли файл вредоносным. С другой — то же самое может сделать и антивирусная программа, чей «движок» использует данный метод детектирования наряду с другими, более сложными.
Криптографические хеш-функции также могут использоваться для защиты от фальсификации передаваемой информации. Иными словами, вы можете удостовериться в том, что файл по пути куда-либо не претерпел никаких изменений, сравнив его хеши, снятые непосредственно до отправки и сразу после получения. Если данные были изменены даже всего на 1 байт, хеш-коды будут отличаться, как мы уже убедились в самом начале статьи. Недостаток такого подхода лишь в том, что криптографическое хеширование требует больше вычислительных мощностей или времени на вычисление, чем алгоритмы с отсутствием криптостойкости. Зато они в разы надежнее.
Кстати, в повседневной жизни мы, сами того не подозревая, иногда пользуемся простейшими хешами. Например, представьте, что вы совершаете переезд и упаковали все вещи по коробкам и ящикам. Погрузив их в грузовик, вы фиксируете количество багажных мест (то есть, по сути, количество коробок) и запоминаете это значение. По окончании выгрузки на новом месте, вместо того чтобы проверять наличие каждой коробки по списку, достаточно будет просто пересчитать их и сравнить получившееся значение с тем, что вы запомнили раньше. Если значения совпали, значит, ни одна коробка не потерялась.
Хэш-карта с закрытой адресацией
Ассоциативный массив. Введение
Д ля начала рассмотрим несколько задач, которые часто встречаются в программировании, затем попытаемся найти в них общие черты, а потом предложим общее решение.
1. Пусть нам необходим массив, который состоит из большого числа элементов. Массив имеет размер порядка 2 128 элементов, но хранятся в нём всего около 2 10 – 2 20 штук. Проблема в том, что нужные элементы в массиве располагаются не обособленно, а размазаны по всему массиву, так что выделить подмассив достаточно малого размера и работать с ним не получится. Создать массив размера 2 128 мы тоже не можем.
Самое простое решение – использовать список. Но у списков скорость поиска, вставки нового элемента и удаления элемента имеют сложность порядка n, а у массива это константа. Иными словами, нам бы хотелось такую структуру данных, в которой бы поиск, вставка и удаление были как и у массива, но при этом не было необходимости держать незанятыми много элементов.
Решение задачи
Пусть нужно хранить 3 значения, с индексами 1001883726, 4524352321524 и 77656433109. Для этого создадим массив A размером в N раз больше, чем элементов. Как находить это число N не известно пока. Возьмём массив размером 10 элементов.
После этого, вместо индекса будем брать остаток от деления на размер массива (в нашем случае 10). Тогда, первый элемент будет иметь индекс 6, и мы поместим его в массив A[6]. Второй элемент в массив под номером 4, третий под номером 9.
Очевидно, что могут появиться элементы с одинаковым индексом. Пусть теперь мы добавляем элемент с индексом 3776. Элемент A[6] же занят, поэтому мы создаём на месте элемента 6 односвязный список и привязываем новое значение к старому.
Когда элементов станет очень много, мы получим маленький массив длинных односвязных списков. Время доступа снизится до O(n). Чтобы этого избежать, когда массив будет заполнен на X процентов, нужно будет пересобрать массив, увеличив его размер в M раз. Тогда, при хорошем распределении, среднее время доступа будет порядка 1, а длинна каждого односвязного списка будет примерно единицей.
Вы успели заметить, что в таком описании очень много условностей. Начнём разбираться с неизвестными X, M и N.
Начальный размер массива, в принципе, может быть любым, хоть единицей. Нам больше важен коэффициент заполнения X, при котором будет происходить пересборка. Это значение называют load factor. В языке C# это значение равно 0.72, а в Java 0.75. Эти значения получены после анализ большого количества кода и считаются для данных языков оптимальными. Анализ мы проводить не будем, а просто возьмём на веру значение 0.72.
Пересборку будем осуществлять следующим образом: создадим новую карту нового размера, поместим в неё элементы из старого массива, удалим старую карту.
Поиск элемента осуществляется подобно вставке. Сначала находим его индекс I в массиве. Если в массиве по номеру I нет элемента, то смотрим, есть ли хвост за I-м элементом. Если есть, то проходим по всему списку и ищем в нём нужный нам элемент. При удалении элемента находим его позицию, удаляем пару, удаляем узел списка.
В качестве структуры для хранения элементов (её ещё называют корзиной) может быть использован не только односвязный список, но, например, красно-чёрное дерево, или список с пропусками. Тогда в плохом случае сложность опустится всего до log(n).
Описанная нами структура называется ассоциативным массивом с закрытой адресацией. Также существует ассоциативный массив с открытой адресацией. В нём вместо создания односвязного списка, по определённому алгоритму мы ищем пустую ячейку в текущем массиве. Рассмотрим его позднее.
Вторая задача
Мы хотим реализовать структуру, подобную массиву, но в качестве индекса хотим использовать строку. То есть, обращаться к массиву как a[“Pupkin”], а не a[1772634]. Очевидно, что если бы мы могли каждой строке поставить в соответствие число, то тогда можно было бы свести вторую задачу к первой.
Третья задача
Для решения второй и третьей задачи воспользуемся хэшированием.
Как говорит Википедия, Хеширование (иногда «хэшировани», англ. hashing) — преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или сводкой сообщения (англ. message digest).
Хэш-функции используются для решения многих задач. В нашем случае они помогут нам тем, что каждой строке или объекту поставят в соответствие число.
Вообще, нахождение и анализ хэш-функций – очень сложная и объёмная задача. Мы не будем о ней говорить, просто возьмём готовые решения. В качестве хранимых объектов в нашем примере будем использовать строки. Хэш-функция для строк выглядит в нашем случае, следующим образом.
Фактически мы производим отображение из почти бесконечного пространства строк (оно ограничено размерами оперативной памяти) в пространство длинных чисел (оно обычно ограничено 64 или 128 битами). Так как мощность множества строк гораздо больше, то отображение будет суръективное, то есть для многих строк хэш-код будет один и тот же. Эта ситуация называется коллизией. Именно поэтому в карте мы будем хранить не хэш-код, а всё значение ключа.
Из этого следует, что ключ должен поддерживать операцию равенства. К счастью, почти все объекты поддерживают эту операцию (исключение, например, это значение NaN, для которого не поддерживается свойство рефлексии a == a).
Хэш-карта. Реализация.
Объявим набор констант. Это значения по умолчанию для нашей хэш-карты.
Структура Entry – пара
Далее, структура для реализации односвязного списка
Нужно также ввести функцию освобождения памяти из-под пары. В принципе, можно было бы оставить освобождение на совести пользователя, но это не этично.
Теперь, собственно, сама структура «хэш-карта».
Для упрощение работы введено ещё одно значение limit. Это целочисленное значение количества элементов, при превышении которого произойдёт пересборка.
Функция создания карты
Здесь мы защищаем пользователя от ввода «плохих» по нашему мнению значений. То есть, минимальное значение элементов массива не может быть меньше INITIAL_SIZE и т.д.
Обёртка для неё. Она позволяет использовать в качестве аргументов непосредственный значения.
Вспомогательная функция rehashUp. Создаём новую карту с новыми размерами, проходим все значения и вставляем их в новую карту.
Поиск элемента. Возвращаем только значение пары
Удаление элемента. Заметьте, здесь мы возвращаем указатель на всю пару, так что при использовании необходимо будет явно удалять это значение.
Функция, которая проходит по всей карте и применяет функцию f ко всем парам.
Удаление всей карты будем проводить совместно с удалением всех пар. Именно для этого мы создавали freeEntry
Основные преимущества хэш-карты это постоянство скорости вставки, удаления и поиска в среднем случае. Кроме того, ключ в карте не требует реализации операции «больше-меньше», требуется наличие операции равенства и хэш-функции. Из-за этого возникают и свои проблемы. Так как значения хранятся неупорядоченно, то поиск максимума и минимума будут порядка O(n), так как придётся просмотреть все элементы. А если хэш-функция «плохая» и даёт много одинаковых кодов, то скорость сильно снизится.
Хэш-карта и карта деревьев в Java: различия и сходства
Производительность Java-программы и правильное использование ресурсов часто зависят от коллекции, которую разработчик выбрал для хранения данных. Следовательно, очень важно понимать разницу между реализациями. Вот почему вопросы, связанные с коллекциями, находятся в верхней части интервью для кандидатов в младшие разработчики Java.
В этой статье мы рассмотрим две реализации интерфейса карты, HashMap и TreeMap, и попытаемся ответить на вопрос об их различиях и о том, когда программисту следует использовать первую и вторую.
Я надеюсь, что читатель хорошо знаком с понятиями интерфейса и реализации, и я дам только основные определения, чтобы упростить это чтение. Я также позволю себе некоторые ссылки на другие статьи и документацию для тех, кто забыл некоторые детали.
Что такое карта
Интерфейс Map является частью платформы сбора Java. Вы можете представить карту как своего рода словарь, где каждый элемент представляет пару ключ-значение. И ключи, и значения являются объектами. Карта позволяет искать объект по заданному ключу. Объект, связанный с ключом, является значением. Все ключи уникальны, в то время как значения могут быть продублированы. Некоторые реализации карты допускают нулевые ключи и нулевые значения. Основными операциями любой карты являются вставка, удаление и поиск элементов.
Как хэш-карта, так и карта деревьев являются реализациями интерфейсов карт. Вкратце, HashMap-это структура данных, которая хэширует ключи, а TreeMap использует естественный порядок ключей для организации дерева поиска.
Что такое HashMap
Чтобы понять, что такое Hashmap, сначала вы должны знать о хешировании и хэш-функциях. Детали алгоритма выходят за рамки этой статьи, но я собираюсь дать вам определение хэш-функции (а также двоичное дерево для другой темы этой статьи, карты деревьев) и краткое описание внутренней работы HashMap для лучшего понимания.
Принцип хэширования
Хэш-коды помогают программам работать быстрее. Предположим, мы сравниваем объекты объема s1 и s2 типа Студент и объявляем, что операция s1.равно(s2) занимает около 500 мс. В этом случае сравнение хэш-кодов s1.hashCode().hashCode() занимает около 20 мс.
Хэш-функции широко используются в криптографии, а также в других областях. Однако магия не предназначена для разработки программного обеспечения: вы не можете поместить что-то большое в маленький сосуд без потерь.
Основные правила работы с хэш – кодами:
Внутри хэш-карты
Что такое карта деревьев
Java TreeMap-это структура данных, которая реализует Map интерфейс и основана на красно-черной структуре данных дерева.
Красно-Черное Дерево
Дерево – это иерархическая структура данных, состоящая из “узлов” и линий, соединяющих узлы (“ветви”). “Корневой” узел находится в верхней части дерева, и от корня могут отходить ветви и узлы (“дочерние” корни). У каждого дочернего узла также могут быть свои собственные дочерние узлы (узлы, расположенные ниже). Узлы без дочерних элементов называются “конечными узлами”, “конечными узлами” или “листьями”.
В двоичном дереве у каждого узла есть ноль, один или два дочерних элемента. Каждый внутренний узел дерева двоичного поиска хранит ключ (а иногда и связанное с ним значение) и имеет два выделенных поддерева, обычно обозначаемых “слева” и “справа”. Вы можете представить это дерево как реализацию алгоритма бинарного поиска|/.
Красно-черное дерево является сбалансированным двоичным деревом со следующими свойствами:
Ознакомьтесь с этой статьей для получения дополнительной информации о Красно-черных деревьях
Карта деревьев
Древовидная карта-это реализация карты, которая сортирует свои записи в соответствии с естественным порядком их ключей. Для чисел это означает порядок возрастания, для строк — алфавитный порядок. Однако можно использовать компаратор, если вам нужно изменить логику упорядочения.
“Круто”, – можете подумать вы… “Теперь я могу вызвать метод toString и отсортировать все объекты или повторить их естественным способом”, и вы будете правы. Однако это не главное преимущество реализации древовидной карты. Самое замечательное в этом то, что вы можете найти некоторые объекты, используя различные фильтры и условия.
Git Essentials
Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!
Здесь мы рассортировали всех Кошек от Бориса до Снежинки в алфавитном порядке. Конечно, мы можем сделать то же самое с хэш-картой, но мы должны закодировать всю логику сортировки и так далее.
Хэш-карта против карты деревьев: основные различия
Заказ
Хэш-карта не упорядочена, в то время как древовидная карта сортируется по ключу. Способ хранения элементов зависит от хэш-функции ключей и кажется хаотичным.
Древовидная карта, которая реализует не только карту, но и Навигационную карту автоматически сортирует пары по их естественным порядкам ключей (в соответствии с их методом compareTo() или внешним Компаратором ).
Пример. Давайте создадим две карты, хэш-карту и карту деревьев, где ключами являются имена кошек из строкового массива.
Карта деревьев, упорядоченная по клавишам (алфавитный порядок имен кошек):
Представление
Согласно своей структуре, HashMap требует больше памяти, чем просто для хранения своих элементов. Производительность хэш — карты зависит от двух параметров- начальной емкости и коэффициента загрузки. Начальная емкость – это количество сегментов новой созданной хэш-карты. Коэффициент нагрузки измеряет процент наполненности. Начальная емкость по умолчанию составляет 16, а коэффициент загрузки по умолчанию равен 0,75. Мы можем изменить эти значения.
Таким образом, HashMap почти всегда работает быстрее, чем TreeMap. Чем больше объект, который хранится, тем быстрее будет хэш-карта по сравнению с картой деревьев. Однако древовидная карта использует оптимальный объем памяти для хранения своих элементов, в отличие от хэш-карты.
Пустые ключи и пустые значения
Хэш-карта позволяет хранить один нулевой ключ и несколько нулевых значений. Он сохраняет запись с нулевым ключом в индексе[0] внутреннего блока. HashMap также позволяет хранить множество нулевых значений. Пример:
На выходе мы получим хэш-карту с тремя элементами, первый из которых имеет нулевой ключ и значение, второй – “обычный”, а третий также имеет нулевое значение.
Что, если мы попытаемся добавить еще один элемент с нулевым ключом?
Новая запись сохраняется в индексе[0] внутреннего блока, поэтому она будет перезаписана:
Древовидная карта сортирует элементы в естественном порядке и не допускает нулевых ключей, потому что compareTo() метод выдает Исключение NullPointerException при сравнении с null.
Поэтому, если мы попытаемся запустить следующий код:
Что у вас общего?
И древовидная карта, и хэш-карта реализуют интерфейс карты, поэтому они не поддерживают дубликаты ключей.
Они не являются потокобезопасными, поэтому вы не можете безопасно использовать их в многопоточном приложении.
Выводы
Древовидная карта использует память намного эффективнее, поэтому это хорошая реализация карты для вас, если вы не уверены в количестве элементов, которые должны храниться в памяти.
Используйте карту деревьев, если вам нужно сохранить все записи в естественном порядке.