Skip to content

Latest commit

 

History

History
1275 lines (979 loc) · 119 KB

Cобеседование по Java. Java Collections.md

File metadata and controls

1275 lines (979 loc) · 119 KB
Raw

Cобеседование по Java. Разбор вопросов и ответов.

     

Нажмите ★, если вам нравится проект. Ваш вклад сердечно ♡ приветствуется.

Если вам интересно мое резюме: https://github.com/DEBAGanov

Java Collections:

Java Collections Framework

Что такое «коллекция»?

«Коллекция» - это структура данных, набор каких-либо объектов. Данными (объектами в наборе) могут быть числа, строки, объекты пользовательских классов и т.п.

к оглавлению

Назовите основные интерфейсы JCF и их реализации.

На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection и Map. Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» соответственно.

Image alt

Интерфейс Collection расширяют интерфейсы:

  • List (список) представляет собой коллекцию, в которой допустимы дублирующие значения. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу. Реализации:

    • ArrayList - инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов. Позволяет хранить любые данные, включая null в качестве элемента.
    • LinkedList (двунаправленный связный список) - состоит из узлов, каждый из которых содержит как собственно данные, так и две ссылки на следующий и предыдущий узел. Позволяет хранить любые данные, включая null.
    • Vector — реализация динамического массива объектов, методы которой синхронизированы. Позволяет хранить любые данные, включая null в качестве элемента. Синхронизирован, но как и Hashtable, эту коллекцию не рекомендуется использовать, если не требуется достижения потокобезопасности.
      • Stack — реализация стека LIFO (last-in-first-out). Является частично синхронизированной коллекцией (кроме метода добавления push()

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

    • HashSet - использует HashMap для хранения данных. В качестве ключа используется добавляемый элемент, а в качестве значения — объект-пустышка new Object(). Из-за особенностей реализации порядок элементов не гарантируется при добавлении.
      • LinkedHashSet — гарантирует, что порядок элементов при обходе коллекции будет идентичен порядку добавления элементов.
    • SortedSet — расширяющий интерфейс Set, описывает упорядоченное множество, отсортированное в возрастающем порядке или по порядку, заданному реализацией интерфейса Comparator.
    • TreeSet — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».

  • Queue — (очередь) предназначена для хранения элементов с предопределённым способом вставки и извлечения FIFO (first-in-first-out):

    • PriorityQueue — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».
    • интерфейс Deque — расширяет вышеописанный интерфейс Queue и определяет поведение двунаправленной очереди, которая работает как обычная однонаправленная очередь, либо как стек, действующий по принципу LIFO (последний вошел - первый вышел).
      • ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out).

Интерфейс Map реализован классами:

  • WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references для ключей (сборщик мусора автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элемента нет жёстких ссылок).
  • Hashtable — хэш-таблица, методы которой синхронизированы. Не позволяет использовать null в качестве значения или ключа и не является упорядоченной.
  • HashMap — хэш-таблица. Не синхронизирована, позволяет использовать null в качестве значения или ключа и не является упорядоченной.
    • LinkedHashMap — упорядоченная реализация хэш-таблицы, благодаря двунаправленным связям между элементами (аналогично LinkedList)
  • интерфейс SortesMap
    • интерфейс NavigableMap
      • TreeMap — реализация основанная на красно-чёрных деревьях. Является упорядоченной и предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».

Image alt

к оглавлению

Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection, Iterable, Iterator, NavigableSet, NavigableMap.

  • 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.Collections - набор статических методов для работы с коллекциями.

java.util.Collection - один из основных интерфейсов Java Collections Framework.

к оглавлению

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

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

В Java Collections API некоторые итераторы ведут себя как fail-fast и выбрасывают ConcurrentModificationException, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент напрямую из коллекции, а не используя методы итератора.

Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):

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

к оглавлению

Какая разница между fail-fast и fail-safe?

В противоположность fail-fast, итераторы fail-safe не вызывают никаких исключений при изменении структуры, потому что они работают с клоном коллекции вместо оригинала.

к оглавлению

Приведите примеры итераторов реализующих поведение fail-safe

Итератор коллекции CopyOnWriteArrayList и итератор представления keySet коллекции ConcurrentHashMap являются примерами итераторов fail-safe.

к оглавлению

Чем различаются Enumeration и 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.

к оглавлению

Сравните Iterator и ListIterator.

  • ListIterator расширяет интерфейс Iterator
  • ListIterator может быть использован только для перебора элементов коллекции List;
  • Iterator позволяет перебирать элементы только в одном направлении, при помощи метода next(). Тогда как ListIterator позволяет перебирать список в обоих направлениях, при помощи методов next() и previous();
  • ListIterator не указывает на конкретный элемент: его текущая позиция располагается между элементами, которые возвращают методы previous() и next().
  • При помощи ListIterator вы можете модифицировать список, добавляя/удаляя элементы с помощью методов add() и remove(). Iterator не поддерживает данного функционала.

к оглавлению

Что произойдет при вызове Iterator.next() без предварительного вызова Iterator.hasNext()?

Если итератор указывает на последний элемент коллекции, то возникнет исключение NoSuchElementException, иначе будет возвращен следующий элемент.

к оглавлению

Сколько элементов будет пропущено, если Iterator.next() будет вызван после 10-ти вызовов Iterator.hasNext()?

Нисколько - hasNext() осуществляет только проверку наличия следующего элемента.

к оглавлению

Как поведёт себя коллекция, если вызвать iterator.remove()?

Если вызову iterator.remove() предшествовал вызов iterator.next(), то iterator.remove() удалит элемент коллекции, на который указывает итератор, в противном случае будет выброшено IllegalStateException().

к оглавлению

Как поведёт себя уже инстанциированный итератор для collection, если вызвать collection.remove()?

При следующем вызове методов итератора будет выброшено ConcurrentModificationException.

к оглавлению

Как избежать ConcurrentModificationException во время перебора коллекции?

  • Попробовать подобрать другой итератор, работающий по принципу fail-safe. К примеру, для List можно использовать ListIterator.
  • Использовать ConcurrentHashMap и CopyOnWriteArrayList.
  • Преобразовать список в массив и перебирать массив.
  • Блокировать изменения списка на время перебора с помощью блока synchronized.

Отрицательная сторона последних двух вариантов - ухудшение производительности.

к оглавлению

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

FIFO, First-In-First-Out («первым пришел-первым ушел») - по этому принципу построена коллекция Queue.

к оглавлению

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

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

к оглавлению

Comparator vs Comparable

Интерфейс Comparable

В нем находится всего один метод:

public interface Comparable<T> {
    public int compareTo(T o);
}

Вы могли заметить, что метод compareTo(T o) возвращает int. Он возвращает:

  • ноль, если два объекта равны;
  • +1, если первый объект (на котором вызывается метод) больше, чем второй (который передается в качестве параметра);
  • -1, если первый объект меньше второго.

Давайте посмотрим на примере. Представим, что мы хотим сравнить два дома.

Давайте у нас будет класс House:

public class House {
    int area;
    int price;
    String city;
    boolean hasFurniture;
}

Как Вы можете видеть, у нас есть четыре параметра - размер дома, цена, город, в котором дом находится, и boolean "hasFurniture" ("продается ли дом с мебелью"). Мы НЕ сделали эти переменные приватными чтобы не отягощать код и не писать гетеры и сеттеры на каждый параметр - но Вы для практики можете это сделать 🙂 Давайте просто добавим конструктор и метод "вывести все параметры":

public class House {
    int area;
    int price;
    String city;
    boolean hasFurniture;
    
    public House(int area, int price, String city, boolean hasFurniture)
    {
        this.area = area;
        this.price = price;
        this.city = city;
        this.hasFurniture = hasFurniture;
    }
    
    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("House{");
            sb.append("area=").append(area);
            sb.append(", price=").append(price);
            sb.append(", city='").append(city).append('\'');
            sb.append(", hasFurniture=").append(hasFurniture);
            sb.append('}');
        return sb.toString();
    }
}

Отлично! Но пока мы не можем сравнить два объекта типа House. Например, если мы попробуем создать TreeSet из объектов типа House (а TreeSet всегда сортирует свои элементы) и добавить туда элемент:

public class Test {

    public static void main(String[] args) {

       TreeSet<House> myHouseArrayList = new TreeSet<House>();

        House firstHouse = new House(100, 120000, "Tokyo", true);

        myHouseArrayList.add(firstHouse);
    }
}

получим ошибку. TreeSet сортирует свои элементы - но в данном случае сортировать у него не получится, поскольку он не знает, по какому критерию нужно сортировать

Теперь, давайте имплементируем Comparable:

public class House implements Comparable<House>{
    int area;
    int price;
    String city;
    boolean hasFurniture;

    public House(int area, int price, String city, boolean hasFurniture)
    {
        this.area = area;
        this.price = price;
        this.city = city;
        this.hasFurniture = hasFurniture;
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("House{");
            sb.append("area=").append(area);
            sb.append(", price=").append(price);
            sb.append(", city='").append(city).append('\'');
            sb.append(", hasFurniture=").append(hasFurniture);
            sb.append('}');
        return sb.toString();
    }

    public int compareTo(House anotherHouse)
    {
        if (this.area == anotherHouse.area) {
            return 0;
        } else if (this.area < anotherHouse.area) {
            return -1;
        } else {
            return 1;
        }
    }
}

Как видите, мы решили сортировать дома по площади.

Теперь давайте создадим три объекта House и положим их в TreeSet:

public class Test {

    public static void main(String[] args) {

       TreeSet<House> myHouseArrayList = new TreeSet<House>();

        House firstHouse = new House(100, 120000, "Tokyo", true);
        House secondHouse = new House(40, 70000, "Oxford", true);
        House thirdHouse = new House(70, 180000, "Paris", false);

        myHouseArrayList.add(firstHouse);
        myHouseArrayList.add(secondHouse);
        myHouseArrayList.add(thirdHouse);

        for (House h: myHouseArrayList) {
            System.out.println(h);
        }
    }
}

На экране получим:

Area: 40, price: 70000, city: Oxford, hasFurniture: true
Area: 70, price: 180000, city: Paris, hasFurniture: false
Area: 100, price: 120000, city: Tokyo, hasFurniture: true

Process finished with exit code 0

Как видите, наши дома стоят не в порядке добавления (Токио, Оксфорд, Париж), а отсортированы по площади (Оксфорд, Париж, Токио). Ну, и ошибок, естественно, тоже нет.

Кстати, метод compareTo(T o), который требует реализовать интерфейс Comparable, часто называют "естественным сравнением" ("natural comparison method") - т.е. методом по умолчанию. Основные типы (например, Integer, String, Float) уже имеют свои методы compareTo(T o).

Тем не менее, если Вам нужен "нестандартный" вид сортировки - следует использовать Comparator.

Интерфейс Comparator Итак, нестандартная сортировка. Допустим, мы все согласны что логичнее всего сравнивать дома по площади. Ну а если их нужно отсортировать, например, по цене?

Для этой цели мы можем создать отдельный класс, который реализует интерфейс Comparator.

Например, у нас уже есть класс House. Давайте создадим отдельный класс, которые будут выполнять функцию сравнения - PriceComparator:

public class PriceComparator implements Comparator<House> {

    public int compare(House h1, House h2) {
        if (h1.price == h2.price) {
            return 0;
        }
        if (h1.price > h2.price) {
            return 1;
        }
        else {
            return -1;
        }
    }
}

Обратите внимение: мы указываем тип объектов, которые хотим сравнивать (House) в скобках после слова "Comparator".

Теперь давайте возьмем main из предыдущего примера, только поместим наши объекты не в TreeSet, а в ArrayList:

public class Test {

    public static void main(String[] args) {

       ArrayList<House> myHouseArrayList = new ArrayList<House>();

        House firstHouse = new House(100, 120000, "Tokyo", true);
        House secondHouse = new House(40, 70000, "Oxford", true);
        House thirdHouse = new House(70, 180000, "Paris", false);

        myHouseArrayList.add(firstHouse);
        myHouseArrayList.add(secondHouse);
        myHouseArrayList.add(thirdHouse);

        for (House h: myHouseArrayList) {
            System.out.println(h);
        }
    }
}

Если запустить этот код, то мы увидим, что все наши элементы лежат в порядке добавление - т.е. они не отсортированы.

Теперь давайте создадим объект класса PriceComparator, а потом вызовем у нашего ArrayList метод sort(), который принимает на вход как раз объект класса, реализующего интерфейс Comparator, в нашем PriceComparator-а отсортируем наш ArrayList:

public class Test {

    public static void main(String[] args) {

       ArrayList<House> myHouseArrayList = new ArrayList<House>();

        House firstHouse = new House(100, 120000, "Tokyo", true);
        House secondHouse = new House(40, 70000, "Oxford", true);
        House thirdHouse = new House(70, 180000, "Paris", false);

        myHouseArrayList.add(firstHouse);
        myHouseArrayList.add(secondHouse);
        myHouseArrayList.add(thirdHouse);

        for (House h: myHouseArrayList) {
            System.out.println(h);
        }

        PriceComparator myPriceComparator = new PriceComparator();
        myHouseArrayList.sort(myPriceComparator);

        System.out.println("Sorted: ");
        for (House h: myHouseArrayList) {
            System.out.println(h);
        }
    }
}

В консоли получим:

Area: 100, price: 120000, city: Tokyo, hasFurniture: true
Area: 40, price: 70000, city: Oxford, hasFurniture: true
Area: 70, price: 180000, city: Paris, hasFurniture: false
Sorted: 
Area: 40, price: 70000, city: Oxford, hasFurniture: true
Area: 100, price: 120000, city: Tokyo, hasFurniture: true
Area: 70, price: 180000, city: Paris, hasFurniture: false

Process finished with exit code 0

Наши дома отсортированы по цене.

Чем отличается ArrayList от Vector?

Зачем добавили ArrayList, если уже был Vector?

  • Методы класса Vector синхронизированы, а ArrayList - нет;
  • По умолчанию, Vector удваивает свой размер, когда заканчивается выделенная под элементы память. ArrayList же увеличивает свой размер только на половину.

Vector это устаревший класс и его использование не рекомендовано.

к оглавлению

Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй?

ArrayList это список, реализованный на основе массива, а LinkedList — это классический двусвязный список, основанный на объектах с ссылками между ними.

ArrayList:

  • доступ к произвольному элементу по индексу за время O(1);
  • доступ к элементам по значению за линейное время O(N);
  • вставка в конец в среднем производится за время O(1);
  • удаление произвольного элемента из списка занимает значительное время т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку влево (реальный размер массива (capacity) не изменяется);
  • вставка элемента в произвольное место списка занимает значительное время т.к. при этом все элементы находящиеся «правее» смещаются на одну ячейку вправо;
  • минимум накладных расходов при хранении.

LinkedList:

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

В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список.

к оглавлению

Что работает быстрее ArrayList или LinkedList?

Смотря какие действия будут выполняться над структурой.

см. Чем отличается ArrayList от LinkedList

к оглавлению

Какое худшее время работы метода contains() для элемента, который есть в LinkedList?

O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.

к оглавлению

Какое худшее время работы метода contains() для элемента, который есть в ArrayList?

O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.

к оглавлению

Какое худшее время работы метода add() для LinkedList?

O(N). Добавление в начало/конец списка осуществляется за время O(1).

к оглавлению

Какое худшее время работы метода add() для ArrayList?

O(N). Вставка элемента в конец списка осуществляется за время O(1), но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый.

к оглавлению

Необходимо добавить 1 млн. элементов, какую структуру вы используете?

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

см. Чем отличается ArrayList от LinkedList

к оглавлению

Как происходит удаление элементов из ArrayList? Как меняется в этом случае размер ArrayList?

При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево и реальный размер массива (его емкость, capacity) не изменяется никак. Механизм автоматического «расширения» массива существует, а вот автоматического «сжатия» нет, можно только явно выполнить «сжатие» командой trimToSize().

к оглавлению

Предложите эффективный алгоритм удаления нескольких рядом стоящих элементов из середины списка, реализуемого ArrayList.

Допустим нужно удалить n элементов с позиции m в списке. Вместо выполнения удаления одного элемента n раз (каждый раз смещая на 1 позицию элементы, стоящие «правее» в списке), нужно выполнить смещение всех элементов, стоящих «правее» n + m позиции на n элементов «левее» к началу списка. Таким образом, вместо выполнения n итераций перемещения элементов списка, все выполняется за 1 проход.

к оглавлению

Сколько необходимо дополнительной памяти при вызове ArrayList.add()?

Если в массиве достаточно места для размещения нового элемента, то дополнительной памяти не требуется. Иначе происходит создание нового массива размером в 1,5 раза превышающим существующий (это верно для JDK выше 1.7, в более ранних версиях размер увеличения иной).

к оглавлению

Сколько выделяется дополнительно памяти при вызове LinkedList.add()?

Создается один новый экземпляр вложенного класса Node.

к оглавлению

Оцените количество памяти на хранение одного примитива типа byte в LinkedList?

Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные.

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
//...
}

Для 32-битных систем каждая ссылка занимает 32 бита (4 байта). Сам объект (заголовок) вложенного класса Node занимает 8 байт. 4 + 4 + 4 + 8 = 20 байт, а т.к. размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типа byte занимает 1 байт памяти, но в JCF примитивы упаковываются: объект типа Byte занимает в памяти 16 байт (8 байт на заголовок объекта, 1 байт на поле типа byte и 7 байт для кратности 8). Также напомню, что значения от -128 до 127 кэшируются и для них новые объекты каждый раз не создаются. Таким образом, в x32 JVM 24 байта тратятся на хранение одного элемента в списке и 16 байт - на хранение упакованного объекта типа Byte. Итого 40 байт.

Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны: 8 + 8 + 8 + 16 = 40байт и 24 байта. Итого 64 байта.

к оглавлению

Оцените количество памяти на хранение одного примитива типа byte в ArrayList?

ArrayList основан на массиве, для примитивных типов данных осуществляется автоматическая упаковка значения, поэтому 16 байт тратится на хранение упакованного объекта и 4 байта (8 для x64) - на хранение ссылки на этот объект в самой структуре данных. Таким образом, в x32 JVM 4 байта используются на хранение одного элемента и 16 байт - на хранение упакованного объекта типа Byte. Для x64 - 8 байт и 24 байта соотвтетсвенно.

к оглавлению

Для ArrayList или для LinkedList операция добавления элемента в середину (list.add(list.size()/2, newElement)) медленнее?

Для ArrayList:

  • проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив (O(N));
  • копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо (O(N));
  • вставка элемента (O(1)).

Для LinkedList:

  • поиск позиции вставки (O(N));
  • вставка элемента (O(1)).

В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет вызова быстрого системного метода System.arraycopy().

к оглавлению

В реализации класса ArrayList есть следующие поля: Object[] elementData, int size. Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?

Размер массива elementData представляет собой вместимость (capacity) ArrayList, которая всегда больше переменной size - реального количества хранимых элементов. При необходимости вместимость автоматически возрастает.

к оглавлению

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

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

Queue - это очередь, которая обычно (но необязательно) строится по принципу FIFO (First-In-First-Out) - соответственно извлечение элемента осуществляется с начала очереди, вставка элемента - в конец очереди. Хотя этот принцип нарушает, к примеру PriorityQueue, использующая «natural ordering» или переданный Comparator при вставке нового элемента.

Deque (Double Ended Queue) расширяет Queue и согласно документации это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса Deque могут строится по принципу FIFO, либо LIFO.

Реализации и Deque, и Queue обычно не переопределяют методы equals() и hashCode(), вместо этого используются унаследованные методы класса Object, основанные на сравнении ссылок.

к оглавлению

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

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

к оглавлению

LinkedList — это односвязный, двусвязный или четырехсвязный список?

Двусвязный: каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.

к оглавлению

Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)?

Для этого в LinkedList есть обратный итератор, который можно получить вызва метод descendingIterator().

к оглавлению

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

Особенностью PriorityQueue является возможность управления порядком элементов. По-умолчанию, элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта Comparator, который задаётся при создании очереди. Данная коллекция не поддерживает null в качестве элементов.

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

к оглавлению

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

Stack был добавлен в Java 1.0 как реализация стека LIFO (last-in-first-out) и является расширением коллекции Vector, хотя это несколько нарушает понятие стека (например, класс Vector предоставляет возможность обращаться к любому элементу по индексу). Является частично синхронизированной коллекцией (кроме метода добавления push()) с вытекающими отсюда последствиями в виде негативного воздействия на производительность. После добавления в Java 1.6 интерфейса Deque, рекомендуется использовать реализации именно этого интерфейса, например ArrayDeque.

к оглавлению

Зачем нужен HashMap, если есть Hashtable?

  • Методы класса Hashtable синхронизированы, что приводит к снижению производительности, а HashMap - нет;
  • HashTable не может содержать элементы null, тогда как HashMap может содержать один ключ null и любое количество значений null;
  • Iterator у HashMap, в отличие от Enumeration у HashTable, работает по принципу «fail-fast» (выдает исключение при любой несогласованности данных).

Hashtable это устаревший класс и его использование не рекомендовано.

к оглавлению

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

IdentityHashMap - это структура данных, так же реализующая интерфейс Map и использующая при сравнении ключей (значений) сравнение ссылок, а не вызов метода equals(). Другими словами, в IdentityHashMap два ключа k1 и k2 будут считаться равными, если они указывают на один объект, т.е. выполняется условие k1 == k2.

IdentityHashMap не использует метод hashCode(), вместо которого применяется метод System.identityHashCode(), по этой причине IdentityHashMap по сравнению с HashMap имеет более высокую производительность, особенно если последний хранит объекты с дорогостоящими методами equals() и hashCode().

Одним из основных требований к использованию HashMap является неизменяемость ключа, а, т.к. IdentityHashMap не использует методы equals() и hashCode(), то это правило на него не распространяется.

IdentityHashMap может применяться для реализации сериализации/клонирования. При выполнении подобных алгоритмов программе необходимо обслуживать хэш-таблицу со всеми ссылками на объекты, которые уже были обработаны. Такая структура не должна рассматривать уникальные объекты как равные, даже если метод equals() возвращает true.

к оглавлению

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

В 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, поэтому тяжело представить назначение такой структуры данных.

к оглавлению

LinkedHashMap - что в нем от LinkedList, а что от HashMap?

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

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

к оглавлению

В чем проявляется «сортированность» SortedMap, кроме того, что toString() выводит все элементы по порядку?

Так же оно проявляется при итерации по коллекции.

к оглавлению

Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресации и на основе метода цепочек. Как реализована HashMap? Почему, по вашему мнению, была выбрана именно эта реализация? В чем плюсы и минусы каждого подхода?

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

Для метода цепочек коэффициент заполнения может быть больше 1 и с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов, либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения.

Среди методов открытой реализации различают:

  • линейное пробирование;
  • квадратичное пробирование;
  • двойное хэширование.

Недостатки структур с методом открытой адресации:

  • Количество элементов в хэш-таблице не может превышать размера массива. По мере увеличения числа элементов и повышения коэффициента заполнения производительность структуры резко падает, поэтому необходимо проводить перехэширование.
  • Сложно организовать удаление элемента.
  • Первые два метода открытой адресации приводят к проблеме первичной и вторичной группировок.

Преимущества хэш-таблицы с открытой адресацией:

  • отсутствие затрат на создание и хранение объектов списка;
  • простота организации сериализации/десериализации объекта.

к оглавлению

Как работает HashMap при попытке сохранить в него два элемента по ключам с одинаковым hashCode(), но для которых equals() == false?

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

к оглавлению

Какое начальное количество корзин в HashMap?

В конструкторе по умолчанию - 16, используя конструкторы с параметрами можно задавать произвольное начальное количество корзин.

к оглавлению

Какова оценка временной сложности операций над элементами из HashMap? Гарантирует ли HashMap указанную сложность выборки элемента?

В общем случае операции добавления, поиска и удаления элементов занимают константное время.

Данная сложность не гарантируется, т.к. если хэш-функция распределяет элементы по корзинам равномерно, временная сложность станет не хуже O(lg(N)), а в случае, когда хэш-функция постоянно возвращает одно и то же значение HashMap превратится в связный список со сложностью О(n) .

к оглавлению

Возможна ли ситуация, когда HashMap выродится в список даже с ключами имеющими разные hashCode()?

Это возможно в случае, если метод, определяющий номер корзины будет возвращать одинаковые значения.

к оглавлению

В каком случае может быть потерян элемент в HashMap?

Допустим, в качестве ключа используется не примитив, а объект с несколькими полями. После добавления элемента в HashMap у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хэш-кода. В результате при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот equals уже не найдет указанный ключ в списке элементов. Тем не менее, даже если equals реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хэш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет в совершенно другую корзину и тогда уже потеряется совсем.

к оглавлению

Почему нельзя использовать byte[] в качестве ключа в HashMap?

Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняется сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента.

к оглавлению

Какова роль equals() и hashCode() в HashMap?

hashCode позволяет определить корзину для поиска элемента, а equals используется для сравнения ключей элементов в списке корзины и искомого ключа.

к оглавлению

Каково максимальное число значений hashCode()?

Число значений следует из сигнатуры int hashCode() и равно диапазону типа int — 232.

к оглавлению

Какое худшее время работы метода get(key) для ключа, которого нет в HashMap?

O(N). Худший случай - это поиск ключа в HashMap, вырожденного в список по причине совпадения ключей по hashCode() и для выяснения хранится ли элемент с определённым ключом может потребоваться перебор всего списка.

к оглавлению

Сколько переходов происходит в момент вызова HashMap.get(key) по ключу, который есть в таблице?

  • ключ равен null: 1 - выполняется единственный метод getForNullKey().
  • любой ключ отличный от null: 4 - вычисление хэш-кода ключа; определение номера корзины; поиск значения; возврат значения.

к оглавлению

Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap?

Один новый объект статического вложенного класса Entry<K,V>.

к оглавлению

Как и когда происходит увеличение количества корзин в HashMap?

Помимо capacity у HashMap есть еще поле loadFactor, на основании которого, вычисляется предельное количество занятых корзин capacity * loadFactor. По умолчанию loadFactor = 0.75. По достижению предельного значения, число корзин увеличивается в 2 раза и для всех хранимых элементов вычисляется новое «местоположение» с учетом нового числа корзин.

к оглавлению

Объясните смысл параметров в конструкторе HashMap(int initialCapacity, float loadFactor).

  • initialCapacity - исходный размер HashMap, количество корзин в хэш-таблице в момент её создания.
  • loadFactor - коэффициент заполнения HashMap, при превышении которого происходит увеличение количества корзин и автоматическое перехэширование. Равен отношению числа уже хранимых элементов в таблице к её размеру.

к оглавлению

Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hashCode()?

Да, будет, но в этом случае HashMap вырождается в связный список и теряет свои преимущества.

Как перебрать все ключи Map?

Использовать метод keySet(), который возвращает множество Set<K> ключей.

к оглавлению

Как перебрать все значения Map?

Использовать метод values(), который возвращает коллекцию Collection<V> значений.

к оглавлению

Как перебрать все пары «ключ-значение» в Map?

Использовать метод entrySet(), который возвращает множество Set<Map.Entry<K, V> пар «ключ-значение».

к оглавлению

В чем отличия TreeSet и HashSet?

TreeSet обеспечивает упорядоченно хранение элементов в виде красно-черного дерева. Сложность выполнения основных операций не хуже O(lg(N)).

HashSet использует для хранения элементов такой же подход, что и HashMap, за тем отличием, что в HashSet в качестве ключа и значения выступает сам элемент, кроме того HashSet не поддерживает упорядоченное хранение элементов и обеспечивает временную сложность выполнения операций аналогично HashMap.

к оглавлению

Что будет, если добавлять элементы в TreeSet по возрастанию?

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

к оглавлению

Чем LinkedHashSet отличается от HashSet?

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

к оглавлению

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

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

Все основные операции выполняются за O(1) и обычно (но негарантированно) быстрей аналогов из HashSet, а пакетные операции (bulk operations), такие как containsAll() и retainAll() выполняются даже горазда быстрей.

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

к оглавлению

Какие существуют способы перебирать элементы списка?

  • Цикл с итератором
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    //iterator.next();
}
  • Цикл for
for (int i = 0; i < list.size(); i++) {
    //list.get(i);
}
  • Цикл while
int i = 0;
while (i < list.size()) {
	//list.get(i);
	i++;
}
  • «for-each»
for (String element : list) {
	//element;
}

к оглавлению

Каким образом можно получить синхронизированные объекты стандартных коллекций?

С помощью статических методов synchronizedMap() и synchronizedList() класса Collections. Данные методы возвращают синхронизированный декоратор переданной коллекции. При этом все равно в случае обхода по коллекции требуется ручная синхронизация.

  Map m = Collections.synchronizedMap(new HashMap());
  List l = Collections.synchronizedList(new ArrayList());

Начиная с Java 6 JCF был расширен специальными коллекциями, поддерживающими многопоточный доступ, такими как CopyOnWriteArrayList и ConcurrentHashMap.

к оглавлению

Как получить коллекцию только для чтения?

При помощи:

  • Collections.unmodifiableList(list);
  • Collections.unmodifiableSet(set);
  • Collections.unmodifiableMap(map).

Эти методы принимают коллекцию в качестве параметра, и возвращают коллекцию только для чтения с теми же элементами внутри.

к оглавлению

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

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);

    for (Integer integer : list) {
        list.remove(1);
    }
}

к оглавлению

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

public static void main(String[] args) {
    List<Integer> list = Collections.emptyList();
    list.add(0);
}

к оглавлению

Реализуйте симметрическую разность двух коллекций используя методы Collection (addAll(...), removeAll(...), retainAll(...)).

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

<T> Collection<T> symmetricDifference(Collection<T> a, Collection<T> b) {    
    // Объединяем коллекции.
    Collection<T> result = new ArrayList<>(a);
    result.addAll(b);
    
    // Получаем пересечение коллекций.
    Collection<T> intersection = new ArrayList<>(a);
    intersection.retainAll(b);
    
    // Удаляем элементы, расположенные в обоих коллекциях.
    result.removeAll(intersection);

    return result;
}

к оглавлению

Как, используя LinkedHashMap, сделать кэш c «invalidation policy»?

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

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

    public LRUCache(int initialCapacity) {
        super(initialCapacity, 0.85f, true);
    }

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

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

к оглавлению

Как одной строчкой скопировать элементы любой collection в массив?

Object[] array = collection.toArray();

к оглавлению

Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?

List<Integer> subList = list.subList(3, list.size() - 3);

к оглавлению

Как одной строчкой преобразовать HashSet в ArrayList?

ArrayList<Integer> list = new ArrayList<>(new HashSet<>());

к оглавлению

Как одной строчкой преобразовать ArrayList в HashSet?

HashSet<Integer> set = new HashSet<>(new ArrayList<>());

к оглавлению

Сделайте HashSet из ключей HashMap.

HashSet<Object> set = new HashSet<>(map.keySet());

к оглавлению

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

HashMap<K, V> map = new HashMap<>(set.size());
for (Map.Entry<K, V> entry : set) {
    map.put(entry.getKey(), entry.getValue());
}

к оглавлению

Источник

Вопросы для собеседования

  1. Что такое Java-коллекции?
  2. Какие интерфейсы являются основными интерфейсами коллекций в Java?
  3. Какие классы реализуют основные интерфейсы коллекций в Java?
  4. Чем отличаются ArrayList и LinkedList? В каких случаях лучше использовать одну или другую коллекцию?
  5. Какие методы есть у List?
  6. Какие методы есть у Set?
  7. Какие методы есть у Map?
  8. Что такое fail-fast поведение в коллекциях?
  9. Какие коллекции в Java упорядочены?
  10. Какие коллекции в Java разрешают дубликаты элементов?
  11. Какие коллекции в Java не разрешают дубликаты элементов?
  12. Что такое capacity у ArrayList и HashMap?
  13. Как работает hashCode() и equals() в Java?
  14. Какие алгоритмы используются для хранения элементов в HashSet и HashMap?
  15. Что такое TreeMap? Как он отличается от HashMap?
  16. Какие методы есть у PriorityQueue?
  17. Что такое Comparator? Как он используется?
  18. Каким образом можно отсортировать элементы в ArrayList?
  19. Какие интерфейсы необходимо реализовать, чтобы класс стал сравнимым?
  20. Что такое обобщенные типы в Java? Как они используются при работе с коллекциями?
  21. Какие методы есть у Collections?
  22. Какие методы есть у Arrays?
  23. Какой интерфейс нужно реализовать, чтобы создать свою собственную коллекцию?
  24. Как работает итератор в Java-коллекциях?
  25. Как добавлять элементы в конец списка?
  26. Что произойдет, если попытаться добавить null-элемент в LinkedList или HashSet?
  27. Что такое weak reference в Java и как он используется в коллекциях?
  28. Каким образом можно создать immutable коллекции в Java?
  29. Что такое ConcurrentModificationException и как ее избежать?
  30. Как использовать Stream API для работы с коллекциями?
  31. Какие коллекции в Java являются потокобезопасными?
  32. Чем отличается ConcurrentHashMap от HashMap?
  33. Какие коллекции лучше использовать, если нужно обеспечить уникальность элементов и быстрый доступ к ним?
  34. Можно ли использовать null-ключ в HashMap?
  35. Какой метод используется для удаления элемента из ArrayList?
  36. Каким образом можно создать копию коллекции в Java?
  37. Как работает метод subList() в List?
  38. Какие коллекции могут быть использованы для реализации стека или очереди?
  39. Как сравнить две коллекции на равенство?
  40. Как добавить все элементы одной коллекции в другую коллекцию?
  41. Как отсортировать список с помощью Comparator?
  42. Как получить первый (или последний) элемент из LinkedList?
  43. Что такое ListIterator? Как он используется?
  44. Как удалить дубликаты элементов из списка?
  45. Как производится сортировка в TreeMap?
  46. Как создать неизменяемую карту в Java?
  47. Какие коллекции в Java поддерживают обратный порядок элементов?
  48. Как удалить все элементы из коллекции?
  49. Как проверить, содержит ли коллекция определенный элемент?
  50. Как получить количество элементов в коллекции?
  51. Каким образом можно сравнить две карты (Map) на равенство?
  52. Что такое LinkedHashMap? Как он отличается от HashMap?
  53. Можно ли использовать TreeSet с объектами не реализующими интерфейс Comparable?
  54. Как создать TreeMap, который будет сортироваться по значению, а не по ключу?
  55. Что такое IdentityHashMap? В каких случаях он может быть полезен?
  56. Как удалить все элементы из HashSet?
  57. Как получить подмножество элементов из Set?
  58. Как перемешать элементы в ArrayList?
  59. Как сделать копию HashMap?
  60. Как проверить, является ли коллекция пустой?
  61. Каким образом можно превратить массив в список (List)?
  62. Как проверить, содержится ли определенное значение в Map?
  63. Как отсортировать HashMap?
  64. Как производится сортировка в PriorityQueue?
  65. Как узнать, есть ли определенный ключ в HashMap?
  66. Как изменить порядок элементов в ArrayList?
  67. Как сделать копию List?
  68. Каким образом можно удалить элементы из списка по условию?
  69. Как проверить, является ли ArrayList отсортированным?
  70. Каким образом можно добавить все элементы из одной карты в другую?
  71. Как установить максимальную емкость (capacity) для ArrayList?
  72. Как создать карту с заданными ключами и значениями?
  73. Как узнать количество элементов в HashMap?
  74. Что такое CopyOnWriteArrayList? В каких случаях он может быть полезен?
  75. Как проверить, является ли коллекция упорядоченной?
  76. Каким образом можно отсортировать массив объектов?
  77. Как добавить элемент в TreeSet?
  78. Как создать карту с заданным значением для всех ключей?
  79. Как удалить все элементы из TreeMap?
  80. Как получить все ключи или значения из карты?
  81. Как производится сортировка в TreeSet?
  82. Каким образом можно убедиться, что две коллекции содержат одинаковые элементы?
  83. Как создать массив из списка?
  84. Как производится сортировка в LinkedList?
  85. Что такое List.subList() и как его использовать?
  86. Как получить первый и последний элементы из PriorityQueue без удаления?
  87. Как сделать копию Set?
  88. Какой алгоритм используется для сортировки в Arrays.sort()?
  89. Как узнать, содержит ли коллекция все элементы другой коллекции?
  90. Каким образом можно создать множество (Set) из массива?
  91. Как проверить, что две карты содержат одинаковые значения?
  92. Как сделать копию TreeMap?
  93. Что такое EnumMap? В каких случаях его использование может быть полезно?
  94. Как добавить все элементы из массива в ArrayList?
  95. Каким образом можно отсортировать список с помощью Comparable?
  96. Как проверить, является ли TreeSet отсортированным?
  97. Как создать массив заданного размера?
  98. Как проверить, что коллекция не содержит дубликатов?
  99. Как сделать копию ArrayDeque?
  100. Каким образом можно преобразовать массив в строку?
  101. Как вывести все элементы коллекции на экран?
  102. Как добавить элементы в начало списка?
  103. Каким образом можно получить первый элемент из TreeSet?
  104. Что такое IdentityHashSet? В каких случаях его использование может быть полезно?
  105. Как узнать, является ли определенный ключ в TreeMap первым или последним?
  106. Как проверить, что две карты содержат одни и те же ключи?
  107. Как добавить элементы в конец списка?
  108. Как создать массив заданного типа?
  109. Как сделать копию HashMap без изменения оригинальной карты?
  110. Каким образом можно создать пустой список?
  111. Как вывести все ключи из карты на экран?
  112. Как проверить, что две коллекции содержат одни и те же элементы, но не обязательно в том же порядке?
  113. Как получить последний элемент из LinkedList?
  114. Как проверить, содержит ли множество (Set) все элементы другого множества?
  115. Как удалить все элементы из Stack?
  116. Как создать список заданного размера?
  117. Как узнать, что ключ уже присутствует в HashMap?
  118. Как сделать копию HashSet?
  119. Каким образом можно отсортировать массив строк?
  120. Что такое Collections.synchronizedList()? В каких случаях его использование может быть полезно?
  121. Как производится сортировка в EnumSet?
  122. Как проверить, содержат ли две коллекции одинаковые элементы в том же порядке?
  123. Как узнать, был ли определенный элемент добавлен в PriorityQueue?
  124. Каким образом можно отсортировать массив чисел?
  125. Что такое WeakHashMap? В каких случаях его использование может быть полезно?
  126. Как проверить, содержит ли Set определенный элемент?
  127. Как добавить все элементы из списка в множество (Set)?
  128. Как узнать, является ли TreeMap пустой?
  129. Как сделать копию Vector?
  130. Как получить первый элемент из LinkedList?
  131. Как проверить, что две карты содержат одни и те же значения, но не обязательно для одних и тех же ключей?
  132. Как удалить все элементы из PriorityQueue?
  133. Как создать список заданного типа?
  134. Что такое «коллекция»?
  135. Назовите основные интерфейсы JCF и их реализации.
  136. Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection, Iterable, Iterator, NavigableSet, NavigableMap.
  137. Почему Map — это не Collection, в то время как List и Set являются Collection?
  138. В чем разница между классами java.util.Collection и java.util.Collections?
  139. Что такое «fail-fast поведение»?
  140. Какая разница между fail-fast и fail-safe?
  141. Приведите примеры итераторов, реализующих поведение fail-safe
  142. Чем различаются Enumeration и Iterator.
  143. Как между собой связаны Iterable и Iterator?
  144. Как между собой связаны Iterable, Iterator и «for-each»?
  145. Сравните Iterator и ListIterator.
  146. Что произойдет при вызове Iterator.next() без предварительного вызова Iterator.hasNext()?
  147. Сколько элементов будет пропущено, если Iterator.next() будет вызван после 10-ти вызовов Iterator.hasNext()?
  148. Как поведёт себя коллекция, если вызвать iterator.remove()?
  149. Как поведёт себя уже инстанциированный итератор для collection, если вызвать collection.remove()?
  150. Как избежать ConcurrentModificationException во время перебора коллекции?
  151. Какая коллекция реализует дисциплину обслуживания FIFO?
  152. Какая коллекция реализует дисциплину обслуживания FILO?
  153. Чем отличается ArrayList от Vector?
  154. Зачем добавили ArrayList, если уже был Vector?
  155. Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй?
  156. Что работает быстрее ArrayList или LinkedList?
  157. Какое худшее время работы метода contains() для элемента, который есть в LinkedList?
  158. Какое худшее время работы метода contains() для элемента, который есть в ArrayList?
  159. Какое худшее время работы метода add() для LinkedList?
  160. Какое худшее время работы метода add() для ArrayList?
  161. Необходимо добавить 1 млн. элементов, какую структуру вы используете?
  162. Как происходит удаление элементов из ArrayList? Как меняется в этом случае размер ArrayList?
  163. Предложите эффективный алгоритм удаления нескольких рядом стоящих элементов из середины списка, реализуемого ArrayList.
  164. Сколько необходимо дополнительной памяти при вызове ArrayList.add()?
  165. Сколько выделяется дополнительно памяти при вызове LinkedList.add()?
  166. Оцените количество памяти на хранение одного примитива типа byte в LinkedList?
  167. Оцените количество памяти на хранение одного примитива типа byte в ArrayList?
  168. Для ArrayList или для LinkedList операция добавления элемента в середину (list.add(list.size()/2, newElement)) медленнее?
  169. В реализации класса ArrayList есть следующие поля: Object[] elementData, int size. Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?
  170. Сравните интерфейсы Queue и Deque.
  171. Кто кого расширяет: Queue расширяет Deque, или Deque расширяет Queue?
  172. Почему LinkedList реализует и List, и Deque?
  173. LinkedList — это односвязный, двусвязный или четырехсвязный список?
  174. Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)?
  175. Что позволяет сделать PriorityQueue?
  176. Stack считается «устаревшим». Чем его рекомендуют заменять? Почему?
  177. Зачем нужен HashMap, если есть Hashtable?
  178. В чем разница между HashMap и IdentityHashMap? Для чего нужна IdentityHashMap?
  179. В чем разница между HashMap и WeakHashMap? Для чего используется WeakHashMap?
  180. В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences?
  181. В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences?
  182. LinkedHashMap - что в нем от LinkedList, а что от HashMap?
  183. В чем проявляется «сортированность» SortedMap, кроме того, что toString() выводит все элементы по порядку?
  184. Как устроен HashMap?
  185. Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресации и на основе метода цепочек. Как реализована HashMap? Почему, по вашему мнению, была выбрана именно эта реализация? В чем плюсы и минусы каждого подхода?
  186. Как работает HashMap при попытке сохранить в него два элемента по ключам с одинаковым hashCode(), но для которых equals() == false?
  187. Какое начальное количество корзин в HashMap?
  188. Какова оценка временной сложности операций над элементами из HashMap? Гарантирует ли HashMap указанную сложность выборки элемента?
  189. Возможна ли ситуация, когда HashMap выродится в список даже с ключами имеющими разные hashCode()?
  190. В каком случае может быть потерян элемент в HashMap?
  191. Почему нельзя использовать byte[] в качестве ключа в HashMap?
  192. Какова роль equals() и hashCode() в HashMap?
  193. Каково максимальное число значений hashCode()?
  194. Какое худшее время работы метода get(key) для ключа, которого нет в HashMap?
  195. Какое худшее время работы метода get(key) для ключа, который есть в HashMap?
  196. Сколько переходов происходит в момент вызова HashMap.get(key) по ключу, который есть в таблице?
  197. Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap?
  198. Как и когда происходит увеличение количества корзин в HashMap?
  199. Объясните смысл параметров в конструкторе HashMap(int initialCapacity, float loadFactor).
  200. Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hashCode()?
  201. Как перебрать все ключи Map?
  202. Как перебрать все значения Map?
  203. Как перебрать все пары «ключ-значение» в Map?
  204. В чем отличия TreeSet и HashSet?
  205. Что будет, если добавлять элементы в TreeSet по возрастанию?
  206. Чем LinkedHashSet отличается от HashSet?
  207. Для Enum есть специальный класс java.util.EnumSet. Зачем? Чем авторов не устраивал HashSet или TreeSet?
  208. Какие существуют способы перебирать элементы списка?
  209. Каким образом можно получить синхронизированные объекты стандартных коллекций?
  210. Как получить коллекцию только для чтения?
  211. Напишите однопоточную программу, которая заставляет коллекцию выбросить ConcurrentModificationException.
  212. Приведите пример, когда какая-либо коллекция выбрасывает UnsupportedOperationException.
  213. Реализуйте симметрическую разность двух коллекций используя методы Collection (addAll(...), removeAll(...), retainAll(...)).
  214. Как, используя LinkedHashMap, сделать кэш c «invalidation policy»?
  215. Как одной строчкой скопировать элементы любой collection в массив?
  216. Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?
  217. Как одной строчкой преобразовать HashSet в ArrayList?
  218. Как одной строчкой преобразовать ArrayList в HashSet?
  219. Сделайте HashSet из ключей HashMap.
  220. Сделайте HashMap из HashSet<Map.Entry<K, V>>.