какие существуют реализации map

Ответы на самые популярные вопросы об интерфейсе Map

0. Как перебрать все значения Map

1. Как конвертировать Map в List

2. Как отсортировать ключи мапы

Поместить Map.Entry в список и отсортировать его, используя Comparator.

В компараторе будем сравнивать исключительно ключи пар:

Если разобрался с лямбдами, эту запись можно существенно сократить:

И, конечно, все можно переписать, используя лямбды:

В отличие от первого способа, используя SortedMap, мы всегда будем хранить данные в отсортированном виде.

3. Как отсортировать значения мапы

4. В чем разница между HashMap, TreeMap, и Hashtable

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

Допустимые значения. HashMap позволяет иметь ключ и значение null, HashTable — нет. TreeMap может использовать значения null только если это позволяет компаратор. Без использования компаратора (при хранении пар в порядке добавления) значение null не допускается.

Синхронизация. Только HashTable синхронизирована, остальные — нет. Если к мапе не будут обращаться разные потоки, рекомендуется использовать HashMap вместо HashTable.

И общее сравнение реализаций:

5. Как создать двунаправленную мапу

6. Как создать пустую Map

Обычная инициализация объекта:

Создание неизменяемой (immutable) пустой мапы:

Источник

Какие существуют реализации map

В интерфейсе java.util.Map параметризуются два типа, это ключ и значение.

Объявление java.util.Map выглядит как:

При этом стоит отметить, что не может быть повторяющихся ключей, что следует из названия и смысла Map : каждому ключу соответствует значение.

Вопрос:

Ответ:

Класс java.util.Dictionary является полностью абтрактным, без какого-либо состояния.

Но благодаря WORA в Java просто так ничего не меняют и не удаляют, поэтому старые классы остались, а новую иерархию начали строить с интерфейсов.

Основные методы, которые предоставляет интерфейс java.util.Map :

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

Как уже было сказано выше, Map это набор пар ключ-значение.

Объявление java.util.Map#Entry выглядит как:

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

Помимо всего прочего предоставляются также компараторы для сравнения пар по ключу и значению.

Объявление выглядит следующим образом:

Объявление выглядит следующим образом:

Иерархия классов выглядит следующим образом:

Абстрактный класс java.util.AbstractMap предоставляет заготовку для последующих реализаций.

Что говорит о том, что операция не поддерживется и ее надо либо не использовать, либо переопределить метод.

Наиболее известные реализации java.util.Map :

Когда и какую реализацию выбрать?

Если порядок хранения элементов не важен, то выбор java.util.HashMap более чем оправдан.

Помните, что java.util.TreeMap не поддерживает работу с null ключами.

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

Стоит помнить, что, как и в случае с итерированием сипсков, если в ходе работы итератора структура данных была изменена (без использования методов итератора), то будет выброшено исключение:

Избежать этого можно удаляя элемент с помощью итератора, с которым происходит работа:

Источник

Map в Java с примерами

В статье о коллекциях я обещал написать статью о Map в Java. Сейчас мы подробно разберем эту очень полезную и нужную структуру данных с примерами кода.

Когда мы слышим слово мап, то первое, что приходит на ум — это карта (у меня гугл мапс). Map как структура данных не имеет ничего общего с картами гугла.

Чтобы правильно понять, что такое мап вспомните поликлинику. Да, воспоминания не очень. Но, нам нужно только вспомнить регистратуру, когда для приема у врача нам сначала нужно выстоять здоровенную очередь за своей картой. Не знаю как там в Европе, но для граждан стран СНГ это знакомо. Мы приходим, говорим свои данные и получаем карточку. Если же мы приходим впервые, нас регистрируют и только потом выдают карточку. Как правило карты находятся в алфавитном порядке и «милой» тете с регистратуры ее не сложно найти.

Иерархия классов Map немного похожа на Set:

HashMap — хранит ключи в hash-таблице. Она имеет наибольшую производительность. Однако такая реализация не гарантирует порядок элементов.

TreeMap — хранит ключи в отсортированном порядке. Работает медленнее чем хэшмап.

LinkedHashMap — хранит ключи в порядке их вставки в мап. Работает немного медленнее чем HashMap.

WeakHashMap — реализация интерфейса Map на основе хэш-таблицы со слабыми ключами. Запись в WeakHashMap будет автоматически удалена, если ее ключ больше не используется обычным образом.

Рассмотрим подробнее HashMap. Скорость ее работы О(1), а в худшем случае O(logn). Чтобы понять, когда будет худший случай давайте разберемся как она работает. Это, кстати, очень популярный вопрос на собеседованиях.

У каждого объекта есть метод hashCode, который возвращает значение хэш кода. Когда мы помещаем объект в HashMap сначала определяется значение hash кода его ключа, далее выбирается место, куда поместить объект в зависимости от полученного хэш кода. Если по такому ключу уже есть значение в мапе, то проверяется объект, который мы пытаемся добавить если он такой же как и существующий, то идет перезапись. Если объекты разные, а хэш код одинаковый (произошла коллизия или мы неправильно переопределили метод hashCode) объект помещается в ту самую ячейку в виде связанного списка. Вот откуда худший случай работы HashMap. Когда хэш код ключей одинаковый эта структура начинает работать как LinkedList скорость которого O(logn). Вы можете спросить: как нужно переопределить метод hashCode чтобы он возвращал одинаковое значение для всех объектов? Вот пример:

public class MapExamples <

private String name ;
private double sum ;

@Override
public int hashCode ( ) <
return 1 ;
>

Да, нужно постараться, чтобы такое сделать, но все же.

Теперь перейдем к примеру. Будут рассмотрены только самые популярные методы. Они у всех реализациях одинаковы.

import java.util.HashMap ;
import java.util.Map ;

public class MapExamples <

Что еще хотелось бы упомянуть о Map в java:

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

Источник

О реализации структуры данных Map в V8

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

Прежде чем мы начнём, хочу отметить, что то, о чём речь пойдёт ниже, относится к движку V8 8.4, который встроен в свежую dev-версию Node.js (если точнее, то речь идёт о коммите 238104c). Вам не нужно ожидать чего-то, выходящего за пределы спецификации.

Алгоритм, лежащий в основе реализации Map

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

V8 использует так называемые «детерминированные хеш-таблицы», предложенные Тайлером Клоузом. Следующий псевдокод, основанный на TypeScript, демонстрирует основные структуры данных, используемые при реализации таких хеш-таблиц:

А теперь — последний кусочек нашей головоломки. Когда таблица оказывается полна записей (и актуальных, и удалённых), она должна быть перехеширована (перестроена) с увеличением её размера. Размер таблицы может быть изменён и в сторону уменьшения.

Практическое исследование алгоритма

Давайте рассмотрим несколько примеров, позволяющих нам исследовать алгоритм на практике. Предположим, у нас имеется CloseTable с 2 хеш-контейнерами ( hastTable.length ), общая ёмкость которой составляет 4 элемента ( dataTable.length ). Эту таблицу заполняют следующим содержимым:

Внутреннее представление таблицы, получившейся в этом примере, может выглядеть так:

Если мы добавим в таблицу ещё пару записей, то она будет нуждаться в перехешировании. Этот процесс мы подробно обсудим немного ниже.

Теперь, когда мы разобрались с тем, что стоит за объектами Map в V8, мы готовы к тому, чтобы двинуться дальше.

Детали реализации

Так как нас особенно интересуют практические подробности о реализации Map в V8, нам, для начала, надо понять то, как задаётся ёмкость таблицы.

Ёмкость таблицы

В V8 ёмкость хеш-таблицы (структуры данных Map ) всегда равна некоей степени двойки. Если говорить о коэффициенте использования хеш-контейнеров, то он всегда представлен числом 2. То есть, максимальная ёмкость таблицы — это 2 * number_of_buckets — 2, умноженное на количество хеш-контейнеров. При создании пустого объекта Map в его внутренней хеш-таблице имеется 2 хеш-контейнера. В результате ёмкость такого объекта равняется 4 записям.

И наконец, коэффициент увеличения или уменьшения таблицы тоже всегда представлен произведением некоего числа на 2. Это значит, что после того, как в описываемую таблицу будет добавлено 4 записи, следующая операция вставки вызовет необходимость в перехешировании таблицы, в ходе которого размер таблицы увеличится в два раза. При уменьшении размеров таблицы, она, соответственно, может стать в 2 раза меньше.

Этот скрипт просто вставляет в структуру данных Map 100 записей. Вот что выводится в консоли после его запуска:

Как видно, когда таблица заполняется, то, при каждом изменении её размера, она увеличивается в 2 раза. Попробуем теперь добиться уменьшения таблицы, удаляя из неё элементы:

Вот что выведет этот скрипт:

Тут, опять же, видно, что размер таблицы уменьшается каждый раз, когда в ней оказывается меньше чем number_of_buckets / 2 элементов.

Хеш-функция

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

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

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

Временная сложность операций с объектами Map

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

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

Потребление памяти

Массив, используемый для хранения структур данных Map в памяти

Отдельные части массива имеют следующее назначение:

Итоги

В этом материале мы разобрали много всего, имеющего отношение к структуре данных Map в JavaScript. Подведём итоги:

Источник

Справочник по Java Collections Framework

Данная публикация не является полным разбором или анализом (не покрывает пакет java.util.concurrent ). Это, скорее, справочник, который поможет начинающим разработчикам понять ключевые отличия одних коллекций от других, а более опытным разработчикам просто освежить материал в памяти.

Что такое Java Collections Framework?

Java Collection Framework — иерархия интерфейсов и их реализаций, которая является частью JDK и позволяет разработчику пользоваться большим количесвом структур данных из «коробки».

Базовые понятия

Интерфейс Map [doc]

Hashtable — реализация такой структуры данных, как хэш-таблица. Она не позволяет использовать null в качестве значения или ключа. Эта коллекция была реализована раньше, чем Java Collection Framework, но в последствии была включена в его состав. Как и другие коллекции из Java 1.0, Hashtable является синхронизированной (почти все методы помечены как synchronized ). Из-за этой особенности у неё имеются существенные проблемы с производительностью и, начиная с Java 1.2, в большинстве случаев рекомендуется использовать другие реализации интерфейса Map ввиду отсутствия у них синхронизации.

WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references. Другими словами, Garbage Collector автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элеметна нет жёстких ссылок.

Интерфейс List [doc]

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

ArrayList — как и Vector является реализацией динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Как можно догадаться из названия, его реализация основана на обычном массиве. Данную реализацию следует применять, если в процессе работы с коллекцией предплагается частое обращение к элементам по индексу. Из-за особенностей реализации поиндексное обращение к элементам выполняется за константное время O(1). Но данную коллекцию рекомендуется избегать, если требуется частое удаление/добавление элементов в середину коллекции. Подробный анализ и описание можно почитать в этом хабратопике.

Интерфейс Set [doc]

Представляет собой неупорядоченную коллекцию, которая не может содержать дублирующиеся данные. Является программной моделью математического понятия «множество».

Интерфейс Queue [doc]

Этот интерфейс описывает коллекции с предопределённым способом вставки и извлечения элементов, а именно — очереди FIFO (first-in-first-out). Помимо методов, определённых в интерфейсе Collection, определяет дополнительные методы для извлечения и добавления элементов в очередь. Большинство реализаций данного интерфейса находится в пакете java.util.concurrent и подробно рассматриваются в данном обзоре.

Заключение

Java Collections Framework содержит большое количество различных структур данных, доступных в JDK «из коробки», которые в большинстве случаев покрывают все потребности при реализации логики приложения. Сравнение временных характеристик основных коллекций, которые зачастую используются в разработке приложений приведено в таблице:

При необходимости, разработчик может создать собственную реализацию, расширив или переопределив существующую логику, либо создав свою собственную реализацию подходящего интерфейса с нуля. Также существует некоторое количество готовых решений, которые являются альтернативой или дополнением к Java Collections Framework. Наиболее популярными являются Google Guava и Commons Collections.

Источник