Курс

"Программирование Java"

Коллекции

Arrays, Collections. ArrayList, LinkedList

 

Пример реализиции собственного ArrayList

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

Особенности использования

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


Коллекция — абстрактная структура данных, которая оперирует группой объектов. Использование
коллекций дает широкие возможности при программировании, так как каждая коллекция
эффективно справляется со своей задачей, поэтому, чтобы не «изобретать велосипед»,
программист должен знать основные коллекции языка, который он изучает

Полезные материалы

Компаратор и хеш-функция

Компаратор

 

Метод equalsTo, hashCode

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

Для того чтобы отсортировать контейнер, нужно уметь сравнивать элементы между собой. Для примитивных числовых типов все естественно: числа можно сравнивать «как в математике», а у объектов нужно указать способ, ввести порядок, упорядочить их. Например, как сортировать список сотрудников? Возможно, по фамилиям, а, возможно, по зарплате. При этом какого сотрудника поставить в начало списка с наибольшей или, наоборот, с наименьшей зарплатой?

Для упорядочивания объектов в языке Java есть два способа: «научить» сами объекты класса сравниваться между собой (реализовать в классе интерфейс Comparable и создать еще один класс, реализующий интерфейс Comparator — «сравниватель»), такие классы называют компараторами

Полезные материалы

Интерфейс Set

Реализация HashSet, TreeSet

Интерфейс Set определяет множество (набор)

Он расширяет Collection и определяет поведение коллекций, не допускающих дублирования элементов. Таким образом, метод add() возвращает false, если делается попытка добавить дублированный элемент в набор. 

Он не определяет никаких собственных дополнительных методов. 

Интерфейс Set заботится об уникальности хранимых объектов, уникальность определятся реализацией метода equals()

Интерфейс Set включает следующие методы:

boolean add (E item): Добавление элемента в коллекцию, если он отсутствует. Возвращает true, если элемент добавлен

boolean addAll (Collection<?> c): Добавление элементов коллекции, если они отсутствуют

void clear (): удаляет все элементы из коллекции

boolean contains (Object item): возвращает true, если объект item содержится в коллекции, иначе возвращает false

boolean containsAll (Collection<?> c): возвращает true, если указанная коллекция содержится в этой коллекции, иначе возвращает false

equals(Object item )  Проверка на равенство

hashCode() Получение hashCode набора

boolean retainAll(Collection<?>c) удаление из этой коллекции всех элементов  указанной коллекции с

boolean isEmpty (): возвращает true, если коллекция пуста, иначе возвращает false

boolean remove (Object item): возвращает true, если объект item удачно удален из коллекции, иначе возвращается false

int size (): возвращает число элементов в коллекции

Object[] toArray (): возвращает массив, содержащий все элементы коллекции

Iterator<E> iterator(): возвращает итератор коллекции

Полезные материалы

Интерфейс Map. Реализация HashMap, TreeMap

Интерфейс Map<K, V> представляет отображение или иначе говоря словарь, где каждый элемент представляет пару "ключ-значение". При этом все ключи уникальные в рамках объекта Map. Такие коллекции облегчают поиск элемента, если нам известен ключ - уникальный идентификатор объекта

Следует отметить, что в отличие от других интерфейсов, которые представляют коллекции, интерфейс Map НЕ расширяет интерфейс Collection

Среди методов интерфейса Map можно выделить следующие:

void clear(): очищает коллекцию

boolean containsKey(Object k): возвращает true, если коллекция содержит ключ k

boolean containsValue(Object v): возвращает true, если коллекция содержит значение v

Set<Map.Entry<K, V>> entrySet(): возвращает набор элементов коллекции. Все элементы представляют объект Map.Entry

boolean equals(Object obj): возвращает true, если коллекция идентична коллекции, передаваемой через параметр obj

boolean isEmpty: возвращает true, если коллекция пуста

V get(Object k): возвращает значение объекта, ключ которого равен k. Если такого элемента не окажется, то возвращается значение null

V getOrDefault(Object k, V defaultValue): возвращает значение объекта, ключ которого равен k. Если такого элемента не окажется, то возвращается значение defaultVlue

V put(K k, V v): помещает в коллекцию новый объект с ключом k и значением v. Если в коллекции уже есть объект с подобным ключом, то он перезаписывается. После добавления возвращает предыдущее значение для ключа k, если он уже был в коллекции. Если же ключа еще не было в коллекции, то возвращается значение null

V putIfAbsent(K k, V v): помещает в коллекцию новый объект с ключом k и значением v, если в коллекции еще нет элемента с подобным ключом

Set<K> keySet(): возвращает набор всех ключей отображения

Collection<V> values(): возвращает набор всех значений отображения

void putAll(Map<? extends K, ? extends V> map): добавляет в коллекцию все объекты из отображения map

V remove(Object k): удаляет объект с ключом k

int size(): возвращает количество элементов коллекции

Чтобы положить объект в коллекцию, используется метод put, а чтобы получить по ключу - метод get. Реализация интерфейса Map также позволяет получить наборы как ключей, так и значений. А метод entrySet() возвращает набор всех элементов в виде объектов Map.Entry<K, V>

Обобщенный интерфейс Map.Entry<K, V> представляет объект с ключом типа K и значением типа V и определяет следующие методы:

boolean equals(Object obj): возвращает true, если объект obj, представляющий интерфейс Map.Entry, идентичен текущему

K getKey(): возвращает ключ объекта отображения

V getValue(): возвращает значение объекта отображения

V setValue(V v): устанавливает для текущего объекта значение v

int hashCode(): возвращает хеш-код данного объекта

Базовые реализации интерфейса Map:

HashMap - хранит значения в произвольном порядке, но позволяет быстро искать элементы карты. Позволяет задавать ключ или значение ключевым словом null. HashMap работает по принципу Hashing. В простом случае хеширование - это способ присвоения уникального кода для любой переменной / объекта после применения любой формулы / алгоритма по его свойствам. Функция хэша должна возвращать один и тот же хэш-код каждый раз, когда функция применяется на одинаковых или равных объектах

TreeMap - сама сортирует значения по заданному критерию. TreeMap используется либо с Comparable элементами, либо в связке с Comparator

Класс TreeMap<K, V> представляет отображение в виде дерева. Он наследуется от класса AbstractMap и реализует интерфейс NavigableMap, а следовательно, также и интерфейс SortedMap. Поэтому в отличие от коллекции HashMap в TreeMap все объекты автоматически сортируются по возрастанию их ключей

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

Рекомендации:

Вы должны использовать TreeMap, если хотите, чтобы записи были отсортированы

Вы должны использовать HashMap, если отдаете приоритет производительности, а не потреблению памяти

 

Поскольку TreeMap имеет большую локальность, мы можем рассмотреть его, если мы хотим получить доступ к объектам, которые относительно близки друг к другу в соответствии с их естественным порядком

 

HashMap можно настроить с помощью initialCapacity и loadFactor, что невозможно для TreeMap

 

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

Основные методы класса Collections

 

 Методы: sort, binarySearch и другие

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

Полезные материалы