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

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

IdentityHashMap - это структура данных, реализующая интерфейс Map, но использующая сравнение ссылок вместо метода equals() при сравнении ключей (значений). Другими словами, в IdentityHashMap два ключа k1 и k2 будут рассматриваться равными, если выполняется условие k1 == k2.
IdentityHashMap не использует метод hashCode(), вместо которого применяется метод System.identityHashCode(Object).
Другое отличие (как следствие) заключается в более высокой производительности IdentityHashMap по сравнению с HashMap, если последний хранит объекты с дорогостоящими методами equals() и hashCode().
Одним из основных требований к использованию HashMap является неизменяемость
ключа, однако это требование не распространяется на IdentityHashMap, который не использует методы equals() и hashCode().
Согласно документации, такая структура данных может применяться для реализации сериализации/клонирования. Для выполнения подобных алгоритмов программе необходимо обслуживать таблицу со всеми ссылками на объекты, которые уже были обработаны. Такая таблица не должна рассматривать уникальные объекты как равные, даже если метод equals() возвращает true.

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

Перед рассмотрением WeakHashMap кратко напомню, что такое WeakReference. В Java существует 4 типа ссылок: сильные (strong reference), мягкие (SoftReference), слабые (WeakReference) и фантомные (PhantomReference). Особенности каждого типа ссылок связаны с работой Garbage Collector. Если объект можно достичь только с помощью цепочки WeakReference (то есть на него не ссылаются сильные и мягкие ссылки), то данный объект будет отмечен для удаления.
WeakHashMap - это структура данных, реализующая интерфейс Map и основанная на использовании WeakReference для хранения ключей. Таким образом, пара "ключ-значение" будет удалена из WeakHashMap, если на объект-ключ более не имеется сильных ссылок.
В качестве примера использования такой структуры данных можно привести следующую ситуацию: допустим имеются объекты, которые необходимо расширить дополнительной информацией, при этом изменение класса этих объектов нежелательно либо невозможно. В этом случае добавляем каждый объект в WeakHashMap в качестве ключа, а в качестве значения - нужную информацию. Таким образом, пока на объект имеется сильная ссылка (либо мягкая), можно проверять хэш-таблицу и извлекать информацию. Как только объект будет удален, то WeakReference для этого ключа будет помещен в ReferenceQueue и затем соответствующая запись для этой слабой ссылки будет удалена из WeakHashMap.

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

SoftHashMap представлена в стронних библиотеках, например, в Apache Commons.

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

PhantomReference при вызове метода get() возвращает всегда null, поэтому, я думаю, создание PhantomHashMap просто невозможно. Плюс назначение такой структуры данных тяжело представить.

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


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

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

Согласно документации Deque ("дек", Double Ended Queue) - это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса Deque могут строится по принципу FIFO, либо LIFO.
Queue - это очередь, обычно (но необязательно) строится по принципу FIFO (First-In-First-Out) - соответственно извлечение элемента осуществляется с начала очереди, вставка элемента - в конец очереди. Этот принцип нарушает, к примеру, приоритетная очередь (PriorityQueue), использующая переданный comparator при вставке нового элемента, либо расстановка элементов осуществляется согласно естественному упорядочиванию (natural ordering).
Deque расширяет Queue.
Реализации и Deque, и Queue обычно не переопределяют методы equals() и hashCode(), основанные на сравнении хранящихся элементов. Вместо этого используются унаследованные методы класса Object, основанные на сравнении ссылок.


  • Кто кого расширяет: Queue расширяет Deque, или Deque расширяет Queue?

Deque расширяет Queue.

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

LinkedList позволяет добавлять элементы в начало и конец списка за константное время, что хорошо подходит для реализации интерфейса Deque (в отличие, например, от ArrayList).

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

java.util.Arrays - класс, содержащий статические методы для работы с массивами, таких как, например, поиск по массиву и его сортировка.
java.lang.reflect.Array - класс для работы с массивами при использовании рефлексии. Рефлексия - это механизм, позволяющий исследовать данные о программе во время её выполнения.

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

Класс java.util.Collections содержит исключительно статические методы для работы с коллекциями. В них входят методы, реализующие полиморфные алгоритмы (такие алгоритмы, использование которых возможно с разными видами структур данных), "оболочки", возвращающие новую коллекцию с инкапсулированной указанной структурой данных и некоторые другие методы.
java.util.Collection - это корневой интерфейс Java Collections Framework. Этот интерфейс в основном применяется там, где требуется высокий уровень абстракции, например, в классе java.util.Collections.

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


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


Fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом. 
В Java Collections API итераторы могут использовать либо fail-fast, либо fail-safe поведение, либо быть weakly consistent. Итератор с fail-fast поведением выбросит исключение ConcurrentModificationException, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент (без использования метода remove() итератора). Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count): 
  • при изменении коллекции (удаление/добавление элемента) счетчик увеличивается; 
  • при создании итератора ему передается текущее значение счетчика; 
  • при каждом обращении к итератору сохраненное значение счетчика сравнивается с текущим, и, если они не совпадают, возникает исключение. 
Использование 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 позволяет создавать объекты, которые будут управлять процессом сравнения (например при сортировках).


Рассказать друзьям:

3 коментарі :

  1. Спасибо за ресурс, но над навигацией нужно поработать

    ОтветитьУдалить
  2. У меня глаза заболели на первом вопросе... Тернарный оператор работает не так как вы его используете! k1==null ? k2==null : k1.equals(k2). Тут написано: сравни к1 и нулл! если да то сравни к2 с нулл, если нет то давай сравним через иквалз! Это даже не компилится! В вашем случае нужно чтобы выполнялось 3 условия! (k1==null && k2==null && k1.equals(k2)).

    ОтветитьУдалить
  3. Да, с навигацией беда, особенно на планшете.

    ОтветитьУдалить