Паршин Павел
Главное меню
Вопросы и ответы на собеседовании по теме Java Collection Framework. Часть 3.
Другое
LinkedList позволяет добавлять элементы в начало и конец списка за константное время, что хорошо подходит для реализации интерфейса Deque (в отличие, например, от ArrayList ).
Класс java.util.Collections содержит исключительно статические методы для работы с коллекциями. В них входят методы, реализующие полиморфные алгоритмы (такие алгоритмы, использование которых возможно с разными видами структур данных), «оболочки», возвращающие новую коллекцию с инкапсулированной указанной структурой данных и некоторые другие методы.
7. Что такое « fail-fast поведение»?
Fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом.
Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени. Также стоит отметить, что fail-fast поведение не может быть абсолютно гарантировано.
Помимо этого класс EnumSet предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров.
Итерация по EnumSet осуществляется согласно порядку объявления элементов перечисления.
9. java.util.Stack — считается «устаревшим». Чем его рекомендуют заменять? Почему?
Рекомендуется использовать интерфейс Deque («дек», Double Ended Queue) и его реализации. Например:
Класс Stack появился в JDK 1.0 и расширяет класс Vector, наследуя его функционал, что несколько нарушает понятие стека (например, класс Vector предоставляет возможность обращаться к любому элементу по индексу). Также использование Deque позволяет следовать принципу программирования на уровне интерфейсов, а не конкретных реализаций, что облегчает дальнейшую поддержку разрабатываемого класса и повышает его гибкость, позволяя при необходимости менять реализацию дека на нужную.
10. Какая коллекция реализует дисциплину обслуживания FIFO?
11. Какая коллекция реализует дисциплину обслуживания FILO?
При добавлении элемента, который уже присутствует в LinkedHashMap (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.
Реализация LinkedHashSet отличается от HashSet поддержкой двухсвязанного списка, определяющего порядок итерации по элементам структуры данных. Элементы списка упорядочены согласно их порядку добавления в LinkedHashSet (insertion-order).
При добавлении элемента, который уже присутствует в LinkedHashSet (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.
16. Говорят, на LinkedHashMap легко сделать простенький кэш c «invalidation policy», знаете как?
Необходимо использовать LRU-алгоритм (Least Recently Used algorithm) и LinkedHashMap с access-order. В этом случае при обращении к элементу он будет перемещаться в конец списка, а наименее используемые элементы будут постепенно группироваться в начале списка.
Простой пример реализации кэша с очисткой старых значений при превышении указанного порога:
Стоит заметить, что LinkedHashMap не позволяет полностью реализовать LRU-алгоритм, поскольку при вставке уже имеющегося в коллекции элемента порядок итерации не меняется.
java-interview
Вопросы для собеседования на разработчика Java
Java Collections Framework
Что такое «коллекция»?
Назовите основные интерфейсы JCF и их реализации.
Интерфейс Collection расширяют интерфейсы:
Интерфейс Mindmap реализован классами:
Что такое «fail-fast поведение»?
fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом. Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени.
Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):
Какая разница между fail-fast и fail-safe?
В противоположность fail-fast, итераторы fail-safe не вызывают никаких исключений при изменении структуры, потому что они работают с клоном коллекции вместо оригинала.
Приведите примеры итераторов, реализующих поведение fail-safe
Итератор коллекции CopyOnWriteArrayList и итератор представления keySet коллекции ConcurrentHashMap являются примерами итераторов fail-safe.
Хотя оба интерфейса и предназначены для обхода коллекций между ними имеются существенные различия:
Как избежать ConcurrentModificationException во время перебора коллекции?
Какая коллекция реализует дисциплину обслуживания FIFO?
Какая коллекция реализует дисциплину обслуживания FILO?
Vector это устаревший класс и его использование не рекомендовано.
ArrayList это список, реализованный на основе массива, а LinkedList — это классический двусвязный список, основанный на объектах с ссылками между ними.
В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти, и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список.
Смотря какие действия будут выполняться над структурой.
O(N). Время поиска элемента линейно пропорционально количеству элементов в списке.
O(N). Время поиска элемента линейно пропорционально количеству элементов в списке.
O(N). Добавление в начало/конец списка осуществляется за время O(1).
O(N). Вставка элемента в конец списка осуществляется за время O(1), но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый.
Необходимо добавить 1 млн. элементов, какую структуру вы используете?
Однозначный ответ можно дать только исходя из информации о том в какую часть списка происходит добавление элементов, что потом будет происходить с элементами списка, существуют ли какие-то ограничения по памяти или скорости выполнения.
Если в массиве достаточно места для размещения нового элемента, то дополнительной памяти не требуется. Иначе происходит создание нового массива размером в 1,5 раза превышающим существующий (это верно для JDK выше 1.7, в более ранних версиях размер увеличения иной).
Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные.
Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны: 8 + 8 + 8 + 16 = 40 байт и 24 байта. Итого 64 байта.
Для ArrayList или для LinkedList операция добавления элемента в середину ( list.add(list.size()/2, newElement) ) медленнее?
Deque (Double Ended Queue) расширяет Queue и согласно документации, это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса Deque могут строиться по принципу FIFO, либо LIFO.
LinkedList — это односвязный, двусвязный или четырехсвязный список?
Двусвязный : каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.
Stack считается «устаревшим». Чем его рекомендуют заменять? Почему?
Hashtable это устаревший класс и его использование не рекомендовано.
Результат выполнения кода:
В Java существует 4 типа ссылок: сильные (strong reference), мягкие (SoftReference), слабые (WeakReference) и фантомные (PhantomReference). Особенности каждого типа ссылок связаны с работой Garbage Collector. Если объект можно достичь только с помощью цепочки WeakReference (то есть на него отсутствуют сильные и мягкие ссылки), то данный объект будет помечен на удаление.
В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences?
В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences?
При добавлении элемента, который уже присутствует в LinkedHashMap (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.
Так же оно проявляется при итерации по коллекции.
HashMap состоит из «корзин» (bucket). С технической точки зрения «корзины» — это элементы массива, которые хранят ссылки на списки элементов. При добавлении новой пары «ключ-значение», вычисляет хэш-код ключа, на основании которого вычисляется номер корзины (номер ячейки массива), в которую попадет новый элемент. Если корзина пустая, то в нее сохраняется ссылка на вновь добавляемый элемент, если же там уже есть элемент, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется.
HashMap реализован с использованием метода цепочек, т.е. каждой ячейке массива (корзине) соответствует свой связный список и при возникновении коллизии осуществляется добавление нового элемента в этот список.
Для метода цепочек коэффициент заполнения может быть больше 1 и с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов, либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения.
Среди методов открытой реализации различают:
Недостатки структур с методом открытой адресации:
Преимущества хэш-таблицы с открытой адресацией:
По значению hashCode() вычисляется индекс ячейки массива, в список которой этот элемент будет добавлен. Перед добавлением осуществляется проверка на наличие элементов в этой ячейке. Если элементы с таким hashCode() уже присутствует, но их equals() методы не равны, то элемент будет добавлен в конец списка.
В общем случае операции добавления, поиска и удаления элементов занимают константное время.
Пример кода двоичного поиска:
Это возможно в случае, если метод, определяющий номер корзины будет возвращать одинаковые значения.
Допустим, в качестве ключа используется не примитив, а объект с несколькими полями. После добавления элемента в HashMap у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хэш-кода. В результате при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот equals уже не найдет указанный ключ в списке элементов. Тем не менее, даже если equals реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хэш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет в совершенно другую корзину и тогда уже потеряется совсем.
Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняется сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента.
hashCode позволяет определить корзину для поиска элемента, а equals используется для сравнения ключей элементов в списке корзины и искомого ключа.
Сколько переходов происходит в момент вызова HashMap.get(key) по ключу, который есть в таблице?
Да, будет, но в этом случае HashMap вырождается в связный список и теряет свои преимущества.
TreeSet обеспечивает упорядоченно хранение элементов в виде красно-черного дерева. Сложность выполнения основных операций не хуже O(log(N)) (Логарифмическое время).
Что будет, если добавлять элементы в TreeSet по возрастанию?
В основе TreeSet лежит красно-черное дерево, которое умеет само себя балансировать. В итоге, TreeSet все равно в каком порядке вы добавляете в него элементы, преимущества этой структуры данных будут сохраняться.
Помимо всего EnumSet предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров.
Класс java util stack считается устаревшим что можно использовать вместо него
Java Collections Framework
Назовите основные интерфейсы JCF и их реализации.
Интерфейс Collection расширяют интерфейсы:
Интерфейс Mindmap реализован классами:
Что такое «fail-fast поведение»?
fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом. Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени.
Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):
Какая разница между fail-fast и fail-safe?
В противоположность fail-fast, итераторы fail-safe не вызывают никаких исключений при изменении структуры, потому что они работают с клоном коллекции вместо оригинала.
Приведите примеры итераторов, реализующих поведение fail-safe
Итератор коллекции CopyOnWriteArrayList и итератор представления keySet коллекции ConcurrentHashMap являются примерами итераторов fail-safe.
Хотя оба интерфейса и предназначены для обхода коллекций между ними имеются существенные различия:
Как избежать ConcurrentModificationException во время перебора коллекции?
Какая коллекция реализует дисциплину обслуживания FIFO?
Какая коллекция реализует дисциплину обслуживания FILO?
Vector это устаревший класс и его использование не рекомендовано.
ArrayList это список, реализованный на основе массива, а LinkedList — это классический двусвязный список, основанный на объектах с ссылками между ними.
В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти, и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список.
Смотря какие действия будут выполняться над структурой.
O(N). Время поиска элемента линейно пропорционально количеству элементов в списке.
O(N). Время поиска элемента линейно пропорционально количеству элементов в списке.
O(N). Добавление в начало/конец списка осуществляется за время O(1).
O(N). Вставка элемента в конец списка осуществляется за время O(1), но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый.
Необходимо добавить 1 млн. элементов, какую структуру вы используете?
Однозначный ответ можно дать только исходя из информации о том в какую часть списка происходит добавление элементов, что потом будет происходить с элементами списка, существуют ли какие-то ограничения по памяти или скорости выполнения.
Если в массиве достаточно места для размещения нового элемента, то дополнительной памяти не требуется. Иначе происходит создание нового массива размером в 1,5 раза превышающим существующий (это верно для JDK выше 1.7, в более ранних версиях размер увеличения иной).
Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные.
Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны: 8 + 8 + 8 + 16 = 40 байт и 24 байта. Итого 64 байта.
Для ArrayList или для LinkedList операция добавления элемента в середину ( list.add(list.size()/2, newElement) ) медленнее?
Deque (Double Ended Queue) расширяет Queue и согласно документации, это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса Deque могут строиться по принципу FIFO, либо LIFO.
LinkedList — это односвязный, двусвязный или четырехсвязный список?
Двусвязный : каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.
Stack считается «устаревшим». Чем его рекомендуют заменять? Почему?
Hashtable это устаревший класс и его использование не рекомендовано.
Результат выполнения кода:
В Java существует 4 типа ссылок: сильные (strong reference), мягкие (SoftReference), слабые (WeakReference) и фантомные (PhantomReference). Особенности каждого типа ссылок связаны с работой Garbage Collector. Если объект можно достичь только с помощью цепочки WeakReference (то есть на него отсутствуют сильные и мягкие ссылки), то данный объект будет помечен на удаление.
В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences?
В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences?
При добавлении элемента, который уже присутствует в LinkedHashMap (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.
Так же оно проявляется при итерации по коллекции.
HashMap состоит из «корзин» (bucket). С технической точки зрения «корзины» — это элементы массива, которые хранят ссылки на списки элементов. При добавлении новой пары «ключ-значение», вычисляет хэш-код ключа, на основании которого вычисляется номер корзины (номер ячейки массива), в которую попадет новый элемент. Если корзина пустая, то в нее сохраняется ссылка на вновь добавляемый элемент, если же там уже есть элемент, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется.
HashMap реализован с использованием метода цепочек, т.е. каждой ячейке массива (корзине) соответствует свой связный список и при возникновении коллизии осуществляется добавление нового элемента в этот список.
Для метода цепочек коэффициент заполнения может быть больше 1 и с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов, либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения.
Среди методов открытой реализации различают:
Недостатки структур с методом открытой адресации:
Преимущества хэш-таблицы с открытой адресацией:
По значению hashCode() вычисляется индекс ячейки массива, в список которой этот элемент будет добавлен. Перед добавлением осуществляется проверка на наличие элементов в этой ячейке. Если элементы с таким hashCode() уже присутствует, но их equals() методы не равны, то элемент будет добавлен в конец списка.
В общем случае операции добавления, поиска и удаления элементов занимают константное время.
Пример кода двоичного поиска:
Это возможно в случае, если метод, определяющий номер корзины будет возвращать одинаковые значения.
Допустим, в качестве ключа используется не примитив, а объект с несколькими полями. После добавления элемента в HashMap у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хэш-кода. В результате при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот equals уже не найдет указанный ключ в списке элементов. Тем не менее, даже если equals реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хэш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет в совершенно другую корзину и тогда уже потеряется совсем.
Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняется сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента.
hashCode позволяет определить корзину для поиска элемента, а equals используется для сравнения ключей элементов в списке корзины и искомого ключа.
Сколько переходов происходит в момент вызова HashMap.get(key) по ключу, который есть в таблице?
Да, будет, но в этом случае HashMap вырождается в связный список и теряет свои преимущества.
TreeSet обеспечивает упорядоченно хранение элементов в виде красно-черного дерева. Сложность выполнения основных операций не хуже O(log(N)) (Логарифмическое время).
Что будет, если добавлять элементы в TreeSet по возрастанию?
В основе TreeSet лежит красно-черное дерево, которое умеет само себя балансировать. В итоге, TreeSet все равно в каком порядке вы добавляете в него элементы, преимущества этой структуры данных будут сохраняться.
Помимо всего EnumSet предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров.
Какие существуют способы перебирать элементы списка?
Каким образом можно получить синхронизированные объекты стандартных коллекций?
Как получить коллекцию только для чтения?
Эти методы принимают коллекцию в качестве параметра, и возвращают коллекцию только для чтения с теми же элементами внутри.
Как, используя LinkedHashMap, сделать кэш c «invalidation policy»?
Стоит заметить, что LinkedHashMap не позволяет полностью реализовать LRU-алгоритм, поскольку при вставке уже имеющегося в коллекции элемента порядок итерации по элементам не меняется.
Как одной строчкой скопировать элементы любой collection в массив?
Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?
Класс java util stack считается устаревшим что можно использовать вместо него
Java Collections Framework
Назовите основные интерфейсы JCF и их реализации.
Интерфейс Collection расширяют интерфейсы:
List (список) представляет собой коллекцию, в которой допустимы дублирующие значения. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу. Реализации:
Set (сет) описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Реализации:
Queue — (очередь) предназначена для хранения элементов с предопределённым способом вставки и извлечения FIFO (first-in-first-out):
Интерфейс Map реализован классами:
Что такое «fail-fast поведение»?
fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом. Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени.
Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):
Какая разница между fail-fast и fail-safe?
В противоположность fail-fast, итераторы fail-safe не вызывают никаких исключений при изменении структуры, потому что они работают с клоном коллекции вместо оригинала.
Приведите примеры итераторов реализующих поведение fail-safe
Итератор коллекции CopyOnWriteArrayList и итератор представления keySet коллекции ConcurrentHashMap являются примерами итераторов fail-safe.
Хотя оба интерфейса и предназначены для обхода коллекций между ними имеются существенные различия:
Как избежать ConcurrentModificationException во время перебора коллекции?
Какая коллекция реализует дисциплину обслуживания FIFO?
Какая коллекция реализует дисциплину обслуживания FILO?
Comparator vs Comparable
В нем находится всего один метод:
Вы могли заметить, что метод compareTo(T o) возвращает int. Он возвращает:
Давайте посмотрим на примере. Представим, что мы хотим сравнить два дома.
Давайте у нас будет класс House:
Отлично! Но пока мы не можем сравнить два объекта типа House. Например, если мы попробуем создать TreeSet из объектов типа House (а TreeSet всегда сортирует свои элементы) и добавить туда элемент:
Теперь, давайте имплементируем Comparable:
Как видите, мы решили сортировать дома по площади.
Теперь давайте создадим три объекта House и положим их в TreeSet:
Как видите, наши дома стоят не в порядке добавления (Токио, Оксфорд, Париж), а отсортированы по площади (Оксфорд, Париж, Токио). Ну, и ошибок, естественно, тоже нет.
Интерфейс Comparator Итак, нестандартная сортировка. Допустим, мы все согласны что логичнее всего сравнивать дома по площади. Ну а если их нужно отсортировать, например, по цене?
Для этой цели мы можем создать отдельный класс, который реализует интерфейс Comparator.
Обратите внимение: мы указываем тип объектов, которые хотим сравнивать (House) в скобках после слова «Comparator».
Теперь давайте возьмем main из предыдущего примера, только поместим наши объекты не в TreeSet, а в ArrayList:
Теперь давайте создадим объект класса PriceComparator, а потом вызовем у нашего ArrayList метод sort(), который принимает на вход как раз объект класса, реализующего интерфейс Comparator, в нашем PriceComparator-а отсортируем наш ArrayList:
Наши дома отсортированы по цене.
Vector это устаревший класс и его использование не рекомендовано.
ArrayList это список, реализованный на основе массива, а LinkedList — это классический двусвязный список, основанный на объектах с ссылками между ними.
В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список.
Смотря какие действия будут выполняться над структурой.
O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.
O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.
O(N). Добавление в начало/конец списка осуществляется за время O(1).
O(N). Вставка элемента в конец списка осуществляется за время O(1), но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый.
Необходимо добавить 1 млн. элементов, какую структуру вы используете?
Однозначный ответ можно дать только исходя из информации о том в какую часть списка происходит добавление элементов, что потом будет происходить с элементами списка, существуют ли какие-то ограничения по памяти или скорости выполнения.
Допустим нужно удалить n элементов с позиции m в списке. Вместо выполнения удаления одного элемента n раз (каждый раз смещая на 1 позицию элементы, стоящие «правее» в списке), нужно выполнить смещение всех элементов, стоящих «правее» n + m позиции на n элементов «левее» к началу списка. Таким образом, вместо выполнения n итераций перемещения элементов списка, все выполняется за 1 проход.
Если в массиве достаточно места для размещения нового элемента, то дополнительной памяти не требуется. Иначе происходит создание нового массива размером в 1,5 раза превышающим существующий (это верно для JDK выше 1.7, в более ранних версиях размер увеличения иной).
Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные.
Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны: 8 + 8 + 8 + 16 = 40байт и 24 байта. Итого 64 байта.
Для ArrayList или для LinkedList операция добавления элемента в середину ( list.add(list.size()/2, newElement) ) медленнее?
Deque (Double Ended Queue) расширяет Queue и согласно документации это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса Deque могут строится по принципу FIFO, либо LIFO.
LinkedList — это односвязный, двусвязный или четырехсвязный список?
Двусвязный : каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.
Stack считается «устаревшим». Чем его рекомендуют заменять? Почему?
Hashtable это устаревший класс и его использование не рекомендовано.
В Java существует 4 типа ссылок: сильные (strong reference), мягкие (SoftReference), слабые (WeakReference) и фантомные (PhantomReference). Особенности каждого типа ссылок связаны с работой Garbage Collector. Если объект можно достичь только с помощью цепочки WeakReference (то есть на него отсутствуют сильные и мягкие ссылки), то данный объект будет помечен на удаление.
В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences?
В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences?
При добавлении элемента, который уже присутствует в LinkedHashMap (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.
Так же оно проявляется при итерации по коллекции.
HashMap реализован с использованием метода цепочек, т.е. каждой ячейке массива (корзине) соответствует свой связный список и при возникновении коллизии осуществляется добавление нового элемента в этот список.
Для метода цепочек коэффициент заполнения может быть больше 1 и с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов, либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения.
Среди методов открытой реализации различают:
Недостатки структур с методом открытой адресации:
Преимущества хэш-таблицы с открытой адресацией:
По значению hashCode() вычисляется индекс ячейки массива, в список которой этот элемент будет добавлен. Перед добавлением осуществляется проверка на наличие элементов в этой ячейке. Если элементы с таким hashCode() уже присутствует, но их equals() методы не равны, то элемент будет добавлен в конец списка.
В общем случае операции добавления, поиска и удаления элементов занимают константное время.
Это возможно в случае, если метод, определяющий номер корзины будет возвращать одинаковые значения.
Допустим, в качестве ключа используется не примитив, а объект с несколькими полями. После добавления элемента в HashMap у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хэш-кода. В результате при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот equals уже не найдет указанный ключ в списке элементов. Тем не менее, даже если equals реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хэш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет в совершенно другую корзину и тогда уже потеряется совсем.
Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняется сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента.
hashCode позволяет определить корзину для поиска элемента, а equals используется для сравнения ключей элементов в списке корзины и искомого ключа.
Сколько переходов происходит в момент вызова HashMap.get(key) по ключу, который есть в таблице?
Да, будет, но в этом случае HashMap вырождается в связный список и теряет свои преимущества.
TreeSet обеспечивает упорядоченно хранение элементов в виде красно-черного дерева. Сложность выполнения основных операций не хуже O(lg(N)).
Что будет, если добавлять элементы в TreeSet по возрастанию?
В основе TreeSet лежит красно-черное дерево, которое умеет само себя балансировать. В итоге, TreeSet все равно в каком порядке вы добавляете в него элементы, преимущества этой структуры данных будут сохраняться.
Помимо всего EnumSet предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров.
Какие существуют способы перебирать элементы списка?
Каким образом можно получить синхронизированные объекты стандартных коллекций?
Как получить коллекцию только для чтения?
Эти методы принимают коллекцию в качестве параметра, и возвращают коллекцию только для чтения с теми же элементами внутри.
Как, используя LinkedHashMap, сделать кэш c «invalidation policy»?
Стоит заметить, что LinkedHashMap не позволяет полностью реализовать LRU-алгоритм, поскольку при вставке уже имеющегося в коллекции элемента порядок итерации по элементам не меняется.
Как одной строчкой скопировать элементы любой collection в массив?
Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?
