Список интерфейсов
Существуют две наиболее часто используемые реализации этого интерфейса – ArrayList и LinkedList. Давайте углубимся в каждый из них
Список массивов
Из названия этой структуры мы понимаем, что внутри нее используется простой массив. Но эта структура имеет динамический размер. Это допускается методом ensureCapacity() , который увеличивает используемый простой массив. Когда этот метод вызывает – он проверяет загруженность используемого массива и при необходимости создает новый массив с емкостью, равной текущему + 60% от текущего. Вызывая метод System.arraycopy , мы копируем все элементы из старого массива в новый. Получение, удаление элемента занимает O(1) – постоянное время, потому что у нас простой массив. Операция поиска по индексу требует O(n) операций, потому что мы должны пройти весь массив.
Связанный список
Эта структура основана на объекте, который имеет ссылки на следующий и предыдущий объекты в списке. У этой структуры есть только одно преимущество от списка массивов: вставка в начале выполняется быстрее, чем в списке массивов. Таким образом, эта структура может быть хороша для некоторых задач, но я не сталкивался с этими задачами.
Стек
Эта структура предоставляет нам следующие методы – push, pop, опрос. Кроме того, он реализует LIFO, что означает “последний вход – первый выход”. Например, если мы поместим в стек элементы 10,2,123 – по вызову pop или roll мы получим 123. Но поп удалит 123 из стека. Опрос не удаляет элемент из стека. На внутреннем уровне он использует простой массив.
Набор интерфейсов
Эти структуры данных созданы для хранения только уникальных элементов. Как проверить, что элемент не содержится в коллекции. Для этого у нас есть несколько вариантов реализации. Давай поговорим об этом. Первой реализацией хэш-набора будет сравнение элементов путем вызова equals из объекта. Второй набор деревьев может хранить только элементы, реализующие сопоставимый интерфейс, или вы должны предоставить компаратор через реализацию конструктора для вашего набора деревьев.
Хэш-набор
Внутри него используется хэш-карта, которая может хранить только уникальные ключи. Эта структура не гарантирует порядок вставки, это означает, что при попытке обойти эту коллекцию мы получаем элемент в другом порядке из порядка вставки. Эта реализация имеет постоянное время для основной операции – добавления, удаления, содержания, размера. Это обеспечивается хэш-функцией, которая выполняется в течение постоянного времени.
Набор деревьев
Если хэш-набор основан на хэш-карте, то набор деревьев основан на карте деревьев. Эти структуры данных гарантируют время O(log(n)) для таких операций, как добавление, удаление и содержит. Это предусмотрено, потому что на древовидной карте используется дерево. Эта коллекция гарантирует естественный порядок. Например:
Set numbers = new TreeSet<>();
numbers.add(2);
numbers.add(1);
for(Integer number : numbers) { System.out.println(number);}
На консоли будут напечатаны
1 2
Связанный набор хэшей
Эта коллекция знаменита тем, что в отличие от предыдущей реализации она гарантирует порядок вставки. Таким образом, при повторении этой структуры данных вы увидите свои элементы в порядке их вставки. Как и в предыдущей реализации набора, внутри используется LinkedHashMap. Когда мы пытаемся добавить элемент, уже добавленный в коллекцию – это действие не влияет на порядок элементов. Для основной операции он обеспечивает постоянное время O (n) для операций добавления, удаления, содержимого. Разрешить содержать нулевые элементы. Для выполнения этой коллекции используются две переменные – initialCapacity и loadFactor. Сначала опишите начальную емкость внутренней используемой карты, во-вторых, укажите, когда необходимо увеличить количество использований корзины на карте.
Набор перечислений
Эта реализация создана специально для типа перечисления. Каждая массовая операция, такая как containsAll, retainAll, будет выполняться быстрее, если вы перейдете к этому экземпляру метода EnumSet. При повторении этого набора вы увидите естественный порядок элементов. Возвращенный итератор не вызывает исключение Concurrentmodificationexception. Также итератор может показывать модификацию, а может и не показывать модификацию. Все основные операции выполняются в одно и то же время.
Навигационный набор
В этой реализации есть хорошие опции, такие как навигация по съемочной площадке. Это означает, что мы можем получить элемент, который меньше или больше, чем мы указали. Также мы можем получить набор элементов, которые больше или меньше того, что мы предоставили. Также мы можем изменить эту коллекцию, вызвав метод descendingSet
Очередь интерфейса
В этой коллекции используется механизм FIFO, который означает, что первый вход, первый выход. Мы можем хранить в этом элементе коллекции перед некоторыми операциями с ним. Существуют все основные операции, такие как добавление, удаление. Однако этот метод существует в двух версиях. Первая версия генерирует исключение, если операция завершилась неудачно, другая версия не генерирует исключение и возвращает специальное значение, такое как null . Позволяет добавить null в эту структуру. Однако LinkedList, которые реализуют этот интерфейс, позволяют нам вставлять нулевые элементы. Этот метод не предоставлял методов для одновременного доступа к нему. Для использования очереди в параллельной среде используйте BlockingQueue, которые предоставляют метод блокировки.
Деке
Эта реализация позволяет нам работать как с концом очереди – началом, так и с концом. DE – это аббревиатура от двойного конца. Может быть создана очередь с ограниченным размером, также может быть создана очередь динамического размера. Также в качестве очереди существуют две версии методов для основных операций. Одна версия выдает исключение, если операция завершилась неудачно, другая версия возвращает специальное значение, которое сигнализирует нам о том, что операция завершилась неудачно. Доступ к индексу отсутствует.
Очередь в массив
Из названия для нас ясно понятно, что эта очередь основана на простом массиве. Не ограничивает размер и обеспечивает пропускную способность массива, если это необходимо. Больше операций, выполненных за амортизированное время.
Приоритетный Запрос
Основной принцип работы этой реализации очереди заключается в том, что при добавлении нового элемента в коллекцию будет вызываться метод сортировки для правильного порядка в коллекции. Что является приоритетным в данном контексте? Просто, как набор деревьев, ваш элемент должен быть сопоставим по какому-либо атрибуту, который вы должны выбрать, или вы должны предоставить компаратор для правильного порядка ваших элементов в этой коллекции. Когда вы вызываете методы опроса (не удаляете из этой коллекции) у вас есть элемент, который имеет наибольший приоритет в текущий момент. Эта коллекция обеспечивала логарифмическую скорость для таких операций, как добавление/предложение, удаление/извлечение, и линейное время для таких операций, как содержит.
Карта интерфейса
Хэш-карта
Из понятного нам названия эта структура внутри использует хэш-функцию. Также эта структура позволяет нам помещать нулевые элементы в качестве ключа или значения. При повторении этого вы увидите элементы не в порядке вставки. Для выполнения этой структуры используйте два параметра, которые передаются ей через конструктор. Это коэффициент нагрузки и начальная пропускная способность. Начальная вместимость определяет количество ведер. Коэффициент загрузки определяет, когда будет вызываться метод для обеспечения подсчета ведер.
Совпадающая хэш-карта
Эта реализация карты необходима для одновременного использования. Вместо hashmap это потокобезопасная реализация карты. Сущность этой карты помечена как изменчивая, что означает, что весь поток должен иметь актуальную версию этой сущности.
Навигационная карта
Этот интерфейс расширяет интерфейс карты сортировки и добавляет методы для навигации по элементам карты – нижний вход, вход на этаж, вход на потолок, вход на высоту. Эти методы могут возвращать null . Может перемещаться в прямом и обратном порядке, вызывая descendingMap. Также есть метод навигации, который предоставляет метод извлечения части карты, такой как карта. Нижние и верхние границы включительно в методах отображения (под/голова/хвост). У него есть методы для получения последнего и первого элементов, так как в очереди существуют две версии этих методов.
Древовидная карта
Это красно-черное дерево, основанное на навигационной карте. Элементы сортируются в естественном порядке или с помощью компаратора, который должен быть предоставлен в конструкторе.
Общий
Вся эта структура, исключая Concurrenthashmap, не является потокобезопасной. Это означает, что если вы хотите иметь несколько потоков, у которых должен быть общий ресурс. Все это не подходит для вашей задачи.
Также заметил, что при попытке изменить коллекции во время операции обхода вы получили Исключение ConcurrentModificationException , которое сигнализирует вам о том, что вы пытаетесь изменить коллекцию во время операции обхода. Это недопустимо! Для этой операции мы должны использовать параллельные структуры данных, расположенные в специальном пакете java.
UPD: Также заметил в комментарии Исключение ConcurrentModificationException будет выдано, когда вы в цикле для итерации попытаетесь удалить элемент. Например, если вы хотите удалить некоторые элементы из коллекции на итерации. Следует использовать итератор:
while(iterator.hasNext()) {
if (iterator.next() == 1) {
iterator.remove();
}
}
Спасибо за вас!
Следите за мной в твиттере: @@Воронянский
Оригинал: “https://dev.to/vrnsky/java-data-structures-417e”