Проект

Общее

Профиль

JAVA COLLECTIONS FRAMEWORK » История » Версия 23

Александр Александров, 28.04.2019 22:53

1 1 Александр Александров
h1. JAVA COLLECTIONS FRAMEWORK
2
3
h2. Вопросы
4
5
# Что такое Коллекция?
6
# Назовите основные интерфейсы коллекций и их имплементации.
7
# Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй?
8
# Чем отличается HashMap от Hashtable?
9
# Чем отличается ArrayList от Vector?
10
# Как сравниваются елементы коллекций?
11
# Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection,Iterable, Iterator, NavigableSet, NavigableMap.
12
# Почему Map - это не Collection, в то время как List и Set являются Collection?
13
# Дайте определение понятию "iterator".
14
# Что вы знаете об интерфейсе Iterable?
15
# Как одной строчкой преобразовать HashSet в ArrayList?
16
# Как одной строчкой преобразовать ArrayList в HashSet?
17
# Как перебрать все ключи Map учитывая, что Map - это не Iterable?
18
# Как перебрать все значения Map учитывая, что Map - это не Iterable?
19
# Как перебрать все пары ключ-значение в Map учитывая, что Map - это не Iterable?
20
# В чем проявляется "сортированность" SortedMap, кроме того, что toString() выводит все по порядку?
21
# Как одним вызовом копировать элементы из любой Collection в массив?
22 10 Александр Александров
# Реализуйте симметричную разность двух коллекций используя методы Collection(addAll(), removeAll(), retainAll()).
23 1 Александр Александров
# Сравните Enumeration и Iterator.
24
# Как между собой связаны Iterable и Iterator?
25
# Как между собой связаны Iterable, Iterator и "for-each " введенный в Java 5?
26
# Сравните Iterator и ListIterator.
27
# Что произойдет, если я вызову Iterator.next() не "спросив" Iterator.hasNext()?
28
# Что произойдет, если я вызову Iterator.next() перед этим 10 раз вызвав Iterator.hasNext()? Я пропущу 9 элементов?
29
# Если у меня есть коллекция и порожденный итератор, изменится ли коллекция, если я вызову iterator.remove()?
30
# Если у меня есть коллекция и порожденный итератор, изменится ли итератор, если я вызову collection.remove(..)?
31
# Зачем добавили ArrayList, если уже был Vector?
32
# В реализации класса ArrayList есть следующие поля: Object[] elementData, int size.
33
# Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?
34
# LinkedList - это односвязный, двусвязный или четырехсвязный список?
35
# Какое худшее время работы метода contain() для элемента, который есть в LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
36
# Какое худшее время работы метода contain() для элемента, который есть в ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
37
# Какое худшее время работы метода add() для LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
38
# Какое худшее время работы метода add() для ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
39
# Сколько выделяется элементов в памяти при вызове ArrayList.add()?
40
# Сколько выделяется элементов в памяти при вызове LinkedList.add()?
41
# Оцените количество памяти на хранение одного примитива типа byte в LinkedList?
42
# Оцените количество памяти на хранение одного примитива типа byte в ArrayList?
43
# Я добавляю элемент в середину List-а: list.add(list.size()/2, newElem). Для кого эта операция медленнее - для ArrayList или для LinkedList?
44
# Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)?
45
# Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?
46
# Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.hashCode() == ref1.hashCode()?
47
# Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.equals(ref1) == true?
48
# Могут ли у разных ссылок на один объект в памяти (ref0 == ref1) быть ref0.equals(ref1) == false?
49
# Есть класс Point{int x, y;}. Почему хэш-код в виде 31 * x + y предпочтительнее чем x + y?
50
# Если у класса Point{int x, y;} "правильно " реализовать метод equals (return ref0.x == ref1.x && ref0.y == ref1.y), но сделать хэш-код в виде int hashCode() {return x;}, то будут ли корректно такие точки помещаться и извлекаться из HashSet?
51
# equals() порождает отношение эквивалентности. Какими из свойств обладает такое отношение: коммутативность, симметричность, рефлексивность, дистрибутивность, ассоциативность, транзитивность?
52
# Можно ли так реализовать equals(Object that) {return this.hashCode() == that.hashCode()}?
53
# В equals требуется проверять, что аргумент (equals(Object that)) такого же типа как и сам объект. В чем разница между this.getClass() == that.getClass() и that instanceof MyClass?
54
# Можно ли реализовать метод equals класса MyClass вот так: class MyClass {public boolean equals(MyClass that) {return this == that;}}?
55
# Будет ли работать HashMap, если все ключи будут возвращать int hashCode() {return 42;}?
56
# Зачем добавили HashMap, если уже был Hashtable?
57
# Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресацией и на основе метода цепочек. Как реализована HashMap? Почему так сделали (по вашему мнению)? В чем минусы и плюсы каждого подхода?
58
# Сколько переходов по ссылкам происходит, когда вы делаете HashMap.get(key) по ключу, который есть в таблице?
59
# Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap?
60
# Как работает HashMap при попытке сохранить в нее два элемента по ключам с
61
# одинаковым hashCode, но для которых equals == false?
62
# HashMap может выродиться в список даже для ключей с разным hashCode. Как это возможно?
63
# Какое худшее время работы метода get(key) для ключа, которого нет в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
64
# Какое худшее время работы метода get(key) для ключа, который есть в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
65
# Объясните смысл параметров в конструкторе HashMap(int initialCapacity, float loadFactor).
66
# В чем разница между HashMap и IdentityHashMap? Для чего нужна IdentityHashMap? Как может быть полезна для реализации сериализации или клонирования?
67
# В чем разница между HashMap и WeakHashMap? Для чего нужна WeakHashMap?
68
# В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences?
69
# В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences?
70
# Сделайте HashSet из HashMap (используйте только множество ключей, но не множество значений).
71
# Сделайте HashMap из HashSet (HashSet<Map.Entry<K, V>>)
72
# Сравните интерфейсы java.util.Queue и java.util.Deque.
73
# Кто кого расширяет: Queue расширяет Deque, или Deque расширяет Queue?
74
# Почему LinkedList реализует и List, и Deque?
75
# В чем разница между классами java.util.Arrays и java.lang.reflect.Array?
76
# В чем разница между классами java.util.Collection и java.util.Collections?
77
# Напишите НЕмногопоточную программу, которая заставляет коллекцию выбросить ConcurrentModificationException.
78
# Что такое "fail-fast поведение"?
79
# Для множеств еnum-ов есть специальный класс java.util.EnumSet? Зачем? Чем авторов не устраивал HashSet или TreeSet?
80
# java.util.Stack - считается "устаревшим". Чем его рекомендуют заменять? Почему?
81
# Какая коллекция реализует дисциплину обслуживания FIFO?
82
# Какая коллекция реализует дисциплину обслуживания FILO?
83
# Приведите пример, когда какая-либо коллекция выбрасывает UnsupportedOperationException.
84
# Почему нельзя написать "ArrayList<List> numbers = new ArrayList<ArrayList>();" но можно "List<ArrayList> numbers = new ArrayList<ArrayList>();"?
85
# LinkedHashMap - что это еще за "зверь"? Что в нем от LinkedList, а что от HashMap?
86
# LinkedHashSet - что это еще за "зверь"? Что в нем от LinkedList, а что от HashSet?
87
# Говорят, на LinkedHashMap легко сделать простенький кэш c "invalidation policy", знаете как?
88
# Что позволяет сделать PriorityQueue?
89
# В чем заключаются отличия java.util.Comparator от java.lang.Comparable?
90
91
h2. Ответы
92
93
h3. Что такое Коллекция?
94
95 2 Александр Александров
Коллекции - это хранилища или контейнеры, поддерживающие различные способы накопления и упорядочения объектов с целью обеспечения возможностей эффективного доступа к ним. Они представляют собой реализацию абстрактных структур данных, поддерживающих три основные операции:
96 1 Александр Александров
97 2 Александр Александров
* добавление нового элемента в коллекцию;
98
* удаление элемента из коллекции;
99
* изменение элемента в коллекции.
100
101 1 Александр Александров
h3. Назовите основные интерфейсы коллекций и их имплементации.
102
103 13 Александр Александров
{{dmsf_image(199)}}
104 6 Александр Александров
105 5 Александр Александров
{{dmsf_image(373, size=800)}}
106
{{dmsf_image(372, size=800)}}
107 1 Александр Александров
108 2 Александр Александров
Сollection расширяет три интерфейса: *List* , *Set* , *Queue* .
109
110 7 Александр Александров
*List* - хранит упорядоченные элементы(могут быть одинаковые); Имеет такие реализации как _LinkedList_, _ArrayList_ и _Vector_.
111 2 Александр Александров
112 7 Александр Александров
* Vector синхронизирован и по этому в одном потоке он работает медленней остальных реализаций.
113 2 Александр Александров
* ArrayList - его преимущество в навигации по коллекции.
114
* LinkedList - его преимущество в во вставке и удалении элементов в коллекции.
115
116
*Set* - коллекции, которые не содержат повторяющихся элементов. Основные реализации: _HashSet_, _TreeSet_, _LinkedHashSet_
117
118
* TreeSet - упорядочивает элементы по их значениям;
119
* HashSet - упорядочивает элементы по их хэш ключах, хотя на первый взляд может показаться что элементы хранятся в случайном порядке.
120
* LinkedHashSet - хранит элементы в порядке их добавления.
121
122
*Queue* - интерфейс для реализации очереди в java. Основные реализации: _LinkedList_, _PriorityQueue_. Очереди работают по принципу FIFO – First in First out.
123
124
*Map* - интерфейс для реализации так называемой карты, где элементы хранятся с их ключами. Основные реализации: _HashTable_, _HashMap_, _TreeMap_, _LinkedHashMap_
125
126 7 Александр Александров
* HashTable - синхронизирована, объявлена устаревшей.
127
* HashMap - порядок элементов рассчитывается по хэш ключу;
128 2 Александр Александров
* TreeMap - элементы хранятся в отсортированном порядке
129
* LinkedHashMap - элементы хранятся в порядке вставки
130
131
*%{color: red}Ключи в Мар не могут быть одинаковыми!%*
132
133 14 Александр Александров
Синхронизировать не синхронизированные коллекции и карты можно посредством класса Collections.synchronizedMap(MyMap)\synchronizedList(MyList)\synchronizedSet(MySet).
134 2 Александр Александров
135 1 Александр Александров
h3. Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй?
136
137 2 Александр Александров
Отличие заключается в способе хранения данных. ArrayList хранит в виде массива, а LinkedList - в виде списка (двунаправленного).
138
В ArrayList быстрее происходит сортировка, т.к. для ее выполнения данные списка копируются в массив (а копировать из массива ArrayList в массив для сортировки быстрее). При большом числе операций добавления и удаления LinkedList должен быть более удачным выбором, т.к. при этих операциях не приходится перемещать части массива.
139
Если при добавлении в ArrayList превышается его объем, размер массива увеличивается, новая емкость рассчитывается по формуле (oldCapacity * 3) / 2 + 1, поэтому лучше указывать размер при создании или, если он не известен, использовать LinkedList (но это может быть существенно при слишком уж больших объемах данных).
140 1 Александр Александров
141
h3. Чем отличается HashMap от Hashtable?
142
143 2 Александр Александров
Класс HashMap по функционалу очень похож на Hashtable. Главное отличие в том, что методы класса Hashtable синхронизированы, а HashMap - нет. Кроме этого класс HashMap в отличии от Hashtable разрешает использование null в качестве ключей и значений.
144
Наличие синхронизации в Hashtable уменьшает производительность кода, использующего данный класс. Поэтому классы JCF (Java Collections Framework, появившийся в Java 2), в том числе и HashMap, несинхронизированы. Если синхронизация все же нужна, можно использовать методы класса Collections: Collections.synchronizedMap(map), Collections.synchronizedList(list) или Collections.synchronizedSet(set).
145
Данные методы возвращают синхронизированный декоратор переданной коллекции. При этом все равно в случае итерирования по коллекции требуется ручная синхронизация. Начиная с Java 6 JCF был расширен специальными коллекциями, поддерживающими многопоточный доступ, такими как CopyOnWriteArrayList и ConcurrentHashMap.
146 1 Александр Александров
147
h3. Чем отличается ArrayList от Vector?
148
149 2 Александр Александров
Методы класса Vector синхронизированы, в то время как ArrayList - нет.
150 1 Александр Александров
151 2 Александр Александров
h3. Как сравниваются элементы коллекций?
152 1 Александр Александров
153 2 Александр Александров
Для сравнения элементов коллекций используется метод equals() и hashcode();Эти методы унаследованы от класса Object.
154 1 Александр Александров
155 2 Александр Александров
* Если наш пользовательский класс переопределяет equals(), то он должен и переопределить hashcode().
156
* Если два объекта эквивалентны, то и хэш коды этих объектов тоже должны быть равны.
157
* Если поле не используется в equals(), то оно и не должно использоваться в hashcode().
158
159 1 Александр Александров
h3. Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection,Iterable, Iterator, NavigableSet, NavigableMap.
160
161 2 Александр Александров
{{dmsf_image(200)}}
162 1 Александр Александров
163
h3. Почему Map - это не Collection, в то время как List и Set являются Collection?
164
165 8 Александр Александров
Коллекция (List и Set) представляет собой совокупность некоторых элементов (обычно экземпляров одного класса). Map - это совокупность пар "ключ"-"значение".
166 2 Александр Александров
Соответственно некоторые методы интерфейса Collection нельзя использовать в Map. Например, метод remove(Object o) в интерфейсе Collection предназначен для удаления элемента, тогда как такой же метод remove(Object key) в интерфейсе Map - удаляет элемент по заданному ключу.
167 1 Александр Александров
168
h3. Дайте определение понятию "iterator".
169
170 2 Александр Александров
Итератор - объект, позволяющий перебирать элементы коллекции. Например foreach реализован с использованием итератора. Одним из ключевых методов интерфейса Collection является метод Iterator<E> iterator(). Он возвращает итератор - то есть объект, реализующий интерфейс Iterator. Интерфейс Iterator имеет следующее определение:
171 1 Александр Александров
172 2 Александр Александров
<pre><code class="java">
173
public interface Iterator <E> {
174 15 Александр Александров
    E next();
175 2 Александр Александров
    boolean hasNext();
176
    void remove();
177
}
178
</code></pre>
179 1 Александр Александров
180
h3. Что вы знаете об интерфейсе Iterable?
181
182 2 Александр Александров
Все коллекции из java.util реализуют интерфейс Collection, который, в свою очередь, расширяет интерфейс Iterable. В интерфейсе Iterable описан только один метод: _Iterator iterator();_
183
Он возвращает Iterator, т.е. объект, который поочерёдно возвращает все элементы коллекции.
184 1 Александр Александров
185
h3. Как одной строчкой преобразовать HashSet в ArrayList?
186
187 2 Александр Александров
<pre><code class="java">
188
public static void main(String[] args) {
189
    Set<String> set = new HashSet<>();
190
    set.add("A");
191
    set.add("B");
192
    List<String> list = new ArrayList<>(set);
193
}
194
</code></pre>
195 1 Александр Александров
196
h3. Как одной строчкой преобразовать ArrayList в HashSet?
197
198 2 Александр Александров
<pre><code class="java">
199
public static void main(String[] args) {
200
    List<String> list = new ArrayList<>();
201
    list.add("A");
202
    list.add("B");
203
    Set<String> set = new HashSet<>(list);
204
}
205
</code></pre>
206 1 Александр Александров
207
h3. Как перебрать все ключи Map учитывая, что Map - это не Iterable?
208
209 2 Александр Александров
Использовать метод keySet(), который возвращает множество (Set<K>) ключей.
210 1 Александр Александров
211
h3. Как перебрать все значения Map учитывая, что Map - это не Iterable?
212
213 2 Александр Александров
Использовать метод values(), который возвращает коллекцию (Collection<V>) значений.
214 1 Александр Александров
215
h3. Как перебрать все пары ключ-значение в Map учитывая, что Map - это не Iterable?
216
217 2 Александр Александров
Использовать метод entrySet(), который возвращает множество (Set<Map.Entry<K, V>) пар "ключ"-"значение".
218 1 Александр Александров
219
h3. В чем проявляется "сортированность" SortedMap, кроме того, что toString() выводит все по порядку?
220
221 2 Александр Александров
Естественное упорядочивание (natural ordering) отражается при итерации по коллекции ключей или значений хэш-таблицы (возвращаемых методами keySet(), values() и entrySet()).
222 1 Александр Александров
223
h3. Как одним вызовом копировать элементы из любой Collection в массив?
224
225 2 Александр Александров
<pre><code class="java">
226
public static void main(String[] args) {
227
    List<String> list = new ArrayList<>();
228
    list.add("A");
229
    list.add("B");
230
    String[] strArray = list.toArray(new String[list.size()]);
231
    // или
232
    Object[] objArray = list.toArray();
233
}
234
</code></pre>
235 1 Александр Александров
236 9 Александр Александров
h3. Реализуйте симметричную разность двух коллекций используя методы Collection(addAll(), removeAll(), retainAll()).
237 1 Александр Александров
238 11 Александр Александров
Симметричная разность двух коллекций - это множество элементов, одновременно не принадлежащих обоим исходным коллекциям.
239 1 Александр Александров
240 2 Александр Александров
{{dmsf_image(201)}}
241 1 Александр Александров
242
h3. Сравните Enumeration и Iterator.
243
244 2 Александр Александров
Оба интерфейса предназначены для обхода коллекций. Интерфейс Iterator был введен несколько позднее в Java Collections Framework и его использование предпочтительнее. Основные различия Iterator по сравнению с Enumeration:
245 1 Александр Александров
246 2 Александр Александров
* наличие метода remove() для удаления элемента из коллекции при обходе;
247
* исправлены имена методов для повышения читаемости кода.
248 1 Александр Александров
249
h3. Как между собой связаны Iterable и Iterator?
250
251 2 Александр Александров
Интерфейс Iterable имеет только один метод - iterator(), который возвращает итератор коллекции для её обхода.
252 1 Александр Александров
253
h3. Как между собой связаны Iterable, Iterator и "for-each " введенный в Java 5?
254
255 2 Александр Александров
Экземпляры классов, реализующих интерфейс Iterable, могут использоваться в конструкции foreach
256 1 Александр Александров
257
h3. Сравните Iterator и ListIterator.
258
259 2 Александр Александров
ListIterator расширяет интерфейс Iterator, позволяя клиенту осуществлять обход коллекции в обоих направлениях, изменять коллекцию и получать текущую позицию итератора. При этом важно помнить, что ListIterator не указывает на конкретный элемент, а его текущая позиция располагается между элементами, которые возвращают методы previous() и next(). Таким образом, модификация коллекции осуществляется для последнего элемента, который был возвращен методами previous() и next().
260 1 Александр Александров
261
h3. Что произойдет, если я вызову Iterator.next() не "спросив" Iterator.hasNext()?
262
263 2 Александр Александров
Если итератор указывает на последний элемент коллекции, то возникнет исключение NoSuchElementException, иначе будет возвращен следующий элемент.
264 1 Александр Александров
265
h3. Что произойдет, если я вызову Iterator.next() перед этим 10 раз вызвав Iterator.hasNext()? Я пропущу 9 элементов?
266
267 2 Александр Александров
Нет, hasNext() осуществляет только проверку наличия следующего элемента.
268 1 Александр Александров
269
h3. Если у меня есть коллекция и порожденный итератор, изменится ли коллекция, если я вызову iterator.remove()?
270
271 2 Александр Александров
Вызов метода iterator.remove() возможен только после вызова метода iterator.next() хотя бы раз, иначе появится исключение IllegalStateException(). Если iterator.next() был вызван прежде, то iterator.remove() удалит элемент, на который указывает итератор.
272 1 Александр Александров
273
h3. Если у меня есть коллекция и порожденный итератор, изменится ли итератор, если я вызову collection.remove(..)?
274
275 12 Александр Александров
Итератор не изменится, но при следующем вызове его методов возникнет исключение ConcurrentModificationException.
276 1 Александр Александров
277
h3. Зачем добавили ArrayList, если уже был Vector?
278
279 2 Александр Александров
Обе структуры данных предназначены для хранения коллекции элементов, в том числе дубликатов и null. Они основаны на использовании массивов, динамически расширяющихся при необходимости. Класс Vector был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Vector синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс ArrayList, методы которого не синхронизированы.
280 1 Александр Александров
281 3 Александр Александров
h3. В реализации класса ArrayList есть следующие поля: Object[] elementData, int size. Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?
282 1 Александр Александров
283 2 Александр Александров
Размер массива elementData представляет собой вместимость (capacity) ArrayList, которая всегда больше переменной size - реального количества хранимых элементов. С добавлением новых элементов вместимость автоматически возрастает при необходимости.
284 1 Александр Александров
285 3 Александр Александров
h3. LinkedList - это односвязный, двусвязный или четырехсвязный список?
286 1 Александр Александров
287
Двухсвязный список: каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.
288
289
h3. Какое худшее время работы метода contain() для элемента, который есть в LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
290
291 3 Александр Александров
O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.
292 1 Александр Александров
293
h3. Какое худшее время работы метода contain() для элемента, который есть в ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
294
295 3 Александр Александров
O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.
296 1 Александр Александров
297
h3. Какое худшее время работы метода add() для LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
298
299 3 Александр Александров
O(N). Здесь стоит заметить, что добавление элемента в конец списка с помощью методом add(value), addLast(value) и добавление в начало списка с помощью addFirst(value) выполняется за время O(1). O(N) - будет при добавление элемента в отсортированный список, а также при добавлении элемента с помощью метода add(index, value)
300 1 Александр Александров
301
h3. Какое худшее время работы метода add() для ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
302
303 3 Александр Александров
O(N). Вставка элемента в конец списка осуществляется за время O(1), но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый.
304 1 Александр Александров
305
h3. Сколько выделяется элементов в памяти при вызове ArrayList.add()?
306
307 3 Александр Александров
Если в массиве достаточно места для размещения нового элемента, то дополнительное место в памяти не выделяется. Иначе происходит создание нового массива с размером:
308 1 Александр Александров
309 3 Александр Александров
<pre>
310
int oldCapacity = elementData.length;
311
int newCapacity = oldCapacity + (oldCapacity >> 1);
312
</pre>
313 1 Александр Александров
314 3 Александр Александров
Другими словами, создается новый массив, размер которого вычисляется как умножение старого размера на 1.5 (это верно для JDK 1.7, в более ранних версиях вычисления отличаются).
315
316 1 Александр Александров
h3. Сколько выделяется элементов в памяти при вызове LinkedList.add()?
317
318 3 Александр Александров
Создается один новый экземпляр вложенного класса Node.
319 1 Александр Александров
320
h3. Оцените количество памяти на хранение одного примитива типа byte в LinkedList?
321
322 3 Александр Александров
Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные. Для x32 систем каждая ссылка занимает 32 бита (4 байта). Сам объект типа Node занимает приблизительно 8 байт. Размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типа byte занимает 1 байт памяти, но в списке примитивы упаковываются, соответственно получаем еще 8 байт. Таким образом, в x32 JVM около 32 байтоввыделяется для хранения одного значения типа byte в LinkedList. Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт). Вычисления аналогичны.
323 1 Александр Александров
324
h3. Оцените количество памяти на хранение одного примитива типа byte в ArrayList?
325
326 3 Александр Александров
ArrayList основан на массиве. Каждый элемент массива хранит примитивный тип данных - byte, размер которого 1 байт.
327 1 Александр Александров
328
h3. Я добавляю элемент в середину List-а: list.add(list.size()/2, newElem). Для кого эта операция медленнее - для ArrayList или для LinkedList?
329
330 3 Александр Александров
Для ArrayList:
331 1 Александр Александров
332 3 Александр Александров
* проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив ( O(N) );
333
* копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо ( O(N/2));
334
* вставка элемента ( O(1) ).
335 1 Александр Александров
336 3 Александр Александров
Для LinkedList:
337 1 Александр Александров
338 3 Александр Александров
* поиск позиции вставки ( O(N/2) );
339
* вставка элемента ( O(1) ).
340 1 Александр Александров
341 3 Александр Александров
В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет системного метода System.arraycopy().
342 1 Александр Александров
343 3 Александр Александров
h3. Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)?
344
345
Использовать обратный итератор. Для этого в LinkedList есть метод descendingIterator().
346
347 1 Александр Александров
h3. Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?
348
349 3 Александр Александров
<pre>
350
List<Integer> sourceList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
351
List<Integer> subList = sourceList.subList(3, sourceList.size() - 3);
352
</pre>
353 1 Александр Александров
354
355
h3. Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.hashCode() == ref1.hashCode()?
356
357 3 Александр Александров
Да, могут. Метод hashCode() не гарантирует уникальность возвращаемого значения.
358 1 Александр Александров
359
h3. Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.equals(ref1) == true?
360
361 3 Александр Александров
Да, могут. Для этого в классе этих объектов должен быть переопределен метод equals(). Если используется метод Object.equals(), то для двух ссылок x и y метод вернет true тогда и только тогда, когда обе ссылки указывают на один и тот же объект (т.е. x == y возвращает true).
362 1 Александр Александров
363 18 Александр Александров
h3. Могут ли у разных ссылок на один объект в памяти (ref0 = = ref1) быть ref0.equals(ref1) = = false?
364 1 Александр Александров
365 3 Александр Александров
Нет, не может. Метод equals() должен гарантировать свойство рефлексивности: для любых ненулевых ссылок xметод x.equals(x) должен возвращать true.
366 1 Александр Александров
367
h3. Есть класс Point{int x, y;}. Почему хэш-код в виде 31 * x + y предпочтительнее чем x + y?
368
369 3 Александр Александров
Множитель создает зависимость значения хэш-кода от очередности обработки полей, а это дает гораздо лучшую хэш-функцию.
370 1 Александр Александров
371 19 Александр Александров
h3. Если у класса Point{int x, y;} "правильно " реализовать метод equals (return ref0.x = = ref1.x && ref0.y = = ref1.y), но сделать хэш-код в виде int hashCode() {return x;}, то будут ли корректно такие точки помещаться и извлекаться из HashSet?
372 1 Александр Александров
373 3 Александр Александров
HashSet использует HashMap для хранения элементов (в качестве ключа используется сам объект). При добавлении элемента в HashMap вычисляется хэшкод и позиция в массиве, куда будет вставлен новый элемент. У всех экземпляров класса Point одинаковый хэшкод, что приводит в вырождению хэш-таблицы в список. При возникновении коллизии осуществляется проверка на наличие уже такого элемента в текущем списке:
374 1 Александр Александров
375 3 Александр Александров
<pre>
376 21 Александр Александров
if (e.hash == hash && (e.key == key || key.equals(e.key))) {
377
    V oldValue = e.value;
378
    e.value = value;       
379
    return oldValue;
380
}
381 3 Александр Александров
</pre>
382 1 Александр Александров
383 3 Александр Александров
Если элемент найден, то его значение перезаписывается. В нашем случае для разных объектов метод equals() будет возвращать false. Соответственно новый элемент будет добавлен в HashSet. Извлечение элемента также будет осуществляться успешно. Но производительность такого кода будет низкой и преимущества хэштаблиц использоваться не будут.
384
385 1 Александр Александров
h3. equals() порождает отношение эквивалентности. Какими из свойств обладает такое отношение: коммутативность, симметричность, рефлексивность, дистрибутивность, ассоциативность, транзитивность?
386
387 3 Александр Александров
Метод equals() должен обеспечивать:
388 1 Александр Александров
389 3 Александр Александров
* симметричность (для любых ненулевых ссылок x и y метод x.equals(y) должен возвращать true тогда и только тогда, когда y.equals(x) возвращает true);
390
* рефлексивность (для любых ненулевых ссылок x метод x.equals(x) должен возвращать true.);
391
* транзитивность (для любых ненулевых ссылок x, y и z, если x.equals(y) возвращает true и y.equals(z)возвращает true, тогда и x.equals(z) должен возвращать true).
392 1 Александр Александров
393 3 Александр Александров
Также есть ещё два свойства: постоянство и неравенство null.
394
395 22 Александр Александров
h3. Можно ли так реализовать equals(Object that) {return this.hashCode() = = that.hashCode()}?
396 1 Александр Александров
397 3 Александр Александров
Строго говоря нельзя, поскольку метод hashCode() не гарантирует уникальность значения для каждого объекта. Однако для сравнения экземпляров класса Object такой код допустим, т.к. метод hashCode() в классе Object возвращает уникальные значения для разных объектов (вычисления основаны на использовании адреса объекта в памяти).
398 1 Александр Александров
399
h3. В equals требуется проверять, что аргумент (equals(Object that)) такого же типа как и сам объект. В чем разница между this.getClass() == that.getClass() и that instanceof MyClass?
400
401 3 Александр Александров
Оператор instanceof сравнивает объект и указанный тип. Его можно использовать для проверки является ли данный объект экземпляром некоторого класса, либо экземпляром его дочернего класса, либо экземпляром класса, который реализует указанный интерфейс. getClass() = ... проверяет два типа на идентичность. Для корректной реализации контракта метода equals() необходимо использовать точное сравнение с помощью getClass().
402 1 Александр Александров
403 23 Александр Александров
h3. Можно ли реализовать метод equals класса MyClass вот так: class MyClass {public boolean equals(MyClass that) {return this = = that;}}?
404 1 Александр Александров
405 3 Александр Александров
Реализовать можно, но данный метод не переопределяет метод equals() класса Object, а перегружает его.
406 1 Александр Александров
407
h3. Будет ли работать HashMap, если все ключи будут возвращать int hashCode() {return 42;}?
408
409 3 Александр Александров
Да, будет. Но тогда хэш-таблица вырождается в связный список и теряет свои преимущества.
410 1 Александр Александров
411
h3. Зачем добавили HashMap, если уже был Hashtable?
412
413 3 Александр Александров
Класс Hashtable был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Hashtable синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс HashMap, методы которого не синхронизированы.
414
Помимо этого класс HashMap обладает некоторыми другими отличиями: например, позволяет хранить один null ключ и множество null значений.
415 1 Александр Александров
416
h3. Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресацией и на основе метода цепочек. Как реализована HashMap? Почему так сделали (по вашему мнению)? В чем минусы и плюсы каждого подхода?
417
418 3 Александр Александров
Класс HashMap реализован с использованием метода цепочек, т.е. каждой ячейке массива соответствует свой связный список и при возникновении коллизии осуществляется добавление нового элемента в этот список. Для метода цепочек коэффициент заполнения может быть больше 1, с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов, либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения. Среди методов открытой реализации различают:
419 1 Александр Александров
420 3 Александр Александров
* линейное пробирование;
421
* квадратичное пробирование;
422
* двойное хеширование.
423
424
Основные недостатки структур с методом открытой адресации: 
425
426
* Количество элементов в таблице не может превышать размера массива. По мере увеличения числа элементов в таблице и повышения коэффициента заполнения (load factor) производительность структуры резко падает, поэтому необходимо проводить перехеширование.
427
* Сложно организовать удаление элемента.
428
* Также первые два метода открытой адресации приводят к проблеме первичной и вторичной группировок.
429
430
Основное преимущество хэш-таблицы с открытой адресацией - это отсутствие затрат на создание и хранение объектов списка. Также проще организовать сериализацию/десериализацию объекта.
431
432 1 Александр Александров
h3. Сколько переходов по ссылкам происходит, когда вы делаете HashMap.get(key) по ключу, который есть в таблице?
433
434 3 Александр Александров
Возможно, я неправильно понял этот вопрос. За переходы по ссылке в данном ответе я считаю вызовы методов.
435 1 Александр Александров
436 3 Александр Александров
{{dmsf_image(204)}}
437
438
Рассмотрим первый случай, когда ключ равен null: выполняем метод getForNullKey().
439
440
{{dmsf_image(203)}}
441
442
В цикле foreach проходимся по списку значений для ключа и возвращаем нужное значение. Таким образом, получаем 1 переход. Второй случай: ключ не равен null. Выполняем метод getEntry(key).
443
444
{{dmsf_image(202)}}
445
446
Вычисляется хэш-код ключа (метод hash(key)), затем определяется индекс ячейки массива, в которой будем искать значение (метод indexFor(hash, table.length)). После того, как нашли нужную пару "ключ-значение" возвращаем значение (метод entry.getValue()). Таким образом, получаем 4 перехода.
447
448 1 Александр Александров
h3. Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap?
449
450 3 Александр Александров
Один новый объект статического вложенного класса Entry<K,V>.
451 1 Александр Александров
452
h3. Как работает HashMap при попытке сохранить в нее два элемента по ключам с одинаковым hashCode, но для которых equals == false?
453
454 3 Александр Александров
По значению hashCode вычисляется индекс ячейки массива, в список которой будет происходить добавление элемента. Перед добавлением осуществляется проверка на наличие уже элементов в этой ячейке. Если
455
элементов нет, то происходит добавление. Если возникает коллизия, то итеративно осуществляется обход списка в поисках элемента с таким же ключом и хэш-кодом. Если такой элемент найден, то его значение перезаписывается, а старое - возвращается. Поскольку в условии сказано, что добавляемые ключи - разные, то второй элемент будет добавлен в начало списка.
456 1 Александр Александров
457
h3. HashMap может выродиться в список даже для ключей с разным hashCode. Как это возможно?
458
459 3 Александр Александров
Это возможно в случае, если метод, определяющий номер ячейки массива по hashCode будет возвращать одинаковое значение.
460 1 Александр Александров
461
h3. Какое худшее время работы метода get(key) для ключа, которого нет в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
462
463 3 Александр Александров
O(N). Худший случай - это поиск ключа в таблице, вырожденной в список, перебор ключей которой занимает линейно пропорциональное время количеству хранимых элементов.
464 1 Александр Александров
465
h3. Какое худшее время работы метода get(key) для ключа, который есть в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
466
467 3 Александр Александров
O(N). Аналогичные рассуждения, что и для предыдущего вопроса.
468 1 Александр Александров
469
h3. Объясните смысл параметров в конструкторе HashMap(int initialCapacity, float loadFactor).
470
471 3 Александр Александров
*int initialCapacity* - исходный размер HashMap (количество корзин в хэштаблице в момент её создания), по умолчанию имеет значение 16. 
472 1 Александр Александров
473 3 Александр Александров
*float loadFactor* - коэффициент заполнения HashMap. Равен отношению числа хранимых элементов в таблице к её размеру. loadFactor - является мерой заполнения таблицы элементами, при превышении количества хранимых таблицей значений , происходит автоматическое перехеширование. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных.
474
475 1 Александр Александров
h3. В чем разница между HashMap и IdentityHashMap? Для чего нужна IdentityHashMap? Как может быть полезна для реализации сериализации или клонирования?
476 3 Александр Александров
477 4 Александр Александров
IdentityHashMap - это структура данных, реализующая интерфейс Map, но использующая сравнение ссылок вместо метода equals() при сравнении ключей (значений). Другими словами, в IdentityHashMap два ключа k1 и k2 будут рассматриваться равными, если выполняется условие k1 == k2. IdentityHashMap не использует метод hashCode(), вместо которого применяется метод System.identityHashCode(Object).
478
Другое отличие (как следствие) заключается в более высокой производительности IdentityHashMap по сравнению с HashMap, если последний хранит объекты с дорогостоящими методами equals() и hashCode(). Одним из основных требований к использованию HashMap является неизменяемость ключа, однако это требование не распространяется на IdentityHashMap, который не использует методы equals() и hashCode(). Согласно документации, такая структура данных может применяться для реализации сериализации/клонирования. Для выполнения подобных алгоритмов программе необходимо обслуживать таблицу со всеми ссылками на объекты, которые уже были обработаны. Такая таблица не должна рассматривать уникальные объекты как равные, даже если метод equals() возвращает true.
479 1 Александр Александров
480
h3. В чем разница между HashMap и WeakHashMap? Для чего нужна WeakHashMap?
481
482 4 Александр Александров
Перед рассмотрением WeakHashMap кратко напомню, что такое WeakReference. В Java существует 4 типа ссылок: сильные (strong reference), мягкие (SoftReference), слабые (WeakReference) и фантомные (PhantomReference). Особенности каждого типа ссылок связаны с работой Garbage Collector. Если объект можно достичь только с помощью цепочки WeakReference (то есть на него не ссылаются сильные и мягкие ссылки), то данный объект будет отмечен для удаления.
483 1 Александр Александров
484 4 Александр Александров
WeakHashMap - это структура данных, реализующая интерфейс Map и основанная на использовании WeakReference для хранения ключей. Таким образом, пара "ключ-значение" будет удалена из WeakHashMap, если на объект-ключ более не имеется сильных ссылок.
485
486
В качестве примера использования такой структуры данных можно привести следующую ситуацию: допустим имеются объекты, которые необходимо расширить дополнительной информацией, при этом изменение класса этих объектов нежелательно либо невозможно. В этом случае добавляем каждый объект в WeakHashMap в качестве ключа, а в качестве значения - нужную информацию. Таким образом, пока на объект имеется сильная ссылка (либо мягкая), можно проверять хэш-таблицу и извлекать информацию. Как только объект будет удален, то WeakReference для этого ключа будет помещен в ReferenceQueue и затем соответствующая запись для этой слабой ссылки будет удалена из WeakHashMap.
487
488 1 Александр Александров
h3. В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences?
489
490 4 Александр Александров
SoftHashMap представлена в стронних библиотеках, например, в Apache Commons.
491 1 Александр Александров
492
h3. В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences?
493
494 4 Александр Александров
PhantomReference при вызове метода get() возвращает всегда null, поэтому, я думаю, создание PhantomHashMap просто невозможно. Плюс назначение такой структуры данных тяжело представить.
495 1 Александр Александров
496
h3. Сделайте HashSet из HashMap (используйте только множество ключей, но не множество значений).
497
498 4 Александр Александров
<pre>
499
Set<Object> keySet = new HashSet<>(map.keySet());
500
</pre>
501 1 Александр Александров
502
h3. Сделайте HashMap из HashSet (HashSet<Map.Entry<K, V>>)
503
504 4 Александр Александров
Map<K, V> map = new HashMap<>(set.size());
505
for (Map.Entry<K,V> netry : set {
506
    map.put(entry.getKey(), entry.getValue());
507
}
508 1 Александр Александров
509
h3. Сравните интерфейсы java.util.Queue и java.util.Deque.
510
511 4 Александр Александров
Согласно документации Deque ("дек", Double Ended Queue) - это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса Deque могут строится по принципу FIFO, либо LIFO. 
512 1 Александр Александров
513 4 Александр Александров
*Queue* - это очередь, обычно (но необязательно) строится по принципу FIFO (First-In-First-Out) - соответственно извлечение элемента осуществляется с начала очереди, вставка элемента - в конец очереди. Этот принцип нарушает, к примеру, приоритетная очередь (PriorityQueue), использующая переданный comparator при вставке нового элемента, либо расстановка элементов осуществляется согласно естественному упорядочиванию (natural ordering).
514
515
*Deque* - расширяет Queue. Реализации и Deque, и Queue обычно не переопределяют методы equals() и hashCode(), основанные на сравнении хранящихся элементов. Вместо этого используются унаследованные методы класса Object, основанные на сравнении ссылок.
516
517 1 Александр Александров
h3. Кто кого расширяет: Queue расширяет Deque, или Deque расширяет Queue?
518
519 4 Александр Александров
Deque расширяет Queue.
520 1 Александр Александров
521
h3. Почему LinkedList реализует и List, и Deque?
522
523 4 Александр Александров
LinkedList позволяет добавлять элементы в начало и конец списка за константное время, что хорошо подходит для реализации интерфейса Deque (в отличие, например, от ArrayList).
524 1 Александр Александров
525
h3. В чем разница между классами java.util.Arrays и java.lang.reflect.Array?
526
527 4 Александр Александров
java.util.Arrays - класс, содержащий статические методы для работы с массивами, таких как, например, поиск по массиву и его сортировка. java.lang.reÚect.Array - класс для работы с массивами при использовании рефлексии. Рефлексия - это механизм, позволяющий исследовать данные о программе во время её выполнения.
528 1 Александр Александров
529
h3. В чем разница между классами java.util.Collection и java.util.Collections?
530
531 4 Александр Александров
Класс java.util.Collections содержит исключительно статические методы для работы с коллекциями. В них входят методы, реализующие полиморфные алгоритмы (такие алгоритмы, использование которых возможно с разными видами структур данных), "оболочки", возвращающие новую коллекцию с инкапсулированной указанной структурой данных и некоторые другие методы.
532 1 Александр Александров
533 4 Александр Александров
*java.util.Collection* - это корневой интерфейс Java Collections Framework. Этот интерфейс в основном применяется там, где требуется высокий уровень абстракции, например, в классе java.util.Collections.
534
535 1 Александр Александров
h3. Напишите НЕмногопоточную программу, которая заставляет коллекцию выбросить ConcurrentModificationException.
536
537 4 Александр Александров
{{dmsf_image(205)}}
538 1 Александр Александров
539
h3. Что такое "fail-fast поведение"?
540
541 4 Александр Александров
Fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом. 
542 1 Александр Александров
543 4 Александр Александров
В Java Collections API итераторы могут использовать либо fail-fast, либо fail-safe поведение, либо быть weakly consistent. Итератор с fail-fast поведением выбросит исключение ConcurrentModiÙcationException, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент (без использования метода remove() итератора). Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):
544
545
* при изменении коллекции (удаление/добавление элемента) счетчик увеличивается;
546
* при создании итератора ему передается текущее значение счетчика;
547
* при каждом обращении к итератору сохраненное значение счетчика сравнивается с текущим, и, если они не совпадают, возникает исключение.
548
549
Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени. Также стоит отметить, что fail-fast поведение не может быть абсолютно гарантировано.
550
551 1 Александр Александров
h3. Для множеств еnum-ов есть специальный класс java.util.EnumSet? Зачем? Чем авторов не устраивал HashSet или TreeSet?
552
553 4 Александр Александров
*EnumSet* - это одна из разновидностей реализации интерфейса Set для использования с перечислениями (Enum). EnumSet использует массив битов для хранения значений (bit vector), что позволяет получить высокую компактность и эффективность. В структуре данных хранятся объекты только одного типа Enum, который указывается при создании экземпляра EnumSet. Все основные операции выполняются за константное время (O(1)) и в основном несколько быстрее (хотя и негарантированно), чем их аналоги в реализации HashSet. Пакетные операции (bulk operations, например, containsAll() и retainAll()) выполняются очень быстро, если их аргументом является экземпляр типаEnum.
554 1 Александр Александров
555 4 Александр Александров
Помимо этого класс EnumSet предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров. Итерация по EnumSet осуществляется согласно порядку объявления элементов перечисления
556
557 1 Александр Александров
h3. java.util.Stack - считается "устаревшим". Чем его рекомендуют заменять? Почему?
558
559 4 Александр Александров
Рекомендуется использовать интерфейс Deque ("дек", Double Ended Queue) и его реализации. Например:
560 1 Александр Александров
561 4 Александр Александров
<pre>
562
Deque<Integer> stack = new ArrayDeque<Integer>();
563
</pre>
564
565
*Стек* - это структура данных, построенная на принципе LIFO (Last-In-First-Out, либо по-другому FILO). Каждое новое значение добавляется на "вершину" стека, а извлекается последний добавленный элемент (с "вершины" стека). При извлечении элемента он удаляется из структуры данных. Класс Stack появился в JDK 1.0 и расширяет класс Vector, наследуя его функционал, что несколько нарушает понятие стека (например, класс Vector предоставляет возможность обращаться к любому элементу по индексу). Также использование Deque позволяет следовать принципу программирования на уровне интерфейсов, а не конкретных реализаций, что облегчает дальнейшую поддержку разрабатываемого класса и повышает его гибкость, позволяя при необходимости менять реализацию дека на нужную.
566
567 1 Александр Александров
h3. Какая коллекция реализует дисциплину обслуживания FIFO?
568
569 4 Александр Александров
FIFO - First-In-First-Out (первый пришел, первым ушел). По этому принципу обычно построена такая структура данных как очередь (java.util.Queue).
570 1 Александр Александров
571
h3. Какая коллекция реализует дисциплину обслуживания FILO?
572
573 4 Александр Александров
FILO - First-In-Last-Out (первый пришел, последним ушел). По этому принципу построена такая структура данных как стек (java.util.Stack).
574 1 Александр Александров
575
h3. Приведите пример, когда какая-либо коллекция выбрасывает UnsupportedOperationException.
576
577 4 Александр Александров
{{dmsf_image(206)}}
578 1 Александр Александров
579 4 Александр Александров
В данном примере возникнет исключение UnsupportedOperationException, поскольку метод asList() возвращает список фиксированной длины, т.е. удаление/добавление элементов в такой список не поддерживается.
580
581 1 Александр Александров
h3. Почему нельзя написать "ArrayList<List> numbers = new ArrayList<ArrayList>();" но можно "List<ArrayList> numbers = new ArrayList<ArrayList>();"?
582
583 4 Александр Александров
Это связано с ограничениями использования generic types (обобщенных типов). ArrayList<ArrayList> не является подтипом ArrayList<List>, соответственно использование такой записи запрещено.
584 1 Александр Александров
585
h3. LinkedHashMap - что это еще за "зверь"? Что в нем от LinkedList, а что от HashMap?
586
587 4 Александр Александров
Реализация LinkedHashMap отличается от HashMap поддержкой двухсвязанного списка, определяющего порядок итерации по элементам структуры данных. По умолчанию элементы списка упорядочены согласно их порядку добавления в LinkedHashMap (insertion-order). Однако порядок итерации можно изменить, установив параметр конструктора accessOrder в значение true. В этом случае доступ осуществляется по порядку последнего обращения к элементу (access-order). Это означает, что при вызове методов get() или put() элемент, к которому обращаемся, перемещается в конец списка. 
588 1 Александр Александров
589 4 Александр Александров
При добавлении элемента, который уже присутствует в LinkedHashMap (т.е. с одинаковым ключом), порядок итерации по элементам не изменяется.
590 1 Александр Александров
591
h3. Говорят, на LinkedHashMap легко сделать простенький кэш c "invalidation policy", знаете как?
592
593 4 Александр Александров
Необходимо использовать LRU-алгоритм (Least Recently Used algorithm) и LinkedHashMap с access-order. В этом случае при обращении к элементу он будет перемещаться в конец списка, а наименее используемые элементы будут постепенно группироваться в начале списка. Для этого в стандартной реализации LinkedHashMap (source) есть метод removeEldestEntries(), который возвращает true, если текущий объект LinkedHashMap должен удалить наименее используемый элемент из коллекции. Метод вызывается при использовании методов put() и putAll():
594 1 Александр Александров
595 4 Александр Александров
{{dmsf_image(208)}}
596
597
Простой пример реализации кэша с очисткой старых значений при превышении указанного порога:
598
599
{{dmsf_image(207)}}
600
601
Стоит заметить, что LinkedHashMap не позволяет полностью реализовать LRUалгоритм, поскольку при вставке уже имеющегося в коллекции элемента порядок итерации не меняется.
602
603 1 Александр Александров
h3. Что позволяет сделать PriorityQueue?
604
605 4 Александр Александров
PriorityQueue - это структура данных, располагающая элементы в порядке натурального упорядочивания, либо используя переданный конструктору Comparator. Используя PriorityQueue, можно, например, реализовать алгоритм Дейкстры для поиска кратчайшего пути от одной вершины графа к другой. Либо применять для хранения объектов согласно их приоритету: например, сортировка пациентов врача - экстренные пациенты перемещаются в начало очереди, менее срочные пациенты - ближе к концу очереди
606 1 Александр Александров
607
h3. В чем заключаются отличия java.util.Comparator от java.lang.Comparable?
608 4 Александр Александров
609
Interface Comparable задает свойство сравнения объекту реализующему его. То есть делает объект сравнимым (по правилам разработчика). Interface Comparator позволяет создавать объекты, которые будут управлять процессом сравнения (например при сортировках).
Go to top