Интерфейс Map и его классы.
1. Что из себя представляет интерфейс Map?
|
M ap предоставляет разработчику базовые методы для работы с данными вида «ключ — значение» то есть по парам. И в качестве ключей, и в качестве значений могут выступать любые объекты — числа, строки или объекты других классов. Также как и Collection, он был дополнен дженериками в версии Java 1.5 и в версии Java 8 появились дополнительные методы для работы с лямбдами, а также методы, которые зачастую реализовались в логике приложения (getOrDefault(Object key, V defaultValue), putIfAbsent(K key, V value)).
|
2. Какие классы расширяют интерфейс Map? (4 класса)
|
- Hashtable — хэш-таблица, методы которой синхронизированы. Не позволяет использовать null в качестве значения или ключа и не является упорядоченной.
- HashMap — хэш-таблица. Позволяет использовать null в качестве значения или ключа и не является синхронизированной.
- LinkedHashMap — упорядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap, порядок итерирования равен порядку добавления элементов. Расширяет HashMap.
- TreeMap — реализация, основанная на красно-чёрных деревьях. Является упорядоченной и по-умолчанию, коллекция сортируется по ключам с использованием принципа "natural ordering", но это поведение может быть настроено под конкретную задачу при помощи объекта Comparator, который указывается в качестве параметра при создании объекта TreeMap.
- WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references для ключей (сборщик мусора автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элемента нет жёстких ссылок).
|
3. Какие методы у Map? (13 штук)
|
- clear() - Удаляет все элементы в мапе.
- clone() - Возвращает мелкую копию этого экземпляра HashMap: ключи и сами значения не клонируются.
- containsKey(Object key) - проверяет наличие какого-то ключа.
- containsValue(Object value) - проверяет наличие значения.
- entrySet() - Возвращает в Set представлении список всех пар в нашей HashMap.
- get(Object key) - Возвращает значение, на которое указанный ключ отображается, или null если эта карта не содержит отображения для ключа.
- isEmpty() – Для проверки того, есть ли в нашей HashMap хотя бы один элемент.
- keySet() - Возвращает в Set представлении список всех ключей, содержащихся в этой мапе.
- put(K key, V value) - Связывает указанное значение с указанным ключом в этой карте.
- putAll(Map m) - Две мапы объединить в одну.
- remove(Object key) - Удаляет отображение для указанного ключа из этой карты если существующий.
- size() - возвращает число элементов в мапе на текущий момент
- values() - Возвращает в Collection представлении список всех значений, содержащихся в этой мапе.
|
4. Почему Map — это не Collection, в то время как List и Set являются Collection?
|
Collection представляет собой совокупность некоторых элементов. Map — это совокупность пар «ключ-значение». Её официальное русское название — “ассоциативный массив”
|
5. Как устроен класс TreeMap?
|
И мплементируя интерфейсы NavigableMap и SortedMap, TreeMap получает дополнительный функционал, которого нет в HashMap, но плата за это — производительность.
TreeMap использует структуру данных, которая называется красно-чёрное дерево.
В реализации TreeMap, добавляется конструктор, который принимает экземпляр компаратора. Этот компаратор и будет отвечать за порядок хранения элементов.
|
6. Красно-Чёрное дерево. Что это? (структура данных)
|
Поиск нужного элемента начинается из корня дерева, в нашем случае это 61. Дальше происходит сравнение с необходимым значением. Если наше значение меньше — отправляемся в левую сторону, если больше — в правую. Так происходит до тех пор, пока не найдем необходимое значение или не упремся в элемент со значением null (листок дерева). Красные и черные цвета используются для упрощения навигации по дереву и его балансировки. Существуют правила, которые всегда должны быть соблюдены при постройке красно-чёрного дерева:
- Корень должен быть окрашен в черный цвет.
- Листья дерева должны быть черного цвета.
- Красный узел должен иметь два чёрных дочерних узла.
- Чёрный узел может иметь любые дочерние узлы.
- Путь от узла к его листьям должен содержать одинаковое количество чёрных узлов.
- Новые узлы добавляются на места листьев.
Если посмотреть на правила 3, 4 и 5 в совокупности, можно понять, как окраска узлов ускоряет навигацию по дереву: путь через чёрные узлы всегда короче, чем через красные. Поэтому по количеству чёрных узлов определяется общий размер дерева, и называется этот размер “чёрная высота”.
Подробнее можно прочитать тут!
|
7. Интерфейсы SortedMap и NavigableMap. Их методы реализованные в TreeMap
|
SortedMap — интерфейс, который расширяет Map и добавляет методы, актуальные для отсортированного набора данных:
- firstKey(): возвращает ключ первого элемента мапы;
- lastKey(): возвращает ключ последнего элемента;
- headMap(K end): возвращает мапу, которая содержит все элементы текущей, от начала до элемента с ключом end;
- tailMap(K start): возвращает мапу, которая содержит все элементы текущей, начиная с элемента start и до конца;
- subMap(K start, K end): возвращает мапу, которая содержит все элементы текущей,начиная с элемента - - start и до элемента с ключом end.
NavigableMap — интерфейс, который расширяет SortedMap и добавляет методы для навигации между элементами мапы:
- firstEntry(): возвращает первый пару “ключ-значение”;
- lastEntry(): возвращает последнюю пару “ключ-значение”;
- pollFirstEntry(): возвращает и удаляет первую пару;
- pollLastEntry(): возвращает и удаляет последнюю пару;
- ceilingKey(K obj): возвращает наименьший ключ k, который больше или равен ключу obj. Если такого ключа нет, возвращает null;
- floorKey(K obj): возвращает самый большой ключ k, который меньше или равен ключу obj. Если такого ключа нет, возвращает null;
- lowerKey(K obj): возвращает наибольший ключ k, который меньше ключа obj. Если такого ключа нет, возвращает null;
- higherKey(K obj): возвращает наименьший ключ k, который больше ключа obj. Если такого ключа нет, возвращает null;
- ceilingEntry(K obj): аналогичен методу ceilingKey(K obj), только возвращает пару “ключ-значение” (или null);
- floorEntry(K obj): аналогичен методу floorKey(K obj), только возвращает пару “ключ-значение” (или null);
- lowerEntry(K obj): аналогичен методу lowerKey(K obj), только возвращает пару “ключ-значение” (или null);
- higherEntry(K obj): аналогичен методу higherKey(K obj), только возвращает пару “ключ-значение” (или null);
- descendingKeySet(): возвращает NavigableSet, содержащий все ключи, отсортированные в обратном порядке;
- descendingMap(): возвращает NavigableMap, содержащую все пары, отсортированные в обратном порядке;
- navigableKeySet(): возвращает объект NavigableSet, содержащий все ключи в порядке хранения;
- headMap(K upperBound, boolean incl): возвращает мапу, которая содержит пары от начала и до элемента upperBound. Аргумент incl указывает, нужно ли включать элемент upperBound в возвращаемую мапу;
- tailMap(K lowerBound, boolean incl): функционал похож на предыдущий метод, только возвращаются пары от lowerBound и до конца;
- subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): как и в предыдущих методах, возвращаются пары от lowerBound и до upperBound, аргументы lowIncl и highIncl указывают, включать ли граничные элементы в новую мапу.
|
8. Отличие TreeMap, HashMap и LinkedHashMap
|
H ashMap простая в использовании и гарантирует быстрый доступ к данным, поэтому это лучший кандидат для решения большинства задач. Большинства, но не всех. Иногда необходимо хранить данные в структурированном виде с возможностью навигации по ним. В таком случае на помощь приходит другая реализация интерфейса Map — TreeMap.
Поэтому если тебе не нужно хранить данные в отсортированном виде, лучше используй HashMap или LinkedHashMap.
|
9. Как устроен класс HashMap?
|
- Реализует интерфейс Map, Cloneable, Serializable и наследуется от абстрактного класса AbstractMap.
- Ключ в HashMap всегда является уникальным. Если поместить в мапу второй объект с ключом от первого объекта, то он перезапишется.
- Список всех ключей можно вывести из HashMap в отдельную коллекцию. (например, в коллекцию Set. Её особенность в том, что в ней не может быть повторяющихся элементов).
- Список всех ключей можно вывести из HashMap в отдельную коллекцию. (например, в обычную коллекцию ArrayList)
- Две мапы можно объединить в одну. putAll(). Мы вызываем его у первой HashMap, передаем вторую в качестве аргумента, и элементы из второй будут добавлены в первую:
- Класс HashMap имеет внутренний класс Entry, который хранит пары ключ-значение;
- Объекты класса Entry хранятся в массиве Entry[ ] под названием table;
- Node — это вложенный класс внутри HashMap
- Ячейка массива называется корзиной и хранит первый элемент;
- Метод hashcode() объекта key используется для поиска корзины этого объекта класса Entry;
- Если ключи двух объектов имеют одинаковый хэш-код, они будут сохранены в одной корзине массива table;
- Метод equals() объекта key используется для подтверждения его уникальности;
- Методы equals() и hashcode() объекта value вообще не используются.
|
10. Поля и константы класса HashMap?
|
Поля:
- transient Node < K, V> [] table – сама хеш-таблица, реализованная на основе массива, для хранения пар «ключ-значение» в виде узлов. Здесь хранятся наши Node;
- transient int size — количество пар «ключ-значение»;
- int threshold — предельное количество элементов, при достижении которого размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
- final float loadFactor — этот параметр отвечает за то, при какой степени загруженности текущей хеш-таблицы необходимо создавать новую хеш-таблицу, т.е. как только хеш-таблица заполнилась на 75%, будет создана новая хеш-таблица с перемещением в неё текущих элементов (затратная операция, так как требуется перехеширование всех элементов);
- transient Set< Map.Entry< K,V>> entrySet — содержит кешированный entrySet(), с помощью которого мы можем перебирать HashMap.
Константы:
- static final int DEFAULT_INITIAL_CAPACITY= 1 << 4 — ёмкость хеш-таблицы по умолчанию (16);
- static final int MAXIMUM_CAPACITY = 1 << 30 — максимально возможная ёмкость хеш-таблицы (приблизительно 1 млрд.);
- static final float DEFAULT_LOAD_FACTOR = 0.75f — коэффициент загрузки, используемый по умолчанию;
- static final int TREEIFY_THRESHOLD = 8 — это «порог» количества элементов в одной корзине, при достижении которого внутренний связный список будет преобразован в древовидную структуру (красно-черное дерево).
- static final int UNTREEIFY_THRESHOLD = 6 — если количество элементов в одной корзине уменьшится до 6, то произойдет обратный переход от дерева к связному списку;
- static final int MIN_TREEIFY_CAPACITY = 64 — минимальная емкость (количество корзин) хеш-таблицы, при которой возможен переход к древовидной структуре. Т.е. если в хеш-таблице по крайней мере 64 бакета и в одном бакете 8 или более элементов, то произойдет переход к древовидной структуре.
|
11. При каких условиях в HashMap лист преобразуется в красно-чёрное дерево? Вернётся к связ. списку?
|
- static final int TREEIFY_THRESHOLD = 8 — это «порог» количества элементов в одной корзине, при достижении которого внутренний связный список будет преобразован в древовидную структуру (красно-черное дерево).
- static final int UNTREEIFY_THRESHOLD = 6 — если количество элементов в одной корзине уменьшится до 6, то произойдет обратный переход от дерева к связному списку;
- static final int MIN_TREEIFY_CAPACITY = 64 — минимальная емкость (количество корзин) хеш-таблицы, при которой возможен переход к древовидной структуре. Т.е. если в хеш-таблице по крайней мере 64 бакета и в одном бакете 8 или более элементов, то произойдет переход к древовидной структуре.
|
12. Методы класса HashMap?
|
HashMap реализует все 13 методов интерфейса Map.
|
13. Можно ли перебрать HashMap в цикле? (Да, можно)
|
for (Map.Entry entry: passportsAndNames.entrySet()) {
System.out.println(entry);}
Интерфейс Map.Entry обозначает пару “ключ-значение” внутри мапы.
Метод entrySet() возвращает список всех пар в нашей HashMap (поскольку наша мапа состоит как раз из таких пар-Entry, то мы перебираем именно пары, а не отдельно ключи или значения).
|
14. Удаление объектов из HashMap по ключу?
|
- заходим в нужный бакет (опять же он предварительно вычисляется);
- если в бакете только один объект (проверяем у него указатель null) сравниваем хеши, ссылки и equals (если вдруг хеши не равны). Нашлось совпадение? Отлично, это наш ключ – удаляем его (=null) и возвращаем значение этого ключа.
- если в бакете больше одного элемента, проверяем каждый элемент в цикле до тех пор, пока не найдем элемент или достигнем конца списка.
- если элемент не был найден — возвращаем null.
|
15. Может ли null быть ключом в HashMap? (Да) Какой хэш-код у null в HashMap? (0)
|
Если вы передадите null в качестве ключа мапы, он перейдет к 0 корзине.
Все ключи, которые являются null, находятся в одной и той же корзине HashMap.
Все значения ключа null будут отправлены туда в виде связанного списка.
Может быть только 1 ключ со значением null.
|
16. Как работает метод get и remove в HashMap?
|
Для того, чтобы получить значение, или удалить пару из мапы, мы должны передать в методы get() и remove() именно уникальный ключ, соответствующий этому значению. Номерных индексов, как в массивах или списках, в HashMap нет — доступ к значению осуществляется по ключу.
|
17. Как работает метод в HashMap?
|
Для добавления новой пары в HashMap используется метод put(). Кроме того, HashMap имеет переопределенный метод toString(), поэтому пару можно выводить на консоль.
|
18. Строение HashMap? Что внутри статического класса Node? (Node синоним пары, ключ – значение)
|
Node — это вложенный статический класс внутри HashMap, который имеет следующие поля:
- final int hash — хеш текущего элемента, который мы получаем в результате хеширования ключа;
- final K key — ключ текущего элемента. Именно сюда записывается то, что вы указываете первым объектом в методе put();
- V value — значение текущего элемента. А сюда записывается то, что вы указываете вторым объектом в методе put();
- Node < K, V> next — ссылка на следующий узел в пределах одной корзины. Список же связный, поэтому ему нужна ссылка не следующий узел, если такой имеется.
newNode() — это метод, который просто возвращает объект класса Node с его полями
Подробнее можно прочитать тут!
|
КОЛЛИЗИЯ
|
1. Что такое коллизия?
|
Коллизия возникает, когда в одной корзине оказывается более одного элемента.
Ситуация, когда разные ключи попадают в одну и ту же корзину (даже с разными хешами), называется коллизией или столкновением. Даже если хеш-таблица больше, чем набор данных, и была выбрана хорошая хеш-функция, это не гарантирует того, что коллизии не возникнут.
|
2. Что происходит при коллизии? 2 причины?
|
- Значение хеша ограничено диапазоном значений типа int (порядка 4 млрд.). В HashCode контракте, неравные объекты могут иметь один и тот же код hash.
- Корзина, может быть, повторно использована даже при наличии большого количества пустых корзин при добавлении двух (неравных) объектов, которые попадают в одну корзину (хэш-код % buckets.length). Когда корзины заполняются, у нового хешируемого объекта, больше шансов оказаться в непустой корзине.
|
3. Как будет разрешаться коллизия?
|
Полученное новое значение также нужно куда-то записать, и для этого нужно определить, куда именно оно будет записано. Это называется решением коллизии.
Существует два подхода:
- external chaining или метод цепочек (реализован в HashMap) — т.е. в ячейке на самом деле содержится список (chain). А уже в списке может содержаться несколько значений (не обязательно с одинаковым хеш-кодом).
- linear probing или метод открытой адресации (реализован в IdentityHashMap) – заключается в поиске первой пустой ячейки после той, на которую указала хеш-функция;
В итоге, добавление элементов при коллизии (в пределах одной корзины) выглядит следующим образом:
- проверяем с помощью методов hashCode() и equals(), что оба ключа одинаковы.
- если ключи одинаковы, заменить текущее значение новым.
- иначе связать новый и старый объекты с помощью структуры данных "связный список", указав ссылку на следующий объект в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре.
Подробнее можно прочитать тут!
|
|
Скачать 0.76 Mb.