Java dictionary или map

Коллекции: list, set, map

Под коллекциями в программировании подразумевают объекты, которые хранят внутри себя какой-либо набор значений и предоставляют набор методов для обращения к этим значениям. В Java можно выделить 3 наиболее часто используемых типа коллекций: списки (list), наборы (set) и словари (map). При объявлении коллекции типизируются каким-либо типом, т.е. одна коллекция хранит данные одного типа.

Список (list)

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

List list = new ArrayList<>();
list.add( «яблоко» );
list.add( «ананас» );
list.add( «яблоко» );
System.out.println(list); // На экране увидим: [яблоко, ананас, яблоко]

Две наиболее частые реализации интерфейса List – это ArrayList и LinkedList.

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

Класс LinkedList представляет собой цепочку элементов, в которой каждый элемент имеет ссылку на предыдущий элемент и на следующий. Также имеется ссылка на начало и на конец списка, что позволяет быстро получать доступ к первому и к последнему элементу. При этом для доступа по индексу требуется пройтись последовательно по всей цепочке, поэтому время доступа по индексу прямо пропорционально размеру списка. Однако сам процесс добавления и удаления элементов весьма прост: нужно всего лишь изменить пару ссылок.

Казалось бы, у каждой реализации списка свои плюсы и минусы, однако в последних версиях Java ArrayList был достаточно хорошо оптимизирован и на практике можно всё время выбирать его без ущерба для производительности в любых задачах.

Набор (set)

Интерфейс Set представляет собой набор уникальных значений и тоже наследуется от Collection. У этого интерфейса есть несколько реализаций, но каждая из них гарантирует, что каждое значение в наборе уникально.

Сравнение любых двух объектов между собой в Java происходит при помощи методов equals() и hashCode() из базового класса Object. Метод equals выполняет полное сравнение элементов, тогда как hashCode только лишь вычисляет хеш-функцию, которая может принимать одинаковые значения для разных элементов. Соотношение между этими двумя методами всегда такое: если для двух объектов hashCode возвращает одинаковое значение, то equals при этом может быть false, однако если equals возвращает true, то hashCode обязан возвращать одинаковые значения. При создании собственных классов, если их предполагается использовать в наборах или словарях, вы должны переопределить эти два метода, чтобы коллекции работали с ними корректно.

Теперь рассмотрим три основные реализации интерфейса Set.

Первая из них – это HashSet. Когда мы будет выполнять проход по этому набору, то порядок элементов на первый взгляд нам покажется хаотичным. Однако на самом деле он будет зависеть от значения хэш-функции для каждого элемента. Также обратите внимание, что мы два раза добавляем «яблоко» в набор, однако в результате увидим его только один раз.

Set hashSet = new HashSet<>();
hashSet.add( «яблоко» );
hashSet.add( «яблоко» ); // дубль
hashSet.add( «ананас» );
hashSet.add( «банан» );
System.out.println(hashSet); // На экране увидим: [банан, яблоко, ананас]

Следующая реализация – это LinkedHashSet, которая расширяет предыдущую. Основное различие заключается в том, что при обходе элементов мы будем видеть их в порядке добавления:

Set linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add( «яблоко» );
linkedHashSet.add( «яблоко» );
linkedHashSet.add( «ананас» );
linkedHashSet.add( «банан» );
System.out.println(linkedHashSet); // [яблоко, ананас, банан]

Ну а третья реализация под названием TreeSet имеет в своей основе структуру данных «красно-чёрное дерево», что позволяет сортировать элементы автоматически:

Set treeSet = new TreeSet<>();
treeSet.add( «яблоко» );
treeSet.add( «яблоко» );
treeSet.add( «ананас» );
treeSet.add( «банан» );
System.out.println(treeSet); // [ананас, банан, яблоко]

Поэтому если хотите сохранять порядок добавления элементов – используйте LinkedHashSet, а если хотите получить отсортированный набор – тогда используйте TreeSet.

Словарь (map)

Интерфейс Map представляет собой набор из пар элементов типа «ключ-значение». На русский язык это переводят по-разному: карта, маппинг, хэш-таблица. Но мне больше всего нравится аналогия со словарём, так как с этим набором мы примерно так и работаем: имеем какое-то слово (ключ) и пытаемся найти его перевод (значение).

Словарь гарантирует, что каждому ключу соответствует одно и только одно значение. Если по уже существующему ключу положить новое значение, то оно перезатрёт старое. При работе с ключами также используются методы equals и hashCode. И по аналогии с Set здесь мы также имеем три основных реализации интерфейса Map.

Первая реализация – это HashMap, которая не гарантирует никакого порядка элементов при обходе. Обратите внимание, что при повторном добавлении элемента с тем же ключом, мы теряем первое значение:

Map hashMap = new HashMap<>();
hashMap.put( «яблоко» , 1 );
hashMap.put( «яблоко» , 2 ); // повторное добавление
hashMap.put( «ананас» , 3 );
hashMap.put( «банан» , 4 );
System.out.println(hashMap); // На экране увидим:

Ещё одна реализация – это LinkedHashMap, которая сохраняет порядок добавления:

Map linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put( «яблоко» , 1 );
linkedHashMap.put( «яблоко» , 2 );
linkedHashMap.put( «ананас» , 3 );
linkedHashMap.put( «банан» , 4 );
System.out.println(linkedHashMap); //

Ну и третья популярная реализация интерфейса Map – это TreeMap, которая сортирует ключи по порядку:

Map treeMap = new TreeMap<>();
treeMap.put( «яблоко» , 1 );
treeMap.put( «яблоко» , 2 );
treeMap.put( «ананас» , 3 );
treeMap.put( «банан» , 4 );
System.out.println(treeMap); //

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

Источник

Map Vs Dictionary

posted 11 years ago

I know Dictionary has been unoffficially deprecated. But comparing Map & DIctionary, I can’t find any differences.
Is there a basic design difference i missed?
Also since now its unofficially deprecated, doesn’t it means we should not be encouraged to use HashTable and use ConcurrentHashMap instead.

Bartender

posted 11 years ago

• 1

sumit anand kumar wrote: I know Dictionary has been unoffficially deprecated. But comparing Map & DIctionary, I can’t find any differences.
Is there a basic design difference i missed?

Dictionary is an abstract class. Map is an interface.

Dictionary uses classes and methods that predate the Collections Framework. Map uses classes and methods that were created to be part of the Collections Framework from the ground up.

Источник

Java Collections Framework

Практически во всех программах возникает потребность хранить набор каких-либо данных. Это могут быть строки и числа, объекты и т.п. Для этих целей как нельзя кстати подходят массивы. Но у массивов есть некоторые ограничения. Например, фиксированный размер, отсутствие возможности удалять элементы, вставлять элементы в середину. Для обхода этого и других ограничений создали коллекции. Во всех типах коллекций (а их много, как мы увидим далее по ходу этой лекции), есть возможность динамически изменять свой размер. Некоторые типы коллекций могут хранить упорядоченные элементы и автоматически упорядочивать новые элементы по мере их добавления.

В этой лекции мы ознакомимся с иерархией классов базовых коллекций Java Collections Framework . Еще существуют различные альтернативные библиотеки, которые расширяют возможности стандартной Java Collections Framework . Наиболее популярная из них — Guava (Google Collections Library).

* На схеме представлены далеко не все интерфейсы и классы. Некоторые упущены для простоты понимания

Основные интерфейсы

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

Давай рассмотрим эти интерфейсы:

1. Collection – обычная коллекция, которая содержит набор отдельных элементов (объектов). В этой коллекции есть основные методы для работы с элементами: вставка ( add , addAll ), удаление ( remove , removeAll , clear ), поиск ( contains , containsAll ), проверка на пустоту коллекции ( isEmpty ) и размер ( size ).
2. Map — коллекция, структура которой представляет собой пары «ключ — значение». Причем в рамках одной Map каждый ключ уникален: нет двух одинаковых по значению ключей. Также эту коллекцию иногда называют словарем (dictionary). Map — это отдельный интерфейс. Он не реализует интерфейс Collection , но входит в Java Collections Framework .

Основные методы для работы с элементами Map :

• вставка ( put , putAll )
• получение ( get , keySet , values , entrySet )
• удаление ( remove , clear )
• поиск ( containsKey , containsValue )
• проверка на пустоту коллекции ( isEmpty )
• размер ( size )

А теперь давай подробнее поговорим о каждом из них.

Интерфейс Collection

Интерфейс Collection расширяет интерфейс Iterable , а у этого интерфейса есть единственный метод iterator() . Для нас это означает, что любая коллекция, которая наследуется от Iterable , будет уметь возвращать итератор.

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

Из рисунка видно, что от интерфейса Collection наследуется 3 интерфейса: List , Queue и Set . Сейчас кратко рассмотрим каждый из них.

List — это упорядоченная коллекция, допускающая дубликаты среди значений. Также можно встретить и другие название — последовательность (sequence), список. Особенностью List является то, что элементы пронумерованы и к ним можно обращаться по номеру (индексу).

Queue — переводится с английского как очередь. Правильное произношение: Queue — КЬЮ. В Queue элементы хранятся в порядке добавления их в очередь.

Set – в отличие от списка, описывает неупорядоченную коллекцию, в которой нет повторов элементов. У Set есть соответствие с понятием в математике — м множество (set).

Реализации интерфейса Map

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

где К — это тип ключей, а V — тип хранимых значений.

По ключу мы можем извлекать данные из Map . Для добавления элемента в Map нужно задать ключ и значение.

Рассмотрим некоторые реализации Map :

1. HashMap — реализация Map , в основе которой лежат хэш-таблицы. Может хранить ключи и значения любых типов, в том числе и null . Порядок элементов не гарантирован.
2. LinkedHashMap — структура данных, хранит данные в виде связного списка элементов. Элементы расположены в том порядке, в котором они добавлялись.
3. TreeMap — реализует интерфейс SortedMap (через NavigableMap ). Элементы в такой структуре хранятся в отсортированном виде (при добавлении нового элемента коллекция сортируется автоматически). TreeMap отлично подходит для хранения больших объемов отсортированной информации с осуществлением быстрого поиска.

Устаревшие коллекции

От прошлых версий Java остались устаревшие коллекции (для поддержания обратной совместимости), которые использовать не рекомендуется:

• Enumeration — аналог интерфейса Iterator ;
• Vector — упорядоченный список элементов, аналог класса ArrayList ;
• Stack — структура, которая реализует хранение элементов по принципу стека (например, стопка книг), есть методы вталкивания (push) и выталкивания (pop) элементов;
• Dictionary — аналог интерфейса Map , но является абстрактным классом;
• Hashtable — аналог HashMap .

Подробнее о Collections Framework ты можешь прочесть в этой статье.

Источник