HashMap и HashSet. Что это на самом деле?

Dart - Using Set, HashSet, LinkedHashSet, SplayTreeSet Examples

Глава Thinking in Java 4th edition

Книги по Java

КОНТЕЙНЕРЫ И ХРАНЕНИЕ ОБЪЕКТОВОграниченное количество объектов с фиксированным временем жизни характерно разве что для относительно простых программ. В основном ваши программы будут создавать новые объекты на основании критериев, которые станут известны лишь во время их работы. До начала выполнения программы вы не знаете ни количества, ни даже типов нужных вам объектов.

Содержание
  • 1 КОНТЕЙНЕРЫ И ХРАНЕНИЕ ОБЪЕКТОВ
    • 1.1 Параметризованные и типизованные контейнеры
    • 1.2 Основные концепции
    • 1.3 Добавление групп элементов
    • 1.4 Вывод содержимого контейнеров
    • 1.5 List
    • 1.6 Итераторы
    • 1.7 Listlterator
    • 1.8 LinkedList
    • 1.9 Стек
    • Множество
    • Карта
    • Очередь
    • PriorityQueue
    • Collection и Iterator
    • Синтаксис foreach и итераторы
    • Идиома «метод-адаптер»
    • Резюме

КОНТЕЙНЕРЫ И ХРАНЕНИЕ ОБЪЕКТОВ

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

МуТуре aReference;

так как заранее неизвестно, сколько таких ссылок реально потребуется.В большинстве языков существуют некоторые пути решения этой крайне насущной задачи. В Java предусмотрено несколько способов хранения объектов (или, точнее, ссылок на объекты). Встроенным типом является массив, который мы уже рассмотрели. Библиотека утилит Java (*) также содержит достаточно полный набор классов контейнеров (также известных, как классы кол­лекций, но, поскольку имя Collection (коллекция) используется для обозначения определенного подмножества библиотеки Java, я буду употреблять общий термин «контейнер»). Контейнеры обладают весьма изощренными возможностями для хранения объектов и работы с ними, и с их помощью удается решить огромное количество задач.

Практические задания

  1. Изучить особенности реализации классов-коллекций в Java.

  2. Доработать программу, созданную в лабораторных работах № 2 — 3:

  1. добавить генерируемым объектам понятия «время рождения» и «время жизни». Время рождения устанавливается в момент генерации объекта, и по значению соответствует времени, прошедшему от начала симуляции. Время жизни – время, через которое объект должен исчезнуть, считая от времени рождения;

  2. вынести параметры времен жизни объектов в пользовательский интерфейс. Для каждого типа объекта должно задаваться собственное время. Рекомендуется использовать текстовые поля, но следуют помнить о проверке на ввод некорректных данных;

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

  4. добавить генерируемым объектам уникальные целочисленные идентификаторы (случайные числа), которые назначаются при генерации объекта. Для хранения сгенерированных идентификаторов используйте коллекцию удобную для поиска по варианту;

  5. добавьте в панель управления кпопку «Текущие объекты». По нажатию на эту кнопку появляется модальное диалоговое окно, содержащее список всех «живых» объектов на момент нажатия со временем их рождения (время рождения – ключ). В класс диалогового окна должна передаваться коллекция с хранением объектов по времени рождения. Типы коллекций задаются вариантом.

Вариант 1

Коллекция для хранения объектов: Vector

Коллекция для хранения и поиска уникальных идентификаторов: HashSet

Коллекция для хранения объектов по времени рождения: TreeMap

Вариант 2

Коллекция для хранения объектов: ArrayList

Коллекция для хранения и поиска уникальных идентификаторов: HashSet

Коллекция для хранения объектов по времени рождения: TreeMap

Вариант 3

Коллекция для хранения объектов: LinkedList

Коллекция для хранения и поиска уникальных идентификаторов: HashSet

Коллекция для хранения объектов по времени рождения: TreeMap

Вариант 4

Коллекция для хранения объектов: Vector

Коллекция для хранения и поиска уникальных идентификаторов: TreeSet

Коллекция для хранения объектов по времени рождения: HashMap

Вариант 5

Коллекция для хранения объектов: ArrayList

Коллекция для хранения и поиска уникальных идентификаторов: TreeSet

Коллекция для хранения объектов по времени рождения: HashMap

Вариант 6

Коллекция для хранения объектов: LinkedList

Коллекция для хранения и поиска уникальных идентификаторов: TreeSet

Коллекция для хранения объектов по времени рождения: HashMap

Вариант 7

Коллекция для хранения объектов: Vector

Коллекция для хранения и поиска уникальных идентификаторов: HashSet

Коллекция для хранения объектов по времени рождения: HashMap

Вариант 8

Коллекция для хранения объектов: ArrayList

Коллекция для хранения и поиска уникальных идентификаторов: HashSet

Коллекция для хранения объектов по времени рождения: HashMap

Вариант 9

Коллекция для хранения объектов: Vector

Коллекция для хранения и поиска уникальных идентификаторов: TreeSet

Коллекция для хранения объектов по времени рождения: TreeMap

Вариант 10

Коллекция для хранения объектов: ArrayList

Коллекция для хранения и поиска уникальных идентификаторов: TreeSet

Коллекция для хранения объектов по времени рождения: TreeMap

Шаг Что такое хэш-код?

Хэш-код – это целое число, которое является уникальным идентификатором содержимого объекта. От сюда вывод – в каждого объекта, с разными данными, свое уникальное число, с помощью которого мы можем судить о равенстве или неравенстве. В яве, за вычисление этого кода отвечает метод hashCode(), который переопределенный в наследниках Object. Для наших классов мы также должны переопределить его.

Есть несколько правил по переопределению данного метода:

1. Это не должна быть константа. Иначе все будет равным, даже если это не так.

2. Метод генерации должен быть хорошо продуман, иначе могут часто попадаться ситуации коллизии.

3. В генерации желательно использовать именно те поля, которые идентифицируют объект, его уникальность.

Пример того как это все выглядит:

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

1 + 2 = 1 + 2 – равенство верно.

Но что будет если у нас такие объекты:

Здесь поменялся только порядок значений для второго объекта. Эти объекты уже не могут быть равны, но…

1 + 2 = 2 + 1 – равенство осталось верно.

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

Можем сделать вывод:

Для одного и того ж объекта хэш-код всегда один(если не изменять вычисляемые поля)

Если хэш-коды равны, то это не значит что и объекты равны.

Если хэш-коды не равны, то значит и объекты не могут быть равны.

Рассмотрим теперь это на примере. Создадим 2 класса, переопределим вычисление хэш-кода и докажем наши выводы.

public class A { private int a; private int b; public A() { } @Override public int hashCode() { return a + b; } //getters & setters }

И методы main где мы сделаем простую проверку вышесказанного.

A o1 = new A(); A o2 = new A(); (1); (2); (1); (2); /* * Объекты одинаковые, ожидаем true * */ (() == ()); (2); (1); /* * Зесь мы иммем 2 объекта которые имеют разные значение, * то есть и объекты являются разными. Ожидаем false * Получаем коллизию, хэш код одинаковый * */ (() == ()); /* * Объект имеет всегда один хэш-код. Равен сам себе * */ (() == ()); (25); (100); /* * Пример того, что разные хэш-кода, указывают на разные * объекты. * */ («o1=»+() + » o2=»+());

Кратко по каждой коллекции

Интерфейс итератора (Iterator)

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

Интерфейс множества (Set)

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

Платформа Java содержит три реализации Set : HashSet, TreeSet и Set не позволяет осуществлять произвольный доступ к элементу в коллекции. Мы можем использовать итератор или цикл по каждому элементу для перебора элементов.

Интерфейс Список (List)

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

Вот небольшой пример использования:

Java List strList = new ArrayList<>(); //добавить в конец (0, «0»); //добавить элемент в определенное место (1, «1»); //заменить элемент (1, «2»); //удалить элемент («1»);

123456789 List strList = new ArrayList<>();//добавить в конецstrList.add(, «0»);//добавить элемент в определенное местоstrList.add(1, «1»);//заменить элементstrList.set(1, «2»);//удалить элементstrList.remove(«1»);

Интерфейс Очередь (Queue)

Очередь — коллекция, которая используется для хранения нескольких элементов.

В очереди обычно, но не обязательно, элементы располагаются по принципу FIFO (first-in, first-out = первый вошел, первый вышел). В очереди FIFO, все новые элементы вставляются в конец очереди.

Интерфейс Dequeue

Коллекция Dequeue поддерживает вставку элемента и удаление элемента как в начало, так и в конец коллекции. Название Deque это сокращение от «двухконцевой очереди» и, как правило, произносится как «deck». Большинство реализаций DEQUE не устанавливают ограничения на количество элементов.

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

Интерфейс Map

Map является объектом, который содержит ключи и значения. Map не может содержать дубли ключей: Каждый ключ может иметь только одно значение.

Платформа Java содержит три реализации Map: HashMap, TreeMap и LinkedHashMap.

Интерфейс ListIterator

ListIterator (итератор для списков) позволяет программисту проходить список в любом направлении, изменять список во итерации, и получать текущую позицию итератора в списке.

Интерфейс SortedSet

SortedSet представляет собой множество, в котором элементы хранятся в порядке возрастания.

Интерфейс SortedMap

SortedMap содержит элементы в порядке возрастания ключей. Эта Map является аналогом SortedSet. SortedMap используются для естественно упорядоченных пар ключ/значение, например, словарей и телефонных справочников.

Читайте также:  4 причины не выключать компьютер целыми днями