JAVA COLLECTIONS FRAMEWORK¶

Вопросы¶

1. Что такое Коллекция?
2. Назовите основные интерфейсы коллекций и их имплементации.
3. Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй?
4. Чем отличается HashMap от Hashtable?
5. Чем отличается ArrayList от Vector?
6. Как сравниваются елементы коллекций?
7. Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection,Iterable, Iterator, NavigableSet, NavigableMap.
8. Почему Map - это не Collection, в то время как List и Set являются Collection?
9. Дайте определение понятию "iterator".
10. Что вы знаете об интерфейсе Iterable?
11. Как одной строчкой преобразовать HashSet в ArrayList?
12. Как одной строчкой преобразовать ArrayList в HashSet?
13. Как перебрать все ключи Map учитывая, что Map - это не Iterable?
14. Как перебрать все значения Map учитывая, что Map - это не Iterable?
15. Как перебрать все пары ключ-значение в Map учитывая, что Map - это не Iterable?
16. В чем проявляется "сортированность" SortedMap, кроме того, что toString() выводит все по порядку?
17. Как одним вызовом копировать элементы из любой Collection в массив?
18. Реализуйте симметрическую разность двух коллекций используя методы Collection(addAll(), removeAll(), retainAll()).
19. Сравните Enumeration и Iterator.
20. Как между собой связаны Iterable и Iterator?
21. Как между собой связаны Iterable, Iterator и "for-each " введенный в Java 5?
22. Сравните Iterator и ListIterator.
23. Что произойдет, если я вызову Iterator.next() не "спросив" Iterator.hasNext()?
24. Что произойдет, если я вызову Iterator.next() перед этим 10 раз вызвав Iterator.hasNext()? Я пропущу 9 элементов?
25. Если у меня есть коллекция и порожденный итератор, изменится ли коллекция, если я вызову iterator.remove()?
26. Если у меня есть коллекция и порожденный итератор, изменится ли итератор, если я вызову collection.remove(..)?
27. Зачем добавили ArrayList, если уже был Vector?
28. В реализации класса ArrayList есть следующие поля: Object[] elementData, int size.
29. Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?
30. LinkedList - это односвязный, двусвязный или четырехсвязный список?
31. Какое худшее время работы метода contain() для элемента, который есть в LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
32. Какое худшее время работы метода contain() для элемента, который есть в ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
33. Какое худшее время работы метода add() для LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
34. Какое худшее время работы метода add() для ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
35. Сколько выделяется элементов в памяти при вызове ArrayList.add()?
36. Сколько выделяется элементов в памяти при вызове LinkedList.add()?
37. Оцените количество памяти на хранение одного примитива типа byte в LinkedList?
38. Оцените количество памяти на хранение одного примитива типа byte в ArrayList?
39. Я добавляю элемент в середину List-а: list.add(list.size()/2, newElem). Для кого эта операция медленнее - для ArrayList или для LinkedList?
40. Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)?
41. Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?
42. Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.hashCode() ref1.hashCode()?
43. Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.equals(ref1) true?
44. Могут ли у разных ссылок на один объект в памяти (ref0 ref1) быть ref0.equals(ref1) false?
45. Есть класс Point{int x, y;}. Почему хэш-код в виде 31 * x + y предпочтительнее чем x + y?
46. Если у класса Point{int x, y;} "правильно " реализовать метод equals (return ref0.x ref1.x && ref0.y ref1.y), но сделать хэш-код в виде int hashCode() {return x;}, то будут ли корректно такие точки помещаться и извлекаться из HashSet?
47. equals() порождает отношение эквивалентности. Какими из свойств обладает такое отношение: коммутативность, симметричность, рефлексивность, дистрибутивность, ассоциативность, транзитивность?
48. Можно ли так реализовать equals(Object that) {return this.hashCode() that.hashCode()}?
49. В equals требуется проверять, что аргумент (equals(Object that)) такого же типа как и сам объект. В чем разница между this.getClass() that.getClass() и that instanceof MyClass?
50. Можно ли реализовать метод equals класса MyClass вот так: class MyClass {public boolean equals(MyClass that) {return this that;}}?
51. Будет ли работать HashMap, если все ключи будут возвращать int hashCode() {return 42;}?
52. Зачем добавили HashMap, если уже был Hashtable?
53. Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресацией и на основе метода цепочек. Как реализована HashMap? Почему так сделали (по вашему мнению)? В чем минусы и плюсы каждого подхода?
54. Сколько переходов по ссылкам происходит, когда вы делаете HashMap.get(key) по ключу, который есть в таблице?
55. Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap?
56. Как работает HashMap при попытке сохранить в нее два элемента по ключам с
57. одинаковым hashCode, но для которых equals false?
58. HashMap может выродиться в список даже для ключей с разным hashCode. Как это возможно?
59. Какое худшее время работы метода get(key) для ключа, которого нет в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
60. Какое худшее время работы метода get(key) для ключа, который есть в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
61. Объясните смысл параметров в конструкторе HashMap(int initialCapacity, float loadFactor).
62. В чем разница между HashMap и IdentityHashMap? Для чего нужна IdentityHashMap? Как может быть полезна для реализации сериализации или клонирования?
63. В чем разница между HashMap и WeakHashMap? Для чего нужна WeakHashMap?
64. В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences?
65. В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences?
66. Сделайте HashSet из HashMap (используйте только множество ключей, но не множество значений).
67. Сделайте HashMap из HashSet (HashSet<Map.Entry<K, V>>)
68. Сравните интерфейсы java.util.Queue и java.util.Deque.
69. Кто кого расширяет: Queue расширяет Deque, или Deque расширяет Queue?
70. Почему LinkedList реализует и List, и Deque?
71. В чем разница между классами java.util.Arrays и java.lang.reflect.Array?
72. В чем разница между классами java.util.Collection и java.util.Collections?
73. Напишите НЕмногопоточную программу, которая заставляет коллекцию выбросить ConcurrentModificationException.
74. Что такое "fail-fast поведение"?
75. Для множеств еnum-ов есть специальный класс java.util.EnumSet? Зачем? Чем авторов не устраивал HashSet или TreeSet?
76. java.util.Stack - считается "устаревшим". Чем его рекомендуют заменять? Почему?
77. Какая коллекция реализует дисциплину обслуживания FIFO?
78. Какая коллекция реализует дисциплину обслуживания FILO?
79. Приведите пример, когда какая-либо коллекция выбрасывает UnsupportedOperationException.
80. Почему нельзя написать "ArrayList<List> numbers = new ArrayList<ArrayList>();" но можно "List<ArrayList> numbers = new ArrayList<ArrayList>();"?
81. LinkedHashMap - что это еще за "зверь"? Что в нем от LinkedList, а что от HashMap?
82. LinkedHashSet - что это еще за "зверь"? Что в нем от LinkedList, а что от HashSet?
83. Говорят, на LinkedHashMap легко сделать простенький кэш c "invalidation policy", знаете как?
84. Что позволяет сделать PriorityQueue?
85. В чем заключаются отличия java.util.Comparator от java.lang.Comparable?

Ответы¶

Что такое Коллекция?¶

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

• добавление нового элемента в коллекцию;
• удаление элемента из коллекции;
• изменение элемента в коллекции.

Назовите основные интерфейсы коллекций и их имплементации.¶

Сollection расширяет три интерфейса: List , Set , Queue .

List - хранит упорядоченные елементы(могут быть одинаковые); Имеет такие реализации как LinkedList, ArrayList и Vector.

• Vector синхронизирован, и по этому в одном потоке, он работает медленней остальных реализаций.
• ArrayList - его преимущество в навигации по коллекции.
• LinkedList - его преимущество в во вставке и удалении элементов в коллекции.

Set - коллекции, которые не содержат повторяющихся элементов. Основные реализации: HashSet, TreeSet, LinkedHashSet

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

Queue - интерфейс для реализации очереди в java. Основные реализации: LinkedList, PriorityQueue. Очереди работают по принципу FIFO – First in First out.

Map - интерфейс для реализации так называемой карты, где элементы хранятся с их ключами. Основные реализации: HashTable, HashMap, TreeMap, LinkedHashMap

• HashTable - синхронизированна, объявлена уставревшей.
• HashMap - порядок елементов рассчитывается по хэш ключу;
• TreeMap - элементы хранятся в отсортированном порядке
• LinkedHashMap - элементы хранятся в порядке вставки

Ключи в Мар не могут быть одинаковыми!

Синхронизировать не синхронизированные коллекции и карты можно посредством класса Collections.synchronizedMap(MyMap)\synchronizedList(MyList).

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

Отличие заключается в способе хранения данных. ArrayList хранит в виде массива, а LinkedList - в виде списка (двунаправленного).
В ArrayList быстрее происходит сортировка, т.к. для ее выполнения данные списка копируются в массив (а копировать из массива ArrayList в массив для сортировки быстрее). При большом числе операций добавления и удаления LinkedList должен быть более удачным выбором, т.к. при этих операциях не приходится перемещать части массива.
Если при добавлении в ArrayList превышается его объем, размер массива увеличивается, новая емкость рассчитывается по формуле (oldCapacity * 3) / 2 + 1, поэтому лучше указывать размер при создании или, если он не известен, использовать LinkedList (но это может быть существенно при слишком уж больших объемах данных).

Чем отличается HashMap от Hashtable?¶

Класс HashMap по функционалу очень похож на Hashtable. Главное отличие в том, что методы класса Hashtable синхронизированы, а HashMap - нет. Кроме этого класс HashMap в отличии от Hashtable разрешает использование null в качестве ключей и значений.
Наличие синхронизации в Hashtable уменьшает производительность кода, использующего данный класс. Поэтому классы JCF (Java Collections Framework, появившийся в Java 2), в том числе и HashMap, несинхронизированы. Если синхронизация все же нужна, можно использовать методы класса Collections: Collections.synchronizedMap(map), Collections.synchronizedList(list) или Collections.synchronizedSet(set).
Данные методы возвращают синхронизированный декоратор переданной коллекции. При этом все равно в случае итерирования по коллекции требуется ручная синхронизация. Начиная с Java 6 JCF был расширен специальными коллекциями, поддерживающими многопоточный доступ, такими как CopyOnWriteArrayList и ConcurrentHashMap.

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

Методы класса Vector синхронизированы, в то время как ArrayList - нет.

Как сравниваются элементы коллекций?¶

Для сравнения элементов коллекций используется метод equals() и hashcode();Эти методы унаследованы от класса Object.

• Если наш пользовательский класс переопределяет equals(), то он должен и переопределить hashcode().
• Если два объекта эквивалентны, то и хэш коды этих объектов тоже должны быть равны.
• Если поле не используется в equals(), то оно и не должно использоваться в hashcode().

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

Почему Map - это не Collection, в то время как List и Set являются Collection?¶

Коллекция (List и Set) представляет собой совокупность некоторых элементов (обычно экземпляров одного класса). Map это совокупность пар "ключ""значение".
Соответственно некоторые методы интерфейса Collection нельзя использовать в Map. Например, метод remove(Object o) в интерфейсе Collection предназначен для удаления элемента, тогда как такой же метод remove(Object key) в интерфейсе Map - удаляет элемент по заданному ключу.

Дайте определение понятию "iterator".¶

Итератор - объект, позволяющий перебирать элементы коллекции. Например foreach реализован с использованием итератора. Одним из ключевых методов интерфейса Collection является метод Iterator<E> iterator(). Он возвращает итератор - то есть объект, реализующий интерфейс Iterator. Интерфейс Iterator имеет следующее определение:

public interface Iterator <E> {
    E next;
    boolean hasNext();
    void remove();
}

Что вы знаете об интерфейсе Iterable?¶

Все коллекции из java.util реализуют интерфейс Collection, который, в свою очередь, расширяет интерфейс Iterable. В интерфейсе Iterable описан только один метод: Iterator iterator();
Он возвращает Iterator, т.е. объект, который поочерёдно возвращает все элементы коллекции.

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

public static void main(String[] args) {
    Set<String> set = new HashSet<>();
    set.add("A");
    set.add("B");
    List<String> list = new ArrayList<>(set);
}

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

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("A");
    list.add("B");
    Set<String> set = new HashSet<>(list);
}

Как перебрать все ключи Map учитывая, что Map - это не Iterable?¶

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

Как перебрать все значения Map учитывая, что Map - это не Iterable?¶

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

Как перебрать все пары ключ-значение в Map учитывая, что Map - это не Iterable?¶

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

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

Естественное упорядочивание (natural ordering) отражается при итерации по коллекции ключей или значений хэш-таблицы (возвращаемых методами keySet(), values() и entrySet()).

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

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("A");
    list.add("B");
    String[] strArray = list.toArray(new String[list.size()]);
    // или
    Object[] objArray = list.toArray();
}

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

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

Сравните Enumeration и Iterator.¶

Оба интерфейса предназначены для обхода коллекций. Интерфейс Iterator был введен несколько позднее в Java Collections Framework и его использование предпочтительнее. Основные различия Iterator по сравнению с Enumeration:

• наличие метода remove() для удаления элемента из коллекции при обходе;
• исправлены имена методов для повышения читаемости кода.

Как между собой связаны Iterable и Iterator?¶

Интерфейс Iterable имеет только один метод - iterator(), который возвращает итератор коллекции для её обхода.

Как между собой связаны Iterable, Iterator и "for-each " введенный в Java 5?¶

Экземпляры классов, реализующих интерфейс Iterable, могут использоваться в конструкции foreach

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

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

Что произойдет, если я вызову Iterator.next() не "спросив" Iterator.hasNext()?¶

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

Что произойдет, если я вызову Iterator.next() перед этим 10 раз вызвав Iterator.hasNext()? Я пропущу 9 элементов?¶

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

Если у меня есть коллекция и порожденный итератор, изменится ли коллекция, если я вызову iterator.remove()?¶

Вызов метода iterator.remove() возможен только после вызова метода iterator.next() хотя бы раз, иначе появится исключение IllegalStateException(). Если iterator.next() был вызван прежде, то iterator.remove() удалит элемент, на который указывает итератор.

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

Итератор не изменится, но при следующем вызове его методов возникнет исключение ConcurrentModiÙcationException.

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

Обе структуры данных предназначены для хранения коллекции элементов, в том числе дубликатов и null. Они основаны на использовании массивов, динамически расширяющихся при необходимости. Класс Vector был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Vector синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс ArrayList, методы которого не синхронизированы.

В реализации класса ArrayList есть следующие поля: Object[] elementData, int size.¶

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

Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?¶

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

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

Какое худшее время работы метода contain() для элемента, который есть в LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?¶

Какое худшее время работы метода contain() для элемента, который есть в ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?¶

Какое худшее время работы метода add() для LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?¶

Какое худшее время работы метода add() для ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?¶

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

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

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

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

Я добавляю элемент в середину List-а: list.add(list.size()/2, newElem). Для кого эта операция медленнее - для ArrayList или для LinkedList?¶

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

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

Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.hashCode() ref1.hashCode()?¶

Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.equals(ref1) true?¶

Могут ли у разных ссылок на один объект в памяти (ref0 ref1) быть ref0.equals(ref1) false?¶

Есть класс Point{int x, y;}. Почему хэш-код в виде 31 * x + y предпочтительнее чем x + y?¶

Если у класса Point{int x, y;} "правильно " реализовать метод equals (return ref0.x ref1.x && ref0.y ref1.y), но сделать хэш-код в виде int hashCode() {return x;}, то будут ли корректно такие точки помещаться и извлекаться из HashSet?¶

equals() порождает отношение эквивалентности. Какими из свойств обладает такое отношение: коммутативность, симметричность, рефлексивность, дистрибутивность, ассоциативность, транзитивность?¶

Можно ли так реализовать equals(Object that) {return this.hashCode() that.hashCode()}?¶

В equals требуется проверять, что аргумент (equals(Object that)) такого же типа как и сам объект. В чем разница между this.getClass() that.getClass() и that instanceof MyClass?¶

Можно ли реализовать метод equals класса MyClass вот так: class MyClass {public boolean equals(MyClass that) {return this that;}}?¶

Будет ли работать HashMap, если все ключи будут возвращать int hashCode() {return 42;}?¶

Зачем добавили HashMap, если уже был Hashtable?¶

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

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

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

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

HashMap может выродиться в список даже для ключей с разным hashCode. Как это возможно?¶

Какое худшее время работы метода get(key) для ключа, которого нет в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?¶

Какое худшее время работы метода get(key) для ключа, который есть в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?¶

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

В чем разница между 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.¶

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

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

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

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

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

Что такое "fail-fast поведение"?¶

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

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

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

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

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

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

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

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

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

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

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