Коллекции.JAVA Flashcards
Что такое «коллекция»?
(4)
«Коллекция» - это структура данных, который содержит набор объектов одного типа.
Данными (объектами в наборе) могут быть числа, строки, объекты пользовательских классов и т.п.
Каждый класс имеет свою специфику хранения объектов.
Классы коллекций являются дженерик-параметрами.
Что такое Java Collections Framework (JCF)?
1) JCF - это набор интерфейсов и реализующих их классов, образующих набор основных используемых коллекций.
2) Хотя это и называется “фреймворк”, JCF скорее является библиотекой.
3) JCF является частью JDK.
Расскажите про иерархию коллекций
Иерархия коллекций в Java - это иерархическая структура классов и интерфейсов, которые предоставляют реализацию различных типов коллекций. Коллекции в Java используются для хранения, обработки и манипулирования группой объектов.
В Java существует два основных пути для иерархии коллекций:
Интерфейсы коллекций:
Collection - основной интерфейс, который описывает базовые методы, необходимые для работы с коллекциями, включая добавление, удаление, поиск и получение элементов. Он расширяет интерфейс Iterable, что позволяет использовать цикл for-each для перебора элементов коллекции.
List - интерфейс, который определяет упорядоченный список элементов, которые могут дублироваться. Он предоставляет дополнительные методы для работы со списками, такие как получение элемента по индексу, вставка элемента в указанную позицию и т.д.
Set - интерфейс, который определяет неупорядоченный набор элементов, которые не могут дублироваться. Он предоставляет методы для проверки наличия элемента в наборе, добавления элемента в набор, удаления элемента из набора и т.д.
Queue - интерфейс, который определяет коллекцию элементов, которые можно добавлять в конец и извлекать из начала. Он расширяет интерфейс Collection и определяет дополнительные методы, такие как offer(), poll() и peek(), которые позволяют добавлять, извлекать и просматривать элементы очереди.
Deque - интерфейс, который определяет двустороннюю очередь, которая позволяет добавлять и извлекать элементы как с головы, так и с хвоста. Он расширяет интерфейс Queue и определяет дополнительные методы, такие как addFirst(), addLast(), removeFirst(), removeLast() и т.д.
Реализации коллекций:
ArrayList - класс, который представляет упорядоченный список элементов, хранящихся в массиве. Он реализует интерфейс List и предоставляет методы для быстрого доступа к элементам по индексу.
LinkedList - класс, который представляет двусвязный список элементов. Он реализует интерфейсы List и Deque и предоставляет быстрое добавление и удаление элемент
Какие данные могут хранить коллекции?
Коллекции могут хранить любые ссылочные типы данных - то есть, ссылки на объекты. Если нужно хранить числа, их придется «оборачивать» в Integer, Double и т.д.
Иерархия Коллекций: главные интерфейсы.
На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection (extends Iterable) и Map. Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» соответственно.
Интерфейс Collection расширяют интерфейсы:
List (список) представляет собой коллекцию, в которой допустимы дублирующие
значения. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно
обратиться по индексу.
Set (сет) описывает неупорядоченную коллекцию, не содержащую повторяющихся
элементов. Реализации:(
Queue (очередь) предназначена для хранения элементов с предопределенным
способом вставки и извлечения FIFO (first-in-first-out):
Методы Collection
(10)
add(E e) - добавляет элемент в коллекцию;
addAll(Collection<? extends E> c) - добавляет все элементы из указанной коллекции в текущую коллекцию;
remove(Object o) - удаляет элемент из коллекции;
removeAll(Collection<?> c) - удаляет из коллекции все элементы, которые есть в указанной коллекции;
retainAll(Collection<?> c) - удаляет из коллекции все элементы, которых нет в указанной коллекции;
clear() - удаляет все элементы из коллекции;
contains(Object o) - проверяет, содержит ли коллекция указанный элемент;
containsAll(Collection<?> c) - проверяет, содержит ли коллекция все элементы из указанной коллекции;
isEmpty() - проверяет, пуста ли коллекция;
size() - возвращает количество элементов в коллекции;
iterator() - возвращает итератор для обхода элементов в коллекции;
toArray() - возвращает массив, содержащий все элементы коллекции;
toArray(T[] a) - возвращает массив указанного типа, содержащий все элементы коллекции.
Назвать главные реализации List
ArrayList - инкапсулирует в себе обычный массив Oblect, длина которого автоматически увеличивается при добавлении новых элементов. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу.
Какие методы ArrayList добавляет в List?
public void trimToSize()
public void ensureCapacity(int minCap)
LinkedList (implements Deque)
двунаправленный связный список - состоит из узлов, каждый из которых содержит как собственно данные, так и две ссылки на следующий и предыдущий узел.
Vector — реализация динамического массива объектов, методы которой синхронизированы.
Stack — расширяет Vector добавляя LIFO (last-in-first-out).
Какие методы добавляет List в Collection?
(6)
get(int index)
set(int index, element)
indexOf(element)
lastIndexOf(element)
ListIterator<E> listIterator();</E>
List<E> subList(int from, int to);</E>
static <E> List<E> of(E... elms)</E></E>
static <E> List<E> copyOf(Collection<? extends E> coll)</E></E>
add(int index, element)
addAll(int index, Collection c)
remove(int index)
Назвать главные реализации Set
(3)
Может ли Set хранить null?
Какие методы добавляет Set в Collection?
HashSet - использует HashMap для хранения данных: в качестве ключа используется добавляемый элемент. В качестве значения объект-заглушка(константа). Порядок хранения элементов неупорядочен.
LinkedHashSet — гарантирует, что порядок элементов при обходе коллекции будет идентичен порядку добавления элементов.
SortedSet->NavigableSet->TreeSet — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».
Не может хранить null.
Какие методы добавляет Set в Collection?
static <E> Set<E> of(E... elms)</E></E> static <E> Set<E> copyOf(Collection<? extends E> coll)</E></E>
Какие доп.методы есть у TreeSet?
public NavigableSet<E> **subSet**(E from, boolean fromIncl, E to, boolean toIncl)</E>
public NavigableSet<E> **tailSet**(E fromElement, boolean inclusive)</E>
public NavigableSet<E> **headSet**(E toElement, boolean inclusive)</E>
first()
last()
Назвать главные реализации Queue? (3)
Какие методы добавляет Deque к Queue?(3)
AbstractQueue => PriorityQueue — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering» (по умолчанию).
Deque => ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать Deque => LinkedList
Deque (двунаправленная очередь) предназначена для хранения и извлечения элементов по принципу FIFO + LIFO.
Какие методы добавляет Deque к Queue?
addFirst()
addLast()
…element->getFirst()
Расположите в виде иерархии следующие интерфейсы:
Iterable
Collection
List
Set
SortedSet
NavigableSet
Map
SortedMap
NavigableMap
Iterator
Почему Map — это не Collection, в то время как List и Set являются Collection?
Collection представляет собой совокупность некоторых элементов. Map - это совокупность пар «ключ-значение».
В чем разница между классами java.util.Collection и java.util.Collections?
Класс java.util.Collection является интерфейсом, который определяет общие методы для всех коллекций в Java, таких как добавление элементов, удаление элементов, проверка наличия элементов и т.д. Он является частью Java Collections Framework и наследуется другими интерфейсами, такими как List, Set и Queue.
Класс java.util.Collections, с другой стороны, является утилитным классом, который предоставляет статические методы для работы с коллекциями. Эти методы позволяют выполнять различные операции над коллекциями, такие как сортировка, перемешивание, копирование, заполнение и т.д. Класс Collections не имеет собственных свойств или методов для работы с коллекциями, он предоставляет только статические методы для работы с объектами коллекций.
Таким образом, разница между классами java.util.Collection и java.util.Collections заключается в том, что первый является интерфейсом, определяющим общие методы для коллекций, а второй - это утилитный класс, предоставляющий статические методы для работы с коллекциями.
Что такое «fail-fast поведение»?
В Java Collections API некоторые итераторы ведут себя как fail-fast и выбрасывают ConcurrentModificationException, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент напрямую из коллекции, а не используя методы итератора.
Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):
- при изменении коллекции счетчик модификаций так же изменяется;
- при создании итератора ему передается текущее значение счетчика;
- при каждом обращении к итератору сохраненное значение счетчика сравнивается с текущим, и, если они не совпадают, возникает исключение.
Какая разница между fail-fast и fail-safe?
В противоположность fail-fast, итераторы fail-safe не вызывают никаких исключений так как “Fail-safe” итератор в Java - это итератор, который создает копию коллекции и работает с ней, а не с оригинальной коллекцией. Это позволяет безопасно изменять коллекцию во время итерации без возникновения исключений ConcurrentModificationException.
Приведите примеры итераторов реализующих поведение fail-safe
Некоторые коллекции в Java, такие как ConcurrentHashMap, CopyOnWriteArrayList и CopyOnWriteArraySet, используют итераторы, которые реализуют поведение “fail-safe”.
Пример fail-fast - Vector и Hashtable.
Чем различаются Enumeration и Iterator?
(3)
Iterator имеет больше методов работы с коллекциями и был специально введен в java2, вместо Enumeration(interface). Рекоммендуется юзать Iterator.
Оба интерфейса предназначены для обхода коллекции, но есть различия:
* -с помощью Enumeration нельзя добавлять/удалять элементы;
* -в Iterator исправлены имена методов для повышения читаемости кода (Enumeration.hasMoreElements() соответствует Iterator.hasNext(), Enumeration.nextElement() соответствует Iterator.next() и т.д);
* -Enumeration присутствуют в устаревших классах, таких как Vector/Stack, тогда как Iterator есть во всех современных коллекциях.
Как между собой связаны Iterable и Iterator?
Интерфейс Iterable имеет только один метод - iterator(), с типом возвращаемого значения - интерфейс Iterator.
Как между собой связаны Iterable, Iterator и «for-each»?
Классы, реализующие интерфейс Iterable, могут применяться в конструкции for-each, которая использует Iterator.
Можно ли итерируясь по ArrayList удалить элемент? Какое вылетит
исключение?
Можно, но нужно использовать iterator.remove().
Иначе при прохождении по ArrayList в цикле for сразу после удаления элемента будет ConcurrentModificationException.
Как поведёт себя коллекция, если вызвать iterator.remove()?
Этот метод удаляет текущий элемент. Важный момент заключается в том, что сначала этот элемент необходимо получить с помощью метода next(), если мы вызовем метод remove() до метода next(), то мы получим IllegalStateException.
Сравните Iterator и ListIterator.
(5)
- ListIterator расширяет интерфейс Iterator
- ListIterator может быть использован только для перебора элементов коллекции List;
- Iterator позволяет перебирать элементы только в одном направлении, при помощи метода next(). Тогда как ListIterator позволяет перебирать список в обоих направлениях, при помощи методов next() и previous();
- ListIterator не указывает на конкретный элемент: его текущая позиция располагается между элементами, которые возвращают методы previous() и next().
- При помощи ListIterator вы можете модифицировать список, добавляя/удаляя элементы с помощью методов add() и remove(). Iterator не поддерживает данного функционала.
Как избежать ConcurrentModificationException во время перебора коллекции?
- Попробовать подобрать другой итератор, работающий по принципу fail-safe. К примеру, для List можно использовать ListIterator.
- Использовать ConcurrentHashMap и CopyOnWriteArrayList.
- Преобразовать список в массив и перебирать массив.
- Блокировать изменения списка на время перебора с помощью блока synchronized.
Отрицательная сторона последних двух вариантов - ухудшение производительности.
Чем Set отличается от List? (5)
1) List хранит объекты к порядке вставки
2) В List элемент можно получить по индексу
3) Set не может хранить одинаковых элементов
4) Метод add() добавляет элемент в коллекцию и возвращает true, если не было такого элемента.
5) Разрешено наличие только одной ссылки типа null
Расскажите про интерфейс Set.(5)
Интерфейс Set расширяет интерфейс Collection.
Set не добавляет новых методов, только вносит изменения унаследованные.
Set - неупорядоченный набор неповторяющихся элементов
В частности, метод add() добавляет элемент в коллекцию и возвращает true, если не было такого элемента.
Разрешено наличие только одной ссылки типа null.
Расскажите про реализации интерфейса Set
В HashSet порядок добавления элементов будет непредсказуемым - используется хэширование для ускорения выборки.
LinkedHashSet хранит элементы в порядке добавления.
SortedSet интерфейс
По умолчанию сортировка производится привычным способом, но можно изменить это поведение через интерфейс Comparable.
В TreeSet объекты хранятся отсортированными по возрастанию из-за применения к/ч дерева.
В чем отличия TreeSet и HashSet? (2)
TreeSet обеспечивает упорядоченное хранение элементов в виде красно-черного дерева. Сложность выполнения основных операций не хуже O(log(N)) (Логарифмическое время).
HashSet использует для хранения элементов такой же подход, что и HashMap, за тем отличием, что в качестве ключа используется добавляемый элемент, а в качестве значения — объект-пустышка (new Object()), кроме того HashSet не поддерживает упорядоченное хранение элементов и обеспечивает временную сложность выполнения операций аналогично HashMap.
Чем LinkedHashSet отличается от HashSet?
Класс LinkedHashSet расширяет класс HashSet, не добавляя никаких новых методов. Класс поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать
упорядоченную итерацию вставки в набор
Основное различие в том, что LinkedHashSet сохраняет порядок вставки элементов, а HashSet - нет.
В основе LinkedHashSet лежит LinkedHashMap вместо HashMap. Благодаря этому порядок элементов при обходе коллекции является идентичным порядку добавления элементов
Что будет, если добавлять элементы в TreeSet по возрастанию?
TreeSet все равно в каком порядке вы добавляете в него элементы, так как в основе TreeSet лежит красно-черное дерево, которое умеет само себя балансировать и хранить элементы по возрастанию.
Как устроен HashSet, сложность основных операций.
Все классы, реализующие интерфейс Set, внутренне поддерживаются реализациями Map.
HashSet хранит элементы с помощью HashMap.
Значение, которые мы передаем в HashSet, является ключом к объекту HashMap, а в качестве значения используется Object.
Т.к. класс реализует интерфейс Set, он может хранить только уникальные значения;
Может хранить NULL – значения;
Порядок добавления элементов вычисляется с помощью хэш-кода;
HashSet также реализует интерфейсы Serializable и Cloneable.
Для поддержания постоянного времени выполнения операций время, затрачиваемое на действия с HashSet, должно быть прямо пропорционально количеству элементов в HashSet + «емкость» встроенного экземпляра HashMap (количество «корзин»). Поэтому для поддержания производительности очень важно не устанавливать слишком высокую начальную ёмкость (или слишком низкий коэффициент загрузки).
Коэффициент загрузки = Количество хранимых элементов в таблице / размер хэш-таблицы Например, если изначальное количество ячеек в таблице равно 16, и коэффициент загрузки равен 0,75, то из этого следует, что когда количество заполненных ячеек достигнет 12, их количество автоматически увеличится.
HashSet - это реализация интерфейса Set в Java, которая использует хэш-таблицу для хранения элементов. В HashSet каждый элемент должен быть уникальным.
При добавлении элемента в HashSet, вычисляется хэш-код элемента, который используется для определения индекса массива, в котором будет храниться элемент. Если два элемента имеют одинаковый хэш-код, то они хранятся в одной ячейке массива в виде связанного списка.
Вот некоторые из основных операций HashSet и их сложность:
Добавление элемента: O(1) в среднем случае, худший случай O(n), где n - количество элементов в связанном списке в массиве. В худшем случае, когда все элементы имеют одинаковый хэш-код, все они будут храниться в одной ячейке массива в виде связанного списка, что увеличивает время выполнения операции до O(n).
Удаление элемента: O(1) в среднем случае, худший случай O(n), где n - количество элементов в связанном списке в массиве. В худшем случае, когда все элементы имеют одинаковый хэш-код, все они будут храниться в одной ячейке массива в виде связанного списка, что увеличивает время выполнения операции до O(n).
Поиск элемента: O(1) в среднем случае, худший случай O(n), где n - количество элементов в связанном списке в массиве. В худшем случае, когда все элементы имеют одинаковый хэш-код, все они будут храниться в одной ячейке массива в виде связанного списка, что увеличивает время выполнения операции до O(n).
HashSet обеспечивает быстрый доступ к элементам, поэтому он часто используется в приложениях, где нужен быстрый поиск или проверка наличия элемента. Однако следует учитывать, что HashSet не гарантирует порядок элементов внутри себя и не подходит для использования в приложениях, где требуется сортировка элементов.
Как устроен LinkedHashSet, сложность основных операций.
LinkedHashSet расширяет класс HashSet, в основе лежит LinkedHashMap - порядок элементов при обходе коллекции является идентичным порядку добавления эл-ов (insertion-order). В среднем сложность поиска, вставки удаления - константное время O(1), в худшем случае это O(n).
LinkedHashSet - это реализация интерфейса Set в Java, которая сочетает в себе хэш-таблицу и связанный список для хранения элементов. В LinkedHashSet каждый элемент должен быть уникальным, а порядок элементов сохраняется в порядке их добавления в множество.
При добавлении элемента в LinkedHashSet, он добавляется как в хэш-таблицу, так и в связанный список. При этом порядок элементов сохраняется, и элементы могут быть перебраны в том порядке, в котором они были добавлены.
Вот некоторые из основных операций LinkedHashSet и их сложность:
Добавление элемента: O(1) в среднем случае, худший случай O(n), где n - количество элементов в связанном списке.
Удаление элемента: O(1) в среднем случае, худший случай O(n), где n - количество элементов в связанном списке.
Поиск элемента: O(1) в среднем случае, худший случай O(n), где n - количество элементов в связанном списке.
Сложность операций LinkedHashSet может быть немного хуже, чем у HashSet, из-за дополнительных действий, необходимых для обслуживания связанного списка. Однако связанный список обеспечивает сохранение порядка элементов, что делает LinkedHashSet более подходящим для использования в приложениях, где требуется сохранение порядка элементов.
LinkedHashSet также имеет дополнительные операции, которых нет в HashSet, такие как getFirst(), getLast() и iterate(), которые позволяют работать со связанным списком напрямую.
Как устроен TreeSet, сложность основных операций.
TreeSet содержит в себе объект NavigableMap, что и обуславливает его поведение, обеспечивает упорядоченное хранение элементов в виде красно-черного дерева.
Сложность выполнения основных операций не хуже O(log(n)) (логарифмическое время).
TreeSet - это реализация интерфейса Set в Java, которая использует бинарное дерево поиска для хранения элементов. В TreeSet каждый элемент должен быть уникальным, а элементы хранятся в отсортированном порядке.
При добавлении элемента в TreeSet, элемент сравнивается с элементами уже хранящимися в дереве и помещается в нужное место, чтобы сохранить порядок элементов. По умолчанию элементы сравниваются с помощью их естественного порядка, но при создании TreeSet можно указать компаратор для определения порядка элементов.
Вот некоторые из основных операций TreeSet и их сложность:
Добавление элемента: O(log n), где n - количество элементов в TreeSet. При добавлении элемента дерево поиска делится на половины, пока не будет найдено место для вставки элемента.
Удаление элемента: O(log n), где n - количество элементов в TreeSet. При удалении элемента дерево поиска делится на половины, пока не будет найден удаляемый элемент.
Поиск элемента: O(log n), где n - количество элементов в TreeSet. При поиске элемента дерево поиска делится на половины, пока не будет найден искомый элемент.
TreeSet обеспечивает быстрый доступ к элементам, а также возможность получения элементов в отсортированном порядке. Однако, добавление и удаление элементов может быть несколько медленнее, чем в HashSet или LinkedHashSet, из-за необходимости перестраивания дерева поиска.
Гарантирует порядок элементов - в основе лежит красно-черное дерево, которое умеет само себя балансировать.
Не предоставляет каких-либо параметров для настройки производительности
Предоставляет дополнительные методы для упорядоченного списка: first(), last(), headSet(), tailSet()
Расскажите про интерфейс List
Интерфейс List в Java представляет упорядоченный список элементов, где каждый элемент имеет свой индекс. Он расширяет интерфейс Collection и предоставляет дополнительные операции для работы с элементами списка. В List элементы могут дублироваться, а порядок элементов сохраняется в соответствии с их позициями в списке.
Некоторые из методов, определенных в интерфейсе List:
add(int index, E element) - добавляет элемент на указанную позицию в списке.
get(int index) - возвращает элемент по указанному индексу.
remove(int index) - удаляет элемент на указанной позиции из списка.
set(int index, E element) - заменяет элемент на указанной позиции в списке.
indexOf(Object o) - возвращает индекс первого вхождения указанного элемента в список.
size() - возвращает количество элементов в списке.
subList(int fromIndex, int toIndex) - возвращает подсписок элементов от fromIndex (включительно) до toIndex (исключая).
Кроме того, интерфейс List реализуется классами ArrayList, LinkedList, Vector и другими. Классы ArrayList и LinkedList представляют два разных подхода к хранению элементов в списке.
ArrayList хранит элементы в динамическом массиве, что позволяет быстро получать доступ к элементам по индексу. Однако, добавление и удаление элементов может быть медленным, если необходимо изменить размер массива.
LinkedList, с другой стороны, использует двусвязный список для хранения элементов. Это позволяет быстро добавлять и удалять элементы в середине списка, но доступ к элементам по индексу может быть медленным.
Vector - это устаревший класс, который аналогичен ArrayList, но имеет синхронизированные методы, что делает его более безопасным для использования в многопоточных приложениях. Однако, в большинстве случаев лучше использовать ArrayList вместо Vector.
Как устроен ArrayList, сложность основных операций.
ArrayList хранит элементы в динамическом массиве. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.
Основное преимущество такой коллекции над массивом – это расширяемость – увеличение длины при надобности.
Если в этом массиве заканчивается место, то создаётся второй массив побольше, куда копируются все элементы из первого. Затем второй массив занимает место первого, а первый – выбрасывается (будет уничтожен сборщиком мусора).
Длина нового массива рассчитывается так (3*n)/2+1, где n – это длина старого массива. Т.е. если старый массив был длиной 100 элементов, то новый будет 300/2+1 = 151
При добавлении элемента в середину ArrayList, все элементы справа от него копируются на 1 позицию вправо, а затем в пустую ячейку добавляется новый элемент.
По возможности, избегайте операций вставки в середину коллекции. Ведь системе приходится заново пересчитывать индексы элементов.
При удалении элемента из середины, все элементы справа от него копируются на 1 позицию влево. Сам массив не укорачивается (можно укоротить через trimToSize()).
Особенности
- Быстрый доступ к элементам по индексу за время O(1);
- Доступ к элементам по значению за линейное время O(n);
- Медленный, когда вставляются и удаляются элементы из «середины» списка;
- Позволяет хранить любые значения в том числе и null;
- Не синхронизирован.
ArrayList в Java - это реализация интерфейса List, основанная на динамическом массиве. ArrayList увеличивает размер внутреннего массива, когда добавляется новый элемент, если текущий массив заполнен, и уменьшает размер, когда удаляется элемент.
Вот некоторые из основных операций ArrayList и их сложность:
Добавление элемента в конец списка: O(1) в среднем случае. Если внутренний массив заполнен, ArrayList должен выделить новый массив большего размера и скопировать все элементы из старого массива в новый массив.
Добавление элемента в середину списка: O(n), где n - количество элементов в списке. В этом случае ArrayList должен сдвинуть все элементы, следующие за заданным индексом, на одну позицию вправо.
Доступ к элементу по индексу: O(1). Элементы хранятся в массиве, и доступ к элементу по индексу является простой операцией.
Удаление элемента: O(n), где n - количество элементов в списке. При удалении элемента ArrayList также должен сдвинуть все элементы, следующие за заданным индексом, на одну позицию влево.
Поиск элемента: O(n), где n - количество элементов в списке. ArrayList не предоставляет быстрого доступа к элементам, как это делают TreeSet или HashSet, поскольку при поиске элемента требуется пройти весь список от начала до конца.
ArrayList является хорошим выбором, если вам нужно быстро получать доступ к элементам по индексу и вы не часто добавляете или удаляете элементы в середине списка. Однако, если вам нужно часто добавлять или удалять элементы в середине списка, возможно, лучше использовать LinkedList.
Как устроен LinkedList, сложность основных операций.
Связный список состоит из одинаковых элементов, которые хранят данные и хранят ссылки на следующий и предыдущий элементы.
Вся работа с LinkedList сводится к изменению ссылок.
Однако, у LinkedList есть отдельные методы для работы с началом и концом списка, которых нет в ArrayList: addFirst(), addLast(): методы для добавления элемента в начало/конец списка Вставка и удаление в середину LinkedList устроены гораздо проще, чем в ArrayList. Мы просто
переопределяем ссылки соседних элементов, а ненужный элемент “выпадает” из цепочки ссылок.
LinkedList в Java - это реализация интерфейса List, основанная на двусвязном списке. Каждый элемент списка содержит ссылки на предыдущий и следующий элементы, за исключением первого и последнего элементов списка, которые могут ссылаться на null.
Вот некоторые из основных операций LinkedList и их сложность:
Добавление элемента в конец списка: O(1). Так как LinkedList хранит ссылку на последний элемент, добавление нового элемента в конец списка сводится к созданию нового узла и установке ссылки предыдущего последнего элемента на новый элемент.
Добавление элемента в середину списка: O(n), где n - количество элементов в списке. В этом случае LinkedList должен пройти от начала списка к месту, куда нужно вставить новый элемент, что требует времени O(n).
Доступ к элементу по индексу: O(n), где n - индекс элемента. Так как каждый элемент в LinkedList связан только со своим предыдущим и следующим элементами, доступ к элементу по индексу требует прохождения по списку от начала до нужного элемента, что требует времени O(n).
Удаление элемента: O(1) или O(n), в зависимости от того, какой элемент нужно удалить. Если элемент находится в начале или конце списка, удаление элемента занимает O(1), в противном случае LinkedList должен пройти от начала списка до нужного элемента, что требует времени O(n).
Поиск элемента: O(n), где n - количество элементов в списке. LinkedList не предоставляет быстрого доступа к элементам, как это делают TreeSet или HashSet, поскольку при поиске элемента требуется пройти весь список от начала до конца.
LinkedList является хорошим выбором, если вам часто нужно добавлять или удалять элементы в середине списка, но при этом не нужен быстрый доступ к элементам по индексу. Однако, если вам нужно быстро получать доступ к элементам по индексу, возможно, лучше использовать ArrayList.
Почему LinkedList реализует и List, и Deque?
LinkedList — класс, реализующий два интерфейса — List и Deque.
Это обеспечивает возможность создания двунаправленной очереди из любых (в том числе и null) элементов. Каждый объект, помещенный в связанный список, является узлом (нодом). Каждый узел содержит элемент, ссылку на предыдущий и следующий узел. Фактически связанный список состоит из последовательности узлов, каждый из которых предназначен для хранения объекта определенного при создании типа.
LinkedList в Java реализует интерфейсы List и Deque, потому что это двусвязный список, который может быть использован как обычный список (List), но также обладает свойствами очереди (Deque), такими как добавление и удаление элементов в начале и конце списка.
Интерфейс List определяет основные методы для работы с последовательностью элементов, которые могут быть доступны по индексу, а также для вставки и удаления элементов в середине списка. LinkedList в этом случае реализует все методы интерфейса List, поскольку каждый элемент списка содержит ссылки на предыдущий и следующий элементы.
Интерфейс Deque, с другой стороны, определяет методы для работы с двусторонней очередью элементов, где элементы могут быть добавлены или удалены с обоих концов очереди. LinkedList также реализует этот интерфейс, потому что он может эффективно поддерживать операции добавления и удаления элементов как в начале, так и в конце списка.
Таким образом, реализация обоих интерфейсов позволяет использовать LinkedList как список, а также как очередь, в которой элементы могут быть добавлены или удалены как в начале, так и в конце. Это делает LinkedList гибким и эффективным в использовании для решения различных задач.
Чем отличаются ArrayList и LinkedList?
ArrayList и LinkedList в Java являются реализациями интерфейса List, но они реализованы с использованием разных структур данных и имеют различные характеристики.
Вот несколько различий между ArrayList и LinkedList:
Структура данных: ArrayList внутренне использует массив для хранения элементов, в то время как LinkedList использует двусвязный список.
Доступ к элементам: ArrayList обеспечивает быстрый доступ к элементам по индексу, так как элементы хранятся в массиве и доступ к ним происходит по индексу, что занимает константное время O(1). В LinkedList для доступа к элементу требуется пройти по списку от начала или конца, что занимает время O(n).
Вставка и удаление элементов: LinkedList лучше подходит для вставки и удаления элементов в середине списка, так как вставка и удаление элемента в LinkedList занимает время O(1), если уже известен узел, после которого нужно вставить новый узел или который нужно удалить. В ArrayList вставка и удаление элемента в середине списка может быть дорогой операцией, так как требуется перемещение всех элементов после позиции вставки или удаления, что занимает время O(n).
Занимаемое место в памяти: ArrayList использует фиксированный массив для хранения элементов, в то время как LinkedList использует узлы, которые хранят значения элементов, а также ссылки на предыдущий и следующий узлы. Это может привести к тому, что ArrayList занимает меньше места в памяти, чем LinkedList.
Таким образом, если требуется быстрый доступ к элементам по индексу и меньшее занимаемое место в памяти, следует использовать ArrayList. Если же требуется частая вставка и удаление элементов в середине списка и не требуется быстрый доступ к элементам по индексу, лучше использовать LinkedList.
В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти, и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список.
В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет вызова быстрого системного метода System.arraycopy().
Что такое Queue?
Queue - это очередь, которая обычно (но необязательно) строится по принципу FIFO (First-In-First-Out) - соответственно извлечение элемента осуществляется с начала очереди, вставка элемента в конец очереди.
Хотя этот принцип нарушает, к примеру, PriorityQueue, использующая «natural ordering» или переданный Comparator при вставке нового элемента.
Особенностью PriorityQueue является возможность управления порядком элементов. По-умолчанию, элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта Comparator, который задаётся при создании очереди.
Данная коллекция не поддерживает null в качестве элементов.
Используя PriorityQueue, можно, например, реализовать алгоритм Дейкстры для поиска кратчайшего пути от одной вершины графа к другой. Либо для хранения объектов согласно определённого свойства.
Что такое Dequeue? Чем отличается от Queue?
Deque - двухстороняя очередь, расширяет queue.
Он отличается от Queue тем, что можно добавлять и удалять элементы как в хвосте так и в голове. Количество методов удваивается.
Пример:
addFirst(E e);
addLast(E e);
Помимо этого реализации интерфейса Deque могут строится по принципу FIFO, либо LIFO.
Реализации и Deque, и Queue обычно не переопределяют методы equals() и hashCode(), а используются методы класса Object, основанные на сравнении ссылок.
Рекомендуется использовать вместо устаревшего Stack.
Deque (Double Ended Queue, двусторонняя очередь) - это структура данных, которая поддерживает добавление и удаление элементов с обоих концов очереди. Это означает, что вы можете добавлять и удалять элементы с начала или конца очереди в любой момент.
Deque отличается от Queue (очереди) тем, что Queue поддерживает только добавление элементов в конец очереди и удаление элементов из начала очереди (FIFO). Однако в Deque можно добавлять и удалять элементы с начала и конца очереди, что дает большую гибкость в управлении данными.
Deque можно использовать в различных сценариях, например, для реализации стека (LIFO), когда элементы добавляются и удаляются только с одного конца очереди, или для обработки задач с приоритетами, когда элементы добавляются как в начало, так и в конец очереди, в зависимости от их приоритета.
Java предоставляет интерфейс Deque и несколько классов, реализующих этот интерфейс, таких как ArrayDeque и LinkedList. Deque расширяет интерфейс Queue и добавляет дополнительные методы для работы с обоими концами очереди.
Приведите пример реализации Dequeue.
ArrayDeque (также известный как «Array Double Ended Queue», произносится как «ArrayDeck») - это особый вид растущего массива, который позволяет нам добавлять или удалять элементы с обеих сторон.
Реализация ArrayDeque может использоваться как Stack (последний пришел-первый вышел) или Queue (первый пришел-первый вышел)
Под капотом ArrayDeque поддерживается массив, который удваивает свой размер при заполнении.
Первоначально, массив инициализируется с размером 16. Он реализован как двусторонняя очередь, где он поддерживает два указателя, а именно голову и хвост.
ArrayDeque:
Это не потокобезопасный
Нулевые элементы не принимаются
Работает значительно быстрее, чем синхронизированный Stack
Более быстрая очередь, чем LinkedList из-за лучшей локализации. Большинство операций амортизировали сложность с постоянным временем
Iterator , возвращаемый ArrayDeque , является отказоустойчивым
ArrayDeque автоматически удваивает размер массива, когда head и хвостовой указатель встречает друг друга при добавлении элемента
Linked list, Stack, ArrayDeque
Какая коллекция реализует FIFO?
Одной из коллекций, реализующих FIFO (First-In-First-Out), является очередь (Queue).
Элементы в очереди добавляются в конец и удаляются из начала очереди. То есть первый элемент, добавленный в очередь, будет первым, который будет удален из очереди.
Java предоставляет несколько классов, реализующих интерфейс Queue, например, LinkedList, PriorityQueue, ArrayDeque.
Какая коллекция реализует LIFO?
Одной из коллекций, реализующих LIFO (Last-In-First-Out), является стек (Stack).
Элементы в стек добавляются и удаляются с одного конца - вершины стека. То есть последний элемент, добавленный в стек, будет первым, который будет удален из стека.
Java предоставляет класс Stack, который реализует интерфейс Deque и позволяет использовать стековые операции (push, pop, peek и т.д.). Однако, в качестве стека также можно использовать любую другую коллекцию, реализующую интерфейс Deque, например, LinkedList или ArrayDeque.
Оцените количество памяти на хранение одного примитива типа byte в LinkedList?
Связный список (LinkedList) в Java состоит из узлов (Node), каждый из которых хранит значение элемента и ссылки на предыдущий и следующий узлы. Для хранения одного примитива типа byte в узле LinkedList необходимо выделить память для самого байта (8 бит), а также для ссылок на предыдущий и следующий узлы. Размер ссылки на узел в 64-битной Java-машины равен 8 байтам.
Таким образом, для хранения одного примитива типа byte в LinkedList потребуется 24 байта памяти: 8 байт для самого байта и 16 байт (8 байт на ссылку на предыдущий узел и 8 байт на ссылку на следующий узел).
Однако, стоит учитывать, что узел LinkedList может также хранить ссылки на объекты, которые в свою очередь могут занимать большее количество памяти, включая их поля, ссылки на другие объекты и т.д. Кроме того, для каждого узла в LinkedList также требуется память для хранения метаданных, например, для управления списком и выделения памяти, что может увеличивать общий объем занимаемой памяти.
Оцените количество памяти на хранение одного примитива типа byte в ArrayList?
ArrayList основан на массиве, для примитивных типов данных осуществляется автоматическая упаковка значения, поэтому 16 байт тратится на хранение упакованного объекта и 4 байта (8 для x64) -
на хранение ссылки на этот объект в самой структуре данных. Таким образом, в x32 JVM 4 байта используются на хранение одного элемента и 16 байт - на хранение упакованного объекта типа Byte.
Для x64 - 8 байт и 24 байта соотвтетсвенно.
х32=20байт
х64=32байт
В ArrayList в Java каждый элемент хранится в отдельной ячейке массива. При создании объекта ArrayList выделяется некоторое начальное количество элементов, и если массив оказывается заполнен, то он увеличивается в размере.
Для хранения одного примитива типа byte в ArrayList необходимо выделить память для самого байта (8 бит). Размер одной ячейки в массиве для типа byte составляет 1 байт.
Таким образом, для хранения одного примитива типа byte в ArrayList потребуется 1 байт памяти. Однако, при этом также нужно учитывать, что для ArrayList необходимо выделить начальное количество элементов и соответствующее количество памяти, а также, если массив оказывается заполнен, то при его расширении требуется дополнительная память.
Какие существуют реализации Map?
Hashtable — реализация такой структуры данных, как хэш-таблица. Она не позволяет использовать null в качестве значения или ключа. Эта коллекция была реализована раньше, чем Java Collection Framework, но в последствии была включена в его состав. Как и другие коллекции из Java 1.0, Hashtable является синхронизированной (почти все методы помечены как synchronized). Из-за этой особенности у неё имеются существенные проблемы с производительностью и, начиная с Java 1.2, в большинстве случаев рекомендуется использовать другие реализации интерфейса Map ввиду отсутствия у них синхронизации.
HashMap — коллекция является альтернативой Hashtable. Двумя основными отличиями от Hashtable являются то, что HashMap не синхронизирована и HashMap позволяет использовать null как в качестве
ключа, так и значения. Так же как и Hashtable, данная коллекция не является упорядоченной: порядок хранения элементов зависит от хэш-функции. Добавление элемента выполняется за константное время O(1), но время удаления, получения зависит от распределения хэш-функции. В идеале является константным, но может быть и линейным O(n).
LinkedHashMap — это упорядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap, порядок итерирования равен порядку добавления элементов. Данная особенность достигается благодаря двунаправленным связям между элементами (аналогично LinkedList). Но это преимущество имеет также и недостаток — увеличение памяти, которое занимет коллекция.
TreeMap — реализация Map основанная на красно-чёрных деревьях. Как и LinkedHashMap является упорядоченной. По-умолчанию, коллекция сортируется по ключам с использованием принципа "natural ordering", но это поведение может быть настроено под конкретную задачу при помощи объекта Comparator, который указывается в качестве параметра при создании объекта TreeMap.
WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references. Другими словами, Garbage Collector автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элеметна нет жёстких ссылок.
Как устроена HashMap, сложность основных операций? (Расскажите про принцип корзин)
HashMap – внутри состоит из корзин и списка элементов, на которые ссылаются корзины.
Корзины – массив
Элементы(Node) – связанный список, то есть каждый элемент списка имеет указатель на следующий элемент.
При добавлении нового элемента, хэш-код ключа определяет корзину для элемента с помощью hashFunction(), который принимает hashCode ключа и возвращает номер корзины. В корзине есть ссылка на связанный список, в который будет положен наш объект. Идет проверка, есть ли элементы в этом списке. Если нету, то корзина получает ссылку нового элемента, если есть, то происходит прохождение по списку элементов и сравнивание элементов в списке. Проверяется равенство hashcode. Зная о коллизии, проводится еще сравнивание ключей методом equals.
Если оба равны: идет перезапись
Если не равен equals: добавляется элемент в конец списка
принцип цепочек
1) Если в ячейке хранится более одного элемента, то из них делают связный список.
2) Ячейка хэш-таблицы ссылается на начало списка.
3) Последовательно перебирая элементы списка и сравнивая их по equals() с искомым объектом, находим нужный.
4) Сложность поиска элемента при этом становится O(n), где n - число элементов хранящихся в хэш-таблице (худший случай - все в этом списке)
5) Вместо линейного списка можно использовать бинарное самобалансирующееся дерево - тогда сложность снизится до O(log(n)).
Если элементов в списке корзины становится слишком много, связный список превращается в бинарное дерево, что ускоряет поиск элемента.
По умолчанию в HashMap 16 корзин. Отвечая, стоит заметить, что можно используя конструкторы с параметрами: через параметр capacity задавать свое начальное количество корзин
HashMap имеет поле loadFactor. Оно может быть задано через конструктор. По умолчанию - 0.75. Его произведение на количество корзин дает нам необходимое число объектов которое нужно добавить чтобы состоялось удвоение количества корзин.
Например если у нас мапка с 16-ю(default) корзинами, а loadFactor равняется 0.75, то расширение произойдет когда мы добавим 16 * 0.75 = 12 объектов.
После удвоения все объекты будут перераспределены с учетом нового количества корзин
Сложность основных операций в HashMap зависит от загруженности хэш-таблицы и от реализации методов equals() и hashCode() для ключей. В идеальном случае, когда хэш-таблица загружена равномерно, поиск, добавление и удаление элементов выполняются за постоянное время O(1).
Однако, в худшем случае, когда все элементы хранятся в одном индексе и образуется длинный связанный список, время выполнения может составлять O(n), где n - количество элементов в HashMap. Поэтому для эффективной работы HashMap необходимо выбирать правильное значение начальной емкости и коэффициента загрузки, чтобы минимизировать вероятность коллизий и связанных с ними потерь производительности.
Таким образом, сложность основных операций в HashMap в среднем является постоянной O(1), но в худшем случае может достигать линейной O(n).
Что такое LinkedHashMap?
LinkedHashMap - упорядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap, порядок итерирования равен порядку добавления элементов.
Данная структура может слегка уступать по производительности родительскому HashMap, при этом время выполнения операций add(), contains(), remove() остается константой — O(1). Понадобится чуть больше места в памяти для хранения элементов и их связей, но это совсем небольшая плата за дополнительные фишечки. Он также принимаетнулевой ключ, а также нулевые значения.
LinkedHashMap не синхронизирована.
LinkedHashMap - это реализация интерфейса Map в Java, которая объединяет характеристики HashMap и LinkedList. Он предоставляет быстрый доступ к элементам, как и HashMap, но также сохраняет порядок вставки элементов, как LinkedList.
Сложность основных операций в LinkedHashMap такие же, как и в HashMap:
Добавление элемента: O(1) в среднем случае и O(n) в худшем случае, где n - количество элементов в LinkedHashMap.
Удаление элемента: O(1) в среднем случае и O(n) в худшем случае, где n - количество элементов в LinkedHashMap.
Поиск элемента: O(1) в среднем случае и O(n) в худшем случае, где n - количество элементов в LinkedHashMap.
Однако, если использовать итератор для перебора элементов, LinkedHashMap предоставляет гарантию сохранения порядка вставки элементов, что делает эту операцию более эффективной, чем в обычной HashMap, где порядок элементов не гарантируется.
Только что созданный объект linkedHashMap, помимо свойств унаследованных от HashMap (такие как table, loadFactor, threshold, size, entrySet и т.п.), так же содержит два доп. свойства:
header — «голова» двусвязного списка. При инициализации указывает сам на себя;
accessOrder — указывает каким образом будет осуществляться доступ к элементам при использовании итератора. При значении true — по порядку последнего доступа. При значении false доступ осуществляется в том порядке, в каком элементы были вставлены.
Как устроена TreeMap, сложность основных операций?
Класс TreeMap<K, V> представляет отображение в виде дерева. Он наследуется от класса AbstractMap и реализует интерфейс NavigableMap, а следовательно, также и интерфейс SortedMap. Поэтому в отличие от коллекции HashMap в TreeMap все объекты автоматически сортируются по возрастанию их ключей.
TreeMap - это реализация интерфейса Map в Java, которая хранит ключи в отсортированном порядке. Для этого он использует красно-черное дерево, которое является самобалансирующимся деревом поиска. Это позволяет ему поддерживать логарифмическую сложность операций, связанных с размером карты.
Сложность основных операций в TreeMap:
Добавление элемента: O(log n), где n - количество элементов в TreeMap.
Удаление элемента: O(log n), где n - количество элементов в TreeMap.
Поиск элемента: O(log n), где n - количество элементов в TreeMap.
Операции добавления, удаления и поиска элементов в TreeMap выполняются с использованием структуры дерева. Дерево разбивается на более мелкие части с каждой операцией, что позволяет быстро и эффективно обрабатывать большие наборы данных.
За счет своей структуры TreeMap предоставляет возможность выполнять дополнительные операции, такие как получение поддерева в диапазоне заданных ключей, обход элементов в порядке возрастания или убывания ключей и т.д. Все эти операции также выполняются за время O(log n), что делает TreeMap очень эффективным инструментом для работы с отсортированными данными.
Что такое WeakHashMap?
является реализацией интерфейса Map на основе хеш-таблиц, с ключами из WeakReference тип.
Запись в WeakHashMap будет автоматически удалена, если ее ключ больше не используется в обычном режиме. Это означает, что не существует ни одной ссылки, указывающая на этот ключ. Когда процесс сборки мусора (GC) отбрасывает ключ, его запись эффективно удаляется с карты, поэтому
этот класс ведет себя несколько иначе, чем другие реализации Map.
Применение – реализация простого кэша.
WeakHashMap - это реализация интерфейса Map в Java, которая использует слабые ссылки для ключей. Это означает, что если на ключ не остается сильных ссылок, то ключ автоматически удаляется из карты во время сборки мусора. Таким образом, WeakHashMap может использоваться для хранения объектов, которые могут быть удалены в случае, если на них больше не осталось ссылок.
Сложность основных операций в WeakHashMap такие же, как и в HashMap:
Добавление элемента: O(1) в среднем случае и O(n) в худшем случае, где n - количество элементов в WeakHashMap.
Удаление элемента: O(1) в среднем случае и O(n) в худшем случае, где n - количество элементов в WeakHashMap.
Поиск элемента: O(1) в среднем случае и O(n) в худшем случае, где n - количество элементов в WeakHashMap.
Однако, поскольку ключи в WeakHashMap используют слабые ссылки, они могут быть удалены в любой момент времени во время сборки мусора. Это может повлиять на производительность, если большое количество объектов удаляется одновременно.
WeakHashMap может использоваться в сценариях, где необходимо хранить данные, которые могут быть автоматически удалены при нехватке памяти, например, в кэшировании, обработке изображений и т.д. Однако его использование требует осторожности и необходимости гарантировать, что ключи в карту будут использоваться достаточно долго, чтобы они не были удалены слишком рано.
Как работает HashMap при попытке сохранить в него два элемента по ключам с одинаковым hashCode(), но для которых equals() == false?
Когда в HashMap добавляется элемент, сначала вычисляется хэш-код его ключа с помощью метода hashCode(). Затем HashMap использует этот хэш-код, чтобы определить, в каком “корзине” должен храниться элемент.
Если два ключа имеют одинаковый хэш-код, они будут храниться в одной “корзине” в виде связанного списка. Когда вы пытаетесь получить значение по ключу, HashMap сначала вычисляет хэш-код ключа, затем находит соответствующую “корзину” и проходит по списку элементов в этой корзине, вызывая метод equals() для каждого ключа, пока не найдет элемент с соответствующим ключом.
Если два ключа имеют одинаковый хэш-код, но не равны друг другу (то есть метод equals() возвращает false), то они будут храниться в одной “корзине” в виде двух элементов в связанном списке. При попытке получить значение по одному из этих ключей, HashMap сначала найдет соответствующую “корзину” по хэш-коду ключа, затем проходит по списку элементов в этой корзине, вызывая метод equals() для каждого ключа, пока не найдет элемент с соответствующим ключом.
Таким образом, если два ключа имеют одинаковый хэш-код, но не равны друг другу, то они могут быть храниться в HashMap в виде двух элементов в связанном списке. Это означает, что при попытке получения значения по одному из этих ключей, HashMap должен пройти по списку и вызвать метод equals() для каждого ключа в списке, что может привести к снижению производительности.
Что будет, если мы кладем в HashMap ключ, у которого equals и hashCode
определены некорректно?
Если ключ, который добавляется в HashMap, имеет не корректно определенные методы equals() и hashCode(), то это может привести к непредсказуемому поведению HashMap.
Обычно, HashMap использует значения хэш-кодов и метод equals() для определения того, какие ключи равны друг другу. Если метод hashCode() некорректно определен, то это может привести к тому, что ключи, которые должны быть различными, имеют одинаковый хэш-код. В этом случае, HashMap не сможет правильно определить, в какой “корзине” должен храниться элемент, что может привести к коллизиям, неэффективному хранению данных и снижению производительности.
Если метод equals() некорректно определен, то это может привести к непредсказуемому поведению при попытке получения значения по ключу. Если два ключа, которые должны быть равными, не определены таким образом, что метод equals() возвращает true, то HashMap будет рассматривать их как разные ключи, даже если они на самом деле представляют одно и то же значение. Это может привести к тому, что HashMap не сможет найти элемент по ключу, который должен существовать, или может вернуть неправильное значение.
Таким образом, для правильной работы HashMap необходимо, чтобы методы equals() и hashCode() были корректно определены для ключей. Если это не выполнено, то работа HashMap может стать непредсказуемой и привести к неожиданным результатам.
Возможна ли ситуация, когда HashMap выродится в список даже с ключами имеющими разные hashCode()?
Это возможно в случае, если метод indexFor(hash, tableLength), определяющий номер корзины будет
возвращать одинаковые значения
Да, такая ситуация возможна. В HashMap хранение элементов происходит в виде “корзин” (buckets), которые представляют собой связанные списки элементов. Каждая “корзина” содержит элементы, у которых хэш-коды равны. Если много элементов имеют одинаковые хэш-коды, и они распределены равномерно по всем “корзинам”, то HashMap будет работать эффективно. Однако, если много элементов имеют одинаковый хэш-код и они хранятся в одной “корзине”, то это может привести к тому, что HashMap выродится в список.
Например, если все ключи имеют одинаковый хэш-код, то все элементы будут храниться в одной “корзине”, и при поиске элемента HashMap будет проходить по всем элементам в этой “корзине” в порядке их добавления, что может привести к снижению производительности.
Еще один пример - если метод hashCode() для ключей реализован таким образом, что он возвращает одно и то же значение для всех ключей, то все элементы будут храниться в одной “корзине”, и HashMap будет работать как связанный список, что также может привести к снижению производительности.
Таким образом, для эффективной работы HashMap необходимо, чтобы хэш-коды ключей были равномерно распределены по всем “корзинам”, а также чтобы метод hashCode() был корректно реализован для каждого ключа.
Почему нельзя использовать byte[] в качестве ключа в HashMap?
Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива).
Также у массивов не переопределен equals и выполняется сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента.
В принципе, можно использовать byte[] в качестве ключа в HashMap. Однако, при использовании byte[] в качестве ключа в HashMap нужно учитывать, что в этом случае сравнение ключей производится по ссылке, а не по значению. Это означает, что если создать два разных массива byte[] с одинаковыми значениями элементов, то они будут иметь разные ссылки и будут считаться разными ключами в HashMap.
Также необходимо учитывать, что в Java массивы являются изменяемыми объектами. Это значит, что если изменить значение какого-то элемента в массиве, который используется в качестве ключа в HashMap, то это может привести к тому, что хэш-код ключа изменится и его местоположение в HashMap тоже изменится. При этом, если после изменения ключа производить поиск по старому ключу, то это может привести к тому, что элемент не будет найден в HashMap.
Если использование byte[] в качестве ключа в HashMap необходимо, то для правильной работы HashMap необходимо переопределить методы hashCode() и equals() для этого типа ключа. В методе hashCode() нужно рассчитывать хэш-код на основе значений элементов массива byte[], а в методе equals() нужно производить сравнение элементов массива по значению.
Таким образом, использование byte[] в качестве ключа в HashMap возможно, но требует дополнительной работы по переопределению методов hashCode() и equals() и учета особенностей работы с изменяемыми объектами.
Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hashCode()?
Да, будет, но в этом случае HashMap вырождается в связный список и теряет свои преимущества
Технически, HashMap будет работать, если все добавляемые ключи будут иметь одинаковый hashCode(). Однако, такое использование HashMap может привести к снижению производительности, поскольку в этом случае все элементы будут храниться в одной “корзине” (bucket).
Каждая “корзина” в HashMap представляет собой связанный список элементов, у которых хэш-коды равны. Если все элементы имеют одинаковый хэш-код, то все они будут храниться в одной “корзине”, и при поиске элемента HashMap будет проходить по всем элементам в этой “корзине” в порядке их добавления, что может привести к снижению производительности.
Кроме того, если все ключи имеют одинаковый хэш-код, то это может привести к тому, что при добавлении новых элементов они будут заменять старые элементы с тем же хэш-кодом, а не добавляться в HashMap. При этом, если новые элементы не эквивалентны старым элементам (то есть, equals() возвращает false), то старый элемент будет потерян.
Таким образом, использование HashMap с ключами, у которых все хэш-коды равны, может привести к ошибкам и неэффективности работы структуры данных. Рекомендуется генерировать хэш-коды ключей таким образом, чтобы они были равномерно распределены по всем “корзинам” в HashMap.
Какое худшее время работы метода get(key) для ключа, которого нет в HashMap?
Худшее время работы метода get(key) для ключа, которого нет в HashMap, будет O(n), где n - это количество элементов в HashMap.
Когда мы вызываем метод get(key) для ключа, которого нет в HashMap, то HashMap должен произвести поиск элемента внутри структуры данных. В худшем случае (когда элемент не найден), HashMap должен пройти по всем n элементам, чтобы убедиться, что элемента с таким ключом нет в коллекции.
При этом, если элементов в HashMap очень много, то время работы метода get(key) может быть значительно увеличено, что может привести к существенному снижению производительности при работе со структурой данных. Однако, при правильном выборе начальной емкости HashMap и коэффициента загрузки, можно минимизировать вероятность возникновения таких ситуаций.
Какое худшее время работы метода get(key) для ключа, который есть в HashMap?
Худшее время работы метода get(key) для ключа, который есть в HashMap, будет O(n), где n - это количество элементов в HashMap. Однако, на практике, время работы метода get(key) для существующего ключа будет гораздо меньше, так как поиск элемента в HashMap выполняется за константное время в среднем случае (O(1)).
Когда мы вызываем метод get(key) для ключа, который есть в HashMap, то в большинстве случаев элемент будет найден немедленно, без необходимости проходить по всем элементам коллекции. Вместо этого, HashMap использует хэш-функцию, чтобы найти “корзину” (bucket), в которой может находиться элемент с данным ключом. Затем, HashMap проходит по элементам в этой “корзине” и сравнивает ключи, пока не найдет элемент с нужным ключом.
Таким образом, время работы метода get(key) для существующего ключа зависит от количества элементов в “корзине”, в которой находится элемент с данным ключом. Если в “корзине” много элементов, то время работы метода get(key) может быть значительно увеличено. Однако, если использовать правильные параметры начальной емкости HashMap и коэффициента загрузки, можно минимизировать вероятность возникновения “переполненных” “корзин” и ускорить время работы метода get(key) для существующих ключей.
Comparator vs. Comparable
Интерфейс Comparable является хорошим выбором, когда он используется для определения порядка по умолчанию или, другими словами, если это основной способ сравнения объектов.
Зачем же использовать Comparator, если уже есть Comparable?
Есть несколько причин:
* иногда нельзя изменить исходный код класса, чьи объекты необходимо
отсортировать, что делает невозможным использование Comparable;
* использование компараторов позволяет избежать добавления дополнительного кода в классы домена;
* можно определить несколько разных стратегий сравнения, что невозможно при использовании Comparable.
Сравните Iterator и ListIterator
ListIterator расширяет интерфейс Iterator;
* ListIterator может быть использован только для перебора элементов коллекции List;
* Iterator позволяет перебирать элементы только в одном направлении при помощи
метода next(), тогда как ListIterator позволяет перебирать список в обоих
направлениях при помощи методов next() и previous();
* ListIterator не указывает на конкретный элемент: его текущая позиция располагается
между элементами, которые возвращают методы previous() и next();
* при помощи ListIterator можно модифицировать список, добавляя/удаляя элементы с
помощью методов add() и remove(), Iterator не поддерживает данного функционала
Зачем добавили ArrayList, если уже был Vector?
методы класса Vector синхронизированы, а ArrayList нет;
* по умолчанию Vector удваивает свой размер, когда заканчивается выделенная под
элементы память, ArrayList же увеличивает свой размер только на половину;
* Vector это устаревший класс и его использование не рекомендовано.
Big O(Сравнение сложности алгоритмов)
O(n!) - это временная сложность алгоритмов, которые увеличивают время выполнения в факториальной прогрессии с увеличением размера входных данных. Алгоритмы с такой временной сложностью считаются крайне неэффективными и редко используются на практике, кроме как для очень маленьких значений n.
O(2^n) - экспоненциальная сложность. Примером может служить алгоритм решения задачи коммивояжера методом полного перебора.
O(n!) - факториальная сложность. Примером может служить алгоритм генерации всех перестановок элементов в массиве.
O(n^3) - кубическая сложность. Примером может служить алгоритм умножения двух матриц.
O(n^2) - квадратичная сложность. Примером может служить алгоритм сортировки пузырьком или алгоритм поиска наибольшей общей подпоследовательности двух строк.
O(n log n) - сложность логарифмического типа. Примерами могут служить алгоритмы быстрой сортировки (quicksort) и сортировки слиянием (merge sort).
O(n) - линейная сложность. Примерами могут служить алгоритмы линейного поиска, подсчета количества элементов в массиве, поиска максимального или минимального элемента в массиве.
O(log n) - логарифмическая сложность. Примерами могут служить алгоритмы бинарного поиска в отсортированном массиве или дереве.
O(1) - константная сложность. Примером может служить доступ к элементу массива по его индексу.
Важно понимать, что временная сложность алгоритма зависит не только от его алгоритмической реализации, но и от размера входных данных. Поэтому, например, алгоритм сортировки пузырьком может быть быстрее алгоритма быстрой сортировки для очень маленьких массивов данных. Однако, при увеличении размера входных данных, алгоритмы с более низкой временной сложностью будут более эффективными.
класс Collections
Collections - это класс в языке Java, который содержит утилиты для работы с коллекциями объектов, такими как списки, множества, отображения и другие. Класс предоставляет статические методы для выполнения различных операций над коллекциями, таких как сортировка, поиск, копирование, заполнение и многое другое.
Некоторые из наиболее распространенных методов, предоставляемых классом Collections, включают:
sort(List<T> list) - сортирует заданный список в порядке возрастания элементов в соответствии с естественным порядком элементов или с использованием заданного компаратора.</T>
binarySearch(List<T> list, T key) - выполняет двоичный поиск по указанному списку и возвращает индекс элемента, равного указанному ключу, или отрицательное значение, если элемент не найден.</T>
reverse(List<?> list) - обращает порядок элементов в заданном списке.
shuffle(List<?> list) - случайным образом перемешивает элементы в заданном списке.
copy(List<? super T> dest, List<? extends T> src) - копирует элементы из одного списка в другой.
fill(List<? super T> list, T obj) - заполняет указанный список заданным объектом.
max(Collection<? extends T> coll) - возвращает максимальный элемент в заданной коллекции, используя естественный порядок элементов или заданный компаратор.
min(Collection<? extends T> coll) - возвращает минимальный элемент в заданной коллекции, используя естественный порядок элементов или заданный компаратор.
Класс Collections является частью Java Collections Framework и предоставляет удобные методы для работы с коллекциями объектов. Он обеспечивает реализацию ряда алгоритмов и структур данных, таких как списки, множества, отображения и др., которые можно использовать для эффективной работы с большим количеством данных.
interface Comparable
Comparable - это интерфейс в языке Java, который используется для сравнения объектов. Он определяет единственный метод compareTo(), который возвращает отрицательное целое число, ноль или положительное целое число в зависимости от того, является ли вызывающий объект меньшим, равным или большим, чем объект, переданный в качестве параметра.
Чтобы сделать свой класс сравнимым, нужно реализовать интерфейс Comparable и переопределить метод compareTo(). Например, если мы хотим сравнивать объекты типа Person по их возрасту, мы можем сделать следующее:
public class Person implements Comparable<Person> {
private String name;
private int age;
@Override
public int compareTo(Person other) {
return Integer.compare(this.age, other.age);
}
В этом примере мы реализовали интерфейс Comparable<Person> и переопределили метод compareTo(), чтобы он сравнивал объекты Person по их возрасту. Метод compareTo() использует метод Integer.compare(), чтобы сравнить возраст текущего объекта с возрастом переданного объекта.</Person>
Теперь мы можем использовать методы, которые работают с объектами, реализующими интерфейс Comparable, например, метод Collections.sort(), чтобы отсортировать список объектов Person по возрасту:
interface Comparator
Comparator - это интерфейс в языке Java, который используется для сравнения объектов, когда класс объекта не может быть изменен или когда нужно провести сравнение по разным критериям. В отличие от интерфейса Comparable, который определяет единственный метод compareTo(), интерфейс Comparator определяет два метода: compare() и equals().
Метод compare() принимает два объекта и возвращает отрицательное целое число, ноль или положительное целое число в зависимости от того, является ли первый объект меньшим, равным или большим, чем второй объект. Метод equals() используется для сравнения Comparator с другим объектом на равенство.
Чтобы сделать свой класс сортируемым с помощью Comparator, нужно реализовать этот интерфейс и переопределить метод compare(). Например, если мы хотим отсортировать список объектов типа Person сначала по имени, а затем по возрасту, мы можем сделать следующее:
public class PersonComparator implements Comparator<Person> {
@Override
public int compare(Person p1, Person p2) {
int nameCompare = p1.getName().compareTo(p2.getName());
if (nameCompare != 0) {
return nameCompare;
}
return Integer.compare(p1.getAge(), p2.getAge());
}
}
В этом примере мы реализовали интерфейс Comparator<Person> и переопределили метод compare(), чтобы он сравнивал объекты Person по имени, а затем по возрасту. Метод compare() использует метод String.compareTo() для сравнения имен, а метод Integer.compare() для сравнения возрастов.</Person>
Comparator vs. Comparable
Интерфейс Comparable является хорошим выбором, когда он используется для определения
порядка по умолчанию или, другими словами, если это основной способ сравнения
объектов.
Зачем же использовать Comparator, если уже есть Comparable?
Есть несколько причин:
* иногда нельзя изменить исходный код класса, чьи объекты необходимо
отсортировать, что делает невозможным использование Comparable;
* использование компараторов позволяет избежать добавления дополнительного кода
в классы домена;
* можно определить несколько разных стратегий сравнения, что невозможно при
использовании Comparable.
Оба интерфейса Comparable и Comparator используются для сравнения объектов, но имеют разные цели и способы использования.
Интерфейс Comparable определяет единственный метод compareTo(), который позволяет сравнивать объекты этого класса с другими объектами этого же класса. Реализация этого метода позволяет классу определить естественный порядок сортировки объектов этого класса.
Например, класс String реализует интерфейс Comparable, что позволяет сравнивать строки по алфавитному порядку:
Интерфейс Comparator позволяет определить специальный порядок сортировки, который может отличаться от естественного порядка сортировки, определенного интерфейсом Comparable. Это может быть полезно в случаях, когда мы не можем изменить код исходного класса, чтобы реализовать интерфейс Comparable, или когда нам нужно сравнить объекты по разным критериям.
Например, мы можем создать класс PersonComparator, который реализует интерфейс Comparator<Person> и используется для сортировки списка объектов типа Person по имени:</Person>
Как видно из этого примера, использование интерфейса Comparator позволяет нам определить специальный порядок сортировки для объектов, которые не реализуют интерфейс Comparable.
В целом, интерфейс Comparable используется для определения естественного порядка сортировки объектов этого класса, в то время как интерфейс Comparator используется для определения специального порядка сортировки, который может отличаться от естественного порядка сортировки.
чем hashmap отличается от hashtable?
HashMap и HashTable представляют собой две разные реализации хеш-таблиц, используемых для хранения и доступа к данным по ключу.
Основные различия между HashMap и HashTable заключаются в следующем:
Синхронизация: HashTable синхронизирован по умолчанию, что означает, что он может быть использован в многопоточных приложениях без дополнительных усилий по синхронизации. В то же время, HashMap не является синхронизированным, но его можно сделать синхронизированным, используя метод Collections.synchronizedMap().
Нулевые значения: HashTable не допускает нулевые значения ни в качестве ключей, ни в качестве значений, в то время как HashMap допускает нулевые значения как ключей и как значений.
Итерация: HashMap предоставляет возможность итерации через элементы с помощью итератора, в то время как HashTable не предоставляет такой функциональности.
Наследование: HashMap является наследником класса AbstractMap, а HashTable является устаревшим классом, который рекомендуется не использовать в новом коде.
Производительность: HashMap обычно предпочтительнее в ситуациях, когда требуется высокая производительность, тогда как HashTable может быть предпочтительнее в случаях, когда требуется гарантированная синхронизация.
Использование в Java 8 и выше: Начиная с Java 8, рекомендуется использовать ConcurrentHashMap вместо HashTable для обеспечения безопасности при многопоточном доступе.
В целом, если вы работаете в многопоточной среде, которая требует гарантированной синхронизации, HashTable может быть предпочтительнее. В остальных случаях, HashMap является более современной и предпочтительной реализацией хеш-таблицы.
