Введение

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

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

Возможно, наиболее важным аспектом, когда речь идет о коллекциях любого рода, является то, как количество элементов в них влияет на их работу. Общий способ описать это - использовать нотацию сложности big-O. Таким образом, когда мы говорим, что операция имеет сложность O(n), это означает, что базовый алгоритм занимает линейное количество времени, пропорциональное количеству элементов в коллекции. Кроме того, для сложности O(1) у нас есть постоянное время для его выполнения, независимо от размера коллекции.

Сказав это, давайте посмотрим, что коллекции Java могут сделать для нас и как они это делают.

Что они могут сделать?

Почти во всех языках программирования коллекция — это способ группировки значений или их ссылок на память, позволяющий нам добавлять, извлекать, удалять или искать их. В Java спецификация API определяет интерфейсы для всех типов коллекций, включая списки, наборы и очереди, все они расширяются из глобального интерфейса Collection с их конкретными контрактами операций.

Ниже мы можем найти список интерфейсов и наиболее важных методов, которые они предоставляют:

  • Коллекция: глобальный интерфейс для каждой коллекции: [добавить, удалить, содержит, размер, очистить, итератор] (доступно во всех интерфейсах ниже)
  • Список: проиндексированный список объектов: [get, set]
  • Набор: список уникальных элементов объектов: []
  • SortedSet: отсортированный список уникальных объектов: [comparator, first, last, headSet, tailSet, subSet, comparator]
  • Очередь: FILO: [предложение, опрос, просмотр]

Как мы видим, в зависимости от типа проблемы, которую нам нужно решить, будет подходящая коллекция для использования. Но это не все. Помимо типа коллекции, также важно понимать, как их реализации структурируют элементы для обработки различных конкретных сценариев.

Начните с более простых

Самая простая реализация коллекции, доступная в API Java, — это ArrayList. Если объем данных невелик, если они могут повторяться и порядок их хранения не имеет значения, то эту коллекцию следует использовать.

Учитывая его индексированную структуру массива, добавление и получение элементов имеют постоянную сложность (O (1)), с линейной сложностью (O (n)) для удаления или поиска элементов на нем.

Еще одна простая коллекция, которую мы можем использовать, — это Vector. У Vector почти такая же реализация, как у ArrayList, но с добавлением возможности синхронизации, что означает, что он потокобезопасен.

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

Связать структурированные коллекции

Связанные структурированные коллекции — это те, у которых есть возможность сохранять порядок добавления элементов при итерации по ним. Это важно, например, при обработке некоторых уже отсортированных данных из базы данных. При извлечении такого рода данных мы не хотим терять элементы заказа, извлеченные из репозитория, иначе не имеет смысла делегировать базе данных эту дополнительную работу.

Простейшей связанной структурой является LinkedList, который может добавлять и удалять элементы с постоянной сложностью (O(1)), но имеет линейную сложность (O(n)) при их получении и поиске.

Связанные списки также реализуют интерфейс Queue, учитывая еще одну важную роль в Java API. Кроме того, все реализации открытых методов Queue имеют постоянную сложность (O (1)), учитывая этот класс, все, что нам нужно для работы с решениями FILO.

До сих пор мы видели, что расширения интерфейса List никогда не были хорошим вариантом, если нам нужна коллекция, используемая в основном для поиска элементов в ней, поскольку нам всегда придется платить за это цену линейной сложности (O (n)).

Хеш-структурированные коллекции

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

Вы можете задаться вопросом, зачем это нужно и стоит ли это затрат на реализацию и увеличения занимаемой площади. Ответ - огромное и звучное ДА!! Это связано с тем, что сложность поиска в коллекции становится постоянной (O (1)). Но для этого мы должны убедиться, что все элементы уникальны, учитывая их контракты на равенство. Вот почему такая структура может использоваться только в конструкциях интерфейса Set.

Но равенство не является прямой концепцией, когда речь идет об элементах в коллекции. То, как мы это сделаем, в основном будет зависеть от бизнес-правил, следующих спецификации Java API.

Класс Java Object, который по умолчанию расширяется всеми другими объектами, имеет два важных метода, используемых для поддержки определения равенства между любым из двух экземпляров. Это методы equals и hashCode, взаимное соглашение которых выглядит следующим образом:

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

Метод hashCode по умолчанию возвращает адрес любого объекта в памяти. Таким образом, два объекта будут считаться равными только в том случае, если они буквально являются одним и тем же экземпляром, что не является очень полезным ограничением. В большинстве случаев нам нужно сравнивать объекты по их состояниям, то есть значениям их атрибутов.

Вы можете подумать, что для этого будет достаточно просто реализовать метод equals, и в большинстве случаев это так. Но не для хеш-структурированных коллекций. Как было сказано ранее, элементы сопоставляются по их хеш-кодам при сохранении в коллекции такого типа. Здесь важно то, что этот ключ является основным критерием для определения равенства между элементами. Если мы не будем следовать контракту между этими двумя методами, бизнес-правило приложения может потерпеть неудачу, даже если ваш метод equals был соответствующим образом переопределен.

Важной информацией о хеш-кодах является то, что если два объекта имеют одинаковое значение, это не делает их равными. Когда у нас есть этот сценарий, так называемая коллизия хэшей, значения сохраняются с использованием связанной структуры в том же ключе. Когда это происходит, мы можем видеть ключи в виде карты корзины, где объекты с одинаковым хешем хранятся вместе и проверяются на равенство с помощью метода equals. Следствием этого является то, что мы можем переопределить метод hashCode, чтобы он возвращал константу, и он будет работать, как и ожидалось, но с потерей производительности, поскольку связанные структуры приведут к более сложному времени выполнения поиска, теряя всю эту структуру. может предложить.

Итак, чтобы убедиться, что мы используем все возможности хеш-структурированного набора, вот практическое правило:

  • При переопределении метода equals сделайте это также для hashCode и убедитесь, что их контракт соблюдается.

В Java API у нас есть две реализации, использующие такую ​​структуру. Более простым является HashSet, который не сохраняет порядок добавления элементов. Если вам нужно использовать эту функцию, вместо нее следует использовать LinkedHashSet. Оба имеют постоянную сложность добавления и поиска (O (1)), но первая имеет сложность итерации, заданную O (h / n), что означает, что чем больше у него элементов, тем быстрее он будет (где h обозначает емкость) .

Коллекции с древовидной структурой

Три структурированные коллекции — еще один важный вид реализации интерфейса Set, который вместо контракта hashCode использует другой механизм для определения равенства между элементами, что также приводит к его наиболее важной особенности: элементы сортируются в процессе итерации коллекции.

Три структурированные коллекции должны реализовывать интерфейс SortedSet и требуют, чтобы их элементы реализовывали интерфейс Comparator. Таким образом, элементы могут определять правило для сравнения друг с другом, что позволяет их сортировать, а также считать равными, когда оно применяется.

Платой за это является логарифмическая сложность (O(log n)) операций добавления, удаления, поиска и итерации. Но, несмотря на то, что это зависит от размера, эта более высокая сложность может быть проигнорирована для небольшого количества элементов, когда требуются отсортированные наборы, и мы не можем делегировать эту функцию внешней системе, такой как база данных.

Единственной реализацией такого рода является TreeSet.

Вывод

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

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

Удачного кодирования!