Ответы на вопросы на собеседование Java Collections Framework (часть 3).

• В чем разница между HashMap и IdentityHashMap? Для чего нужна IdentityHashMap? Как может быть полезна для реализации сериализации или клонирования? 

• В чем разница между HashMap и WeakHashMap? Для чего нужна WeakHashMap?

• В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences?

• В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences?

• Сделайте HashSet из HashMap (используйте только множество ключей, но не множество значений).

• Сделайте HashMap из HashSet (HashSet<Map.Entry<K, V>>). 

• Сравните интерфейсы java.util.Queue и java.util.Deque.

• Почему LinkedList реализует и List, и Deque?

• В чем разница между классами java.util.Arrays и java.lang.reflect.Array?

• В чем разница между классами java.util.Collection и java.util.Collections?

• Напишите НЕмногопоточную программу, которая заставляет коллекцию выбросить ConcurrentModificationException.

• Что такое “fail-fast поведение”? 

• при изменении коллекции (удаление/добавление элемента) счетчик увеличивается; 
• при создании итератора ему передается текущее значение счетчика; 
• при каждом обращении к итератору сохраненное значение счетчика сравнивается с текущим, и, если они не совпадают, возникает исключение. 

Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени. Также стоит отметить, что fail-fast поведение не может быть абсолютно гарантировано. 

• Для множеств еnum-ов есть специальный класс java.util.EnumSet? Зачем? Чем авторов не устраивал HashSet или TreeSet? 

EnumSet - это одна из разновидностей реализации интерфейса Set для использования с перечислениями (Enum). EnumSet использует массив битов для хранения значений (bit vector), что позволяет получить высокую компактность и эффективность. В структуре данных хранятся объекты только одного типа Enum, который указывается при создании экземпляра EnumSet. Все основные операции выполняются за константное время (O(1)) и в основном несколько быстрее (хотя и негарантированно), чем их аналоги в реализации HashSet. Пакетные операции (bulk operations, например, containsAll() и retainAll()) выполняются очень быстро, если их аргументом является экземпляр типаEnum. 

Помимо этого класс EnumSet предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров. 

Итерация по EnumSet осуществляется согласно порядку объявления элементов перечисления. 

• java.util.Stack - считается «устаревшим». Чем его рекомендуют заменять? Почему? 

Рекомендуется использовать интерфейс Deque ("дек", Double Ended Queue) и его реализации. Например: 

Стек - это структура данных, построенная на принципе LIFO (Last-In-First-Out, либо по-другому FILO). Каждое новое значение добавляется на "вершину" стека, а извлекается последний добавленный элемент (с "вершины" стека). При извлечении элемента он удаляется из структуры данных.

Класс Stack появился в JDK 1.0 и расширяет класс Vector, наследуя его функционал, что несколько нарушает понятие стека (например, класс Vector предоставляет возможность обращаться к любому элементу по индексу). Также использование Deque позволяет следовать принципу программирования на уровне интерфейсов, а не конкретных реализаций, что облегчает дальнейшую поддержку разрабатываемого класса и повышает его гибкость, позволяя при необходимости менять реализацию дека на нужную.

• Какая коллекция реализует дисциплину обслуживания FIFO?

FIFO - First-In-First-Out (первый пришел, первым ушел). По этому принципу обычно построена такая структура данных как очередь (java.util.Queue).

• Какая коллекция реализует дисциплину обслуживания FILO?

FILO - First-In-Last-Out (первый пришел, последним ушел). По этому принципу построена такая структура данных как стек (java.util.Stack).

• Приведите пример, когда какая-либо коллекция выбрасывает UnsupportedOperationException.

В данном примере возникнет исключение UnsupportedOperationException, поскольку метод asList() возвращает список фиксированной длины, т.е. удаление/добавление элементов в такой список не поддерживается.

• Почему нельзя написать “ArrayList<List> numbers = new ArrayList<ArrayList>();” но можно “List<ArrayList> numbers = new ArrayList<ArrayList>();”?

Это связано с ограничениями использования generic types (обобщенных типов). ArrayList<ArrayList> не является подтипом ArrayList<List>, соответственно использование такой записи запрещено.

• LinkedHashMap - что это еще за «зверь»? Что в нем от LinkedList, а что от HashMap? 

Реализация LinkedHashMap отличается от HashMap поддержкой двухсвязанного списка, определяющего порядок итерации по элементам структуры данных. По умолчанию элементы списка упорядочены согласно их порядку добавления в LinkedHashMap (insertion-order). Однако порядок итерации можно изменить, установив параметр конструктора accessOrder в значение true. В этом случае доступ осуществляется по порядку последнего обращения к элементу (access-order). Это означает, что при вызове методов get() или put() элемент, к которому обращаемся, перемещается в конец списка.

При добавлении элемента, который уже присутствует в LinkedHashMap (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.

• LinkedHashSet - что это еще за «зверь»? Что в нем от LinkedList, а что от HashSet?

Реализация LinkedHashSet отличается от HashSet поддержкой двухсвязанного списка, определяющего порядок итерации по элементам структуры данных. Элементы списка упорядочены согласно их порядку добавления в LinkedHashSet (insertion-order).

При добавлении элемента, который уже присутствует в LinkedHashSet (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.

• Говорят, на LinkedHashMap легко сделать простенький кэш c “invalidation policy”, знаете как?

Необходимо использовать LRU-алгоритм (Least Recently Used algorithm) и LinkedHashMap с access-order. В этом случае при обращении к элементу он будет перемещаться в конец списка, а наименее используемые элементы будут постепенно группироваться в начале списка.

Для этого в стандартной реализации LinkedHashMap (source) есть метод

removeEldestEntries(), который возвращает true, если текущий объект LinkedHashMap

должен удалить наименее используемый элемент из коллекции. Метод вызывается при использовании методов put() и putAll():

Простой пример реализации кэша с очисткой старых значений при превышении указанного порога:

Стоит заметить, что LinkedHashMap не позволяет полностью реализовать LRU-алгоритм, поскольку при вставке уже имеющегося в коллекции элемента порядок итерации не меняется.

• Что позволяет сделать PriorityQueue?

PriorityQueue - это структура данных, располагающая элементы в порядке натурального упорядочивания, либо используя переданный конструктору Comparator.

Используя PriorityQueue, можно, например, реализовать алгоритм Дейкстры для поиска кратчайшего пути от одной вершины графа к другой. Либо применять для хранения объектов согласно их приоритету: например, сортировка пациентов врача - экстренные пациенты перемещаются в начало очереди, менее срочные пациенты - ближе к концу очереди.

• В чем заключаются отличия java.util.Comparator от java.lang.Comparable?

Interface Comparable задает свойство сравнения объекту реализующему его. То есть делает объект сравнимым (по правилам разработчика).

Interface Comparator позволяет создавать объекты, которые будут управлять процессом сравнения (например при сортировках).