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. Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?¶

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

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

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

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

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

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

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

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

O(N). Здесь стоит заметить, что добавление элемента в конец списка с помощью методом add(value), addLast(value) и добавление в начало списка с помощью addFirst(value) выполняется за время O(1). O(N) - будет при добавление элемента в отсортированный список, а также при добавлении элемента с помощью метода add(index, value)

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

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

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

Если в массиве достаточно места для размещения нового элемента, то дополнительное место в памяти не выделяется. Иначе происходит создание нового массива с размером:

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

Другими словами, создается новый массив, размер которого вычисляется как умножение старого размера на 1.5 (это верно для JDK 1.7, в более ранних версиях вычисления отличаются).

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

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

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

Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные. Для x32 систем каждая ссылка занимает 32 бита (4 байта). Сам объект типа Node занимает приблизительно 8 байт. Размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типа byte занимает 1 байт памяти, но в списке примитивы упаковываются, соответственно получаем еще 8 байт. Таким образом, в x32 JVM около 32 байтоввыделяется для хранения одного значения типа byte в LinkedList. Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт). Вычисления аналогичны.

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

ArrayList основан на массиве. Каждый элемент массива хранит примитивный тип данных - byte, размер которого 1 байт.

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

Для ArrayList:

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

Для LinkedList:

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

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

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

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

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

List<Integer> sourceList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
List<Integer> subList = sourceList.subList(3, sourceList.size() - 3);

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

Да, могут. Метод hashCode() не гарантирует уникальность возвращаемого значения.

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

Да, могут. Для этого в классе этих объектов должен быть переопределен метод equals(). Если используется метод Object.equals(), то для двух ссылок x и y метод вернет true тогда и только тогда, когда обе ссылки указывают на один и тот же объект (т.е. x y возвращает true).

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

Нет, не может. Метод equals() должен гарантировать свойство рефлексивности: для любых ненулевых ссылок xметод x.equals(x) должен возвращать true.

Есть класс 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?¶

HashSet использует HashMap для хранения элементов (в качестве ключа используется сам объект). При добавлении элемента в HashMap вычисляется хэшкод и позиция в массиве, куда будет вставлен новый элемент. У всех экземпляров класса Point одинаковый хэшкод, что приводит в вырождению хэш-таблицы в список. При возникновении коллизии осуществляется проверка на наличие уже такого элемента в текущем списке:

e.hash == hash && ((k = e.key) == || key.equals(k))

Если элемент найден, то его значение перезаписывается. В нашем случае для разных объектов метод equals() будет возвращать false. Соответственно новый элемент будет добавлен в HashSet. Извлечение элемента также будет осуществляться успешно. Но производительность такого кода будет низкой и преимущества хэштаблиц использоваться не будут.

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

Метод equals() должен обеспечивать:

• симметричность (для любых ненулевых ссылок x и y метод x.equals(y) должен возвращать true тогда и только тогда, когда y.equals(x) возвращает true);
• рефлексивность (для любых ненулевых ссылок x метод x.equals(x) должен возвращать true.);
• транзитивность (для любых ненулевых ссылок x, y и z, если x.equals(y) возвращает true и y.equals(z)возвращает true, тогда и x.equals(z) должен возвращать true).

Также есть ещё два свойства: постоянство и неравенство null.

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

Строго говоря нельзя, поскольку метод hashCode() не гарантирует уникальность значения для каждого объекта. Однако для сравнения экземпляров класса Object такой код допустим, т.к. метод hashCode() в классе Object возвращает уникальные значения для разных объектов (вычисления основаны на использовании адреса объекта в памяти).

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

Оператор instanceof сравнивает объект и указанный тип. Его можно использовать для проверки является ли данный объект экземпляром некоторого класса, либо экземпляром его дочернего класса, либо экземпляром класса, который реализует указанный интерфейс. getClass() = ... проверяет два типа на идентичность. Для корректной реализации контракта метода equals() необходимо использовать точное сравнение с помощью getClass().

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

Реализовать можно, но данный метод не переопределяет метод equals() класса Object, а перегружает его.

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

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

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

Класс Hashtable был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Hashtable синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс HashMap, методы которого не синхронизированы.
Помимо этого класс HashMap обладает некоторыми другими отличиями: например, позволяет хранить один null ключ и множество null значений.

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

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

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

Основные недостатки структур с методом открытой адресации:

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

Основное преимущество хэш-таблицы с открытой адресацией - это отсутствие затрат на создание и хранение объектов списка. Также проще организовать сериализацию/десериализацию объекта.

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

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

Рассмотрим первый случай, когда ключ равен null: выполняем метод getForNullKey().

В цикле foreach проходимся по списку значений для ключа и возвращаем нужное значение. Таким образом, получаем 1 переход. Второй случай: ключ не равен null. Выполняем метод getEntry(key).

Вычисляется хэш-код ключа (метод hash(key)), затем определяется индекс ячейки массива, в которой будем искать значение (метод indexFor(hash, table.length)). После того, как нашли нужную пару "ключ-значение" возвращаем значение (метод entry.getValue()). Таким образом, получаем 4 перехода.

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

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

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

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

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

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

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

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

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

O(N). Аналогичные рассуждения, что и для предыдущего вопроса.

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

int initialCapacity - исходный размер HashMap (количество корзин в хэштаблице в момент её создания), по умолчанию имеет значение 16.

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

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