Структуры данных в картинках. 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).
Паршин Павел
Главное меню
Вопросы и ответы на собеседовании по теме Java Collection Framework. Часть 1.
Общая иерархия
9. Как одним вызовом копировать элементы из любой Collection в массив?
Iterator, Iterable
Оба интерфейса предназначены для обхода коллекций. Интерфейс Iterator был введен несколько позднее в Java Collections Framework и его использование предпочтительнее.
Основные различия Iterator по сравнению с Enumeration :
Нет, hasNext() осуществляет только проверку наличия следующего элемента.
7. Если у меня есть коллекция и порожденный итератор, изменится ли коллекция, если я вызову iterator.remove()?
Если iterator.next() был вызван прежде, то iterator.remove() удалит элемент, на который указывает итератор.
List: ArrayList, LinkedList
Обе структуры данных предназначены для хранения коллекции элементов, в том числе дупликатов и null. Они основаны на использовании массивов, динамически расширяющихся при необходимости.
Класс Vector был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Vector синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс ArrayList, методы которого не синхронизированы.
3. LinkedList — это односвязный, двусвязный или четырехсвязный список?
Двухсвязный список: каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.
Если в массиве достаточно места для размещения нового элемента, то дополнительное место в памяти не выделяется. Иначе происходит создание нового массива с размером:
Другими словами, создается новый массив, размер которого вычисляется как умножение старого размера на 1.5 (это верно для JDK 1.7, в более ранних версиях вычисления отличаются).
Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны.
Использовать обратный итератор. Для этого в LinkedList есть метод descendingIterator().
14. Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?
Коллекции в Java
2020.06.08 (Последнее изменение: 2021.07.15)
Общее описание
Интерфейсы коллекций
Иерархия интерфейсов коллекций 
| Интерфейс | Описание |
|---|---|
| Itarable | Реализация данного интерфейса позволяет объекту использоваться в цикле “for-each” |
| Collection | Корневой интерфейс в иерархии коллекций. |
| List | Упорядоченная коллекция (также известная как последовательность). |
| Set | Коллекция (набор/множество), которая не содержит повторяющихся элементов. |
| SortedSet | Интерфейс Set, который дополнительно обеспечивает упорядочение по его элементам. |
| NavigableSet | Интерфейс SortedSet расширенный с помощью методов навигации, обеспечивающих поиск ближайших совпадений искомых элементов. |
| Queue | Очередь, предназначенна для хранения элементов перед обработкой. |
| Deque | Линейная коллекция, которая поддерживает вставку и удаление элементов на обоих концах. |
| Map | Отображение. Объект, который сопоставляет ключи со значениями. |
| SortedMap | Отображение, которое дополнительно обеспечивает упорядочивание по ключам. |
| NavigableMap | Интерфейс SortedMap расширенный с помощью методов навигации, обеспечивающих поиск ближайших совпадений искомых элементов. |
| Iterator | Итератор по коллекции. |
| ListIterator | Итератор для списков, который позволяет программисту перемещаться по списку в любом направлении, изменять список во время итерации и получать текущее положение итератора в списке. |
| RandomAccess | Маркерный интерфейс, используемый реализациями списков для указания на то, что они поддерживают быстрый (обычно постоянный по времени) произвольный доступ. |
| Интерфейс | Описание |
|---|---|
| Cloneable | Позволяет классам, реализующим интерфейс, сделать копию экземпляра класса. |
| Serializable | Интерфейс позволяет классу быть сериализованным, это означает что объект класса может быть преобразован в последовательность бит или байт для передачи по сети. |
Интерфейс Map
Отображение. Структура данных для хранения связанных вместе пар “ключ-значение”.
public interface Map
Вложенные классы
| Класс | Описание |
|---|---|
| static interface Map.Entry | Запись отображения (пара ключ-значение отображения). Получается с помощью метода Map.entrySet() |
| Метод | Описание |
|---|---|
| K getKey() | Возвращает ключ соответствующий данной записи. |
| V getValue() | Возвращает значение соответствующее данной записи. |
| V setValue(V value) | Заменяет значение соответствующее этой записи на указанное значение (опциональная операция). |
Методы
Наиболее общие реализации сведены в следующей таблице:
| Interface | Hash Table | Resizable Array | Balanced Tree | Linked List | Hash Table + Linked List |
|---|---|---|---|---|---|
| Set | HashSet | TreeSet | LinkedHashSet | ||
| List | ArrayList | LinkedList | |||
| Deque | ArrayDeque | LinkedList | |||
| Map | HashMap | TreeMap | LinkedHashMap |
Свойства коллекций
Временная сложность
| Среднее | Индекс | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(n) | O(n) |
| Vector | O(1) | O(n) | O(n) | O(n) |
| LinkedList | O(n) | O(n) | O(1) | O(1) |
| Hashtable | n/a | O(1) | O(1) | O(1) |
| HashMap | n/a | O(1) | O(1) | O(1) |
| LinkedHashMap | n/a | O(1) | O(1) | O(1) |
| TreeMap | n/a | O(log(n)) | O(log(n)) | O(log(n)) |
| HashSet | n/a | O(1) | O(1) | O(1) |
| LinkedHashSet | n/a | O(1) | O(1) | O(1) |
| TreeSet | n/a | O(log(n)) | O(log(n)) | O(log(n)) |
| Худшее | Индекс | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(n) | O(n) |
| Vector | O(1) | O(n) | O(n) | O(n) |
| LinkedList | O(n) | O(n) | O(1) | O(1) |
| Hashtable | n/a | O(n) | O(n) | O(n) |
| HashMap | n/a | O(n) | O(n) | O(n) |
| LinkedHashMap | n/a | O(n) | O(n) | O(n) |
| TreeMap | n/a | O(log(n)) | O(log(n)) | O(log(n)) |
| HashSet | n/a | O(n) | O(n) | O(n) |
| LinkedHashSet | n/a | O(n) | O(n) | O(n) |
| TreeSet | n/a | O(log(n)) | O(log(n)) | O(log(n)) |
ArrayList
Является реализацией динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Реализация основана на обычном массиве.
Следует применять, если в процессе работы с коллекцией предполагается частое обращение к элементам по индексу.
Не рекомендуется применять, если требуется частое удаление/добавление элементов в середину коллекции.
Пример использования ArrayList
Ссылки
LinkedList
Пример использования LinkedList
Ссылки:
HashSet
Пример использования хэш-множества HashSet
Ссылки:
TreeSet
Древовидное множество. Хранит отсортированную коллекцию в виде структуры красно-черного дерева.
Пример использования TreeSet
Ссылки:
EnumSet
Специализированное множество используется с типами enum (перечислениями).
Для реализации использует битовую последовательность. В каждом бите устанавливается 1, если соответствующее значение перечисления присутствует в множестве. Все методы в EnumSet реализованы с использованием арифметических побитовых операций. Эти вычисления очень быстрые, и поэтому все основные операции выполняются за постоянное время. Если сравнивать EnumSet с другими реализациями Set то он обычно быстрее, потому что значения хранятся в предсказуемом порядке, и для каждого вычисления необходимо проверять только один бит. В отличие от HashSet, нет необходимости вычислять hashcode, чтобы найти правильный сегмент. EnumSet очень компактен и эффективен. Следовательно, использует меньше памяти.
EnumSet следует использовать, когда мы храним значения enum в множестве.
Пример использования EnumSet
Ссылки:
LinkedHashSet
Множество сохраняющее значения в хэш таблицу в виде связанного списка с сохранением порядка ввода.
Сравнение LinkedHashSet и HashSet
Сравнение LinkedHashSet и TreeSet
Ссылки:
ArrayDeque
Двусторонняя очередь. Массив с изменяющимся размером, реализующий интерфейс Deque.
Сравнение ArrayDeque и LinkedList
Использование в качестве стэка
Ссылки:
PriorityQueue
Очередь по приоритету возвращает элементы в отсортированном порядке, после того как они были введены в произвольном порядке.
Например, мы хотим получить элементы в порядке возрастания. В этом случае голова очереди будет указывать на наименьший элемент. Когда элемент будет получен, следующий наименьший элемент станет головой очереди.
Элементы приоритетной очереди могут быть не отсортированы, однако элементы возвращаются в отсортированном порядке.
Ссылки:
HashMap
Отображение. Структура данных для хранения связанных вместе пар “ключ-значение”. Хэширует только ключи, значения не хэшируются. Хэширование выполняется немного быстрее, чем вставка в дерево, поэтому данные отображение используется, когда не требуется отсортированный порядок ключей.
Ссылки:
TreeMap
Отображение. Структура данных для хранения связанных вместе пар “ключ-значение”. Использует хранение ключей в виде дерева для поиска. Функция сравнения для вставки в дерево используется только для ключей, значения не сравниваются.
Ссылки:
WeakHashMap
Отображение основанное на хэш таблицах со слабыми ключами. Записи в нем автоматически будут удалены системой сборки “мусора”, если ключ не используется (на него нет ссылок, кроме WeakHashMap), при удалении ключа также будет удалено связанное значение.
Сравнение WeakHashMap и HashMap
Ссылки:
LinkedHashMap
Отображение основанное на хэш-таблицах с сохранением порядка ввода элементов или порядка доступа к элементам в двунаправленном связанном списке. Порядок доступа может быть использован при реализации кэширования с “наиболее давним использованием”. Сохраняются часто используемые элементы, а при заполнении удаляется наиболее старый элемент.
Сравнение LinkedHashMap и HashMap
Оба LinkedHashMap и HashMap реализуют интерфейс Map. Однако, существуют некоторые отличия между ними.
Ссылки:
EnumMap
Класс EnumMap специализированная реализация Map для использования типа enum в качестве ключей. Все ключи должны иметь один тип enum который явно или неявно указан при создании отображения. Внутри данный класс реализован как массивы. Такая реализация очень компактна и эффективна.
Ссылки:
IdentityHashMap
Этот класс не является реализацией общего назначения интерфейса Map! Хотя этот класс реализует интерфейс Map, он намеренно нарушает общее соглашение, которое предписывает использование метода equals() при сравнении объектов. Этот класс используется только когда требуется семантика равенства ссылок.
Класс IdentityHashMap используется, когда хэш-значения ключей должны вычисляться не методом hashCode(), а методом System.identityHashCode(). В данном методе вычисление хэш-кода происходит исходя из адреса объекта в памяти. Для сравнения объектов типа IdentityHashMap используется операция ==, а не метод equals().
Ссылки:
Представления и оболочки
Представлением называется объект реализующий интерфейс коллекции методы которого управляют исходной коллекцией.
Поддиапазоны
headSet()
tailSet()
headMap()
tailMap()
Немодифицируемые представления
В классе Collections есть методы, которые создают немодифицируемые представления коллекций. Данные представления производят динамическую проверку попытки изменить коллекцию и генерируют исключение.
Синхронизированные представления
Если обращение к коллекции происходит из нескольких потоков, то нужно исключить ее повреждение. Вместо реализации потокобезопасных классов был использован механизм представлений, чтобы сделать потокобезопасными обычные коллекции.
Проверяемые представления
Предназначены для отладки ошибок, возникающих при применении обобщенных типов. При несоответствии типа генерируется исключение типа ClassCastException.
Прочее
Сортировка и перестановка
Двоичный поиск
Алгоритмы
Взаимное преобразование коллекций и массивов
Преобразование массива в коллекцию
Преобразование коллекции в массив
В интерфейсе Interface Collection есть следующие методы:
Унаследованные коллекции
В первом выпуске java появились коллекции, применявшиеся до появления фреймворка коллекций. Они были добавлены в фреймворк коллекций.
Иерархия унаследованных классов коллекций Hashtable, Properties 
Иерархия унаследованных классов коллекций Vector, Stack 
Использование пар в Java
Узнайте, как реализовать функции сопряжения в Java.
1. Обзор
Простая реализация Пары доступна в основных библиотеках Java. Кроме того, некоторые сторонние библиотеки, такие как Apache Commons и другие, предоставили эту функциональность в своих соответствующих API.
Дальнейшее чтение:
Хэш-карта Java Под капотом
Выполните итерацию по карте на Java
Java – Объединение Нескольких Коллекций
2. Основная Реализация Java
2.1. Класс Пар
Этот пример иллюстрирует простой Целое число в Строку сопоставление с использованием концепции пар.
2.2. Абстрактная карта.SimpleEntry и АбстрактНая карта.SimpleImmutableEntry
Доступ к ключу и значению можно получить с помощью стандартных методов получения и настройки.
Кроме того, класс AbstractMap также содержит вложенный класс, представляющий неизменяемую пару, класс SimpleImmutableEntry :
3. Общие ресурсы Apache
В библиотеке Apache Commons мы можем найти класс Pair в пакете org.apache.commons.lang3.tuple|/. Это абстрактный класс, поэтому его нельзя создать напрямую.
Здесь мы можем найти два подкласса, представляющих неизменяемые и изменяемые пары, Imm utable Пара и Изменяемая пара.
Обе реализации имеют доступ к методам получения/установки ключей/значений:
Неудивительно, что попытка призвать Значение SET() на Неизменная пара приводит к Исключение UnsupportedOperationException.
Однако операция полностью допустима для изменяемой реализации:
4. Вавр
В библиотеке Vavr функция сопряжения обеспечивается неизменяемым классом Tuple2 :
В этой реализации мы не можем изменить объект после создания, поэтому мутирующие методы возвращают новый экземпляр, содержащий указанное изменение:
5. Альтернатива I – Класс Простых Контейнеров
Либо по предпочтениям пользователя, либо в отсутствие какой-либо из вышеупомянутых библиотек стандартным обходным путем для функции сопряжения является создание простого контейнерного класса, который обертывает желаемые возвращаемые значения.
Самым большим преимуществом здесь является возможность указать наше имя, что помогает избежать наличия одного и того же класса, представляющего разные объекты домена:
6. Альтернатива II – Массивы
Другим распространенным обходным путем является использование простого массива с двумя элементами для достижения аналогичных результатов:
Как правило, ключ находится в нулевом индексе массива, в то время как его соответствующее значение находится в первом индексе.
7. Заключение
В этой статье мы обсудили концепцию Пар в Java и различные реализации, доступные в основной Java, а также в других сторонних библиотеках.
