Продолжение ответов на вопросы.

1 часть.
2 часть.

Другое

1. Сравните интерфейсы 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, основанные на сравнении ссылок.

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

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

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

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

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

java.util.Arrays - класс, содержащий статические методы для работы с массивами, таких как, например, поиск по массиву и его сортировка.

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

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

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

java.util.Collection - это корневой интерфейс Java Collections Framework. Этот интерфейс в основном применяется там, где требуется высокий уровень абстракции, например, в классе java.util.Collections.

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

List<String> stringList = new ArrayList<>();
stringList.add("1");
stringList.add("2");
stringList.add("3");

Iterator<String> listIterator = stringList.iterator();
stringList.remove("2");
while (listIterator.hasNext()) {
    System.out.println(listIterator.next());
}

7. Что такое «fail-fast поведение»?

Fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом.

В Java Collections API итераторы могут использовать либо fail-fast, либо fail-safe поведение, либо быть weakly consistent. Итератор с fail-fast поведением выбросит исключение ConcurrentModificationException, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент (без использования метода remove() итератора). Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):

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

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

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

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

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

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

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

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

Deque<Integer> stack = new ArrayDeque<Integer>();

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

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

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

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

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

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

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

List fixedList = Arrays.asList("1", "2", "3");
Iterator<String> listIterator = fixedList.iterator();
while (iterator.hasNext()) {
    String currentElement = iterator.next();
    if ("2".equals(currentElement)) {
        iterator.remove();
    }
}

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

13. Почему нельзя написать ArrayList<List> numbers = new ArrayList<ArrayList>(), но можно List<ArrayList> numbers = new ArrayList<ArrayList>()?

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

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

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

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

Хорошая статья по этой теме - Структуры данных в картинках. LinkedHashMap.

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

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

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

16. Говорят, на LinkedHashMap легко сделать простенький кэш c «invalidation policy», знаете как?

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

Для этого в стандартной реализации LinkedHashMap (source) есть метод removeEldestEntries(), который возвращает true, если текущий объект LinkedHashMap должен удалить наименее используемый элемент из коллекции. Метод вызывается при использовании методов put() и putAll():

void addEntry(int hash, K key, V value, int bucketIndex) {
    createEntry(hash, key, value, bucketIndex);

    // Remove eldest entry if instructed, else grow capacity if appropriate
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    } else {
        if (size >= threshold)
            resize(2 * table.length);
    }
}

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final int MAX_ENTRIES = 10;

    public LRUCache(int initialCapacity) {
        // Изменяем порядок итерации на access order.
        super(initialCapacity, 0.85f, true);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_ENTRIES;
    }
}

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

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

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

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