HasMap:
пакет java.util.
Существует два основных вида хеш-таблиц: с цепочками и открытой адресацией.
extends AbstractMap
implements Map, Cloneable, Serializable
класс HasMap - это key-value коллекция работающая по принципу Хеширования. hashCode
Этот класс не дает никаких гарантий упорядоченного размещения элементов.
- Берется у ключа int значение через метод *.hash(Object key) , если обьект равен null , то сразу возвращается 0 .
Key-value значения хранаться попарно в классе Entry , а сами классы Entry храняться в массиве с именем table (capacity - по умолчанию имеет значение 16).
Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки списка.
Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии.В самом худшем случае, время выполнения может составить Θ(n) .
Ключи и значения могут быть любых типов, в том числе и null. Для хранения примитивных типов используются соответствующие классы-оберки;
Новоявленный объект hashmap, содержит ряд свойств:
- table — Массив типа Entry[], который является хранилищем ссылок на списки (цепочки) значений;
- loadFactor — Коэффициент загрузки. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных;
- threshold — Предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
- size — Количество элементов HashMap-а
Вы можете указать свои емкость и коэффициент загрузки, используя конструкторы HashMap(capacity) и HashMap(capacity, loadFactor). Максимальная емкость, которую вы сможете установить, равна половине максимального значения int (1073741824).
Добавление елемента в HashMap:
- Сначала ключ проверяется на равенство null. Если это проверка вернула true, будет вызван метод putForNullKey(value)
- Далее генерируется хэш на основе ключа. Для генерации используется метод hash(hashCode), в который передается key.hashCode().
- С помощью метода indexFor(hash, tableLength), определяется позиция в массиве, куда будет помещен элемент.
При значении хэша 51 и размере таблице 16, мы получаем индекс в массиве 3.
- Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Хэш и ключ нового элемента поочередно сравниваются с хэшами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается.
- Если же предыдущий шаг не выявил совпадений, будет вызван метод addEntry(hash, key, value, index) для добавления нового элемента.
При возникновении коллизии:
- Пропускается, ключ не равен null .
- Далее генерируется хэш на основе ключа ("idx".hashCode() =101603)
- Определение позиции в массиве .
- Новый элемент добавляется в начало цепочки .
Методы:
- *.put(562354, "Шекспир") - добавить в HashMap новый элемент.
- void *.putAll(otherMap) - копирует всё из одной Map'ы в эту.
- String *.get(56265) - вернуть значение по ключу 56265.
- int *.size() - возвращает размер .
- boolean *.containsKey(56265) - Есть ли такой ключ в этой коллекции ?
- boolean *.containsValue("Шекспир") - Есть ли такое значение в этой коллекции ?
- boolean *.isEmpty() - Пустая ли коллекция ?
- *.remove(56265) - Удалить элемент по ключу .
- HashMap *.clone() - клонирует коллекцию.
- void *.clear() - очищает коллекцию .
- Set *.keySet() - получить все ключи из коллекции (key).
- Set(Map.Entry) *.entrySet() - получить все key-value(Entry) .
- List *.values() - Получить все значения (value).