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

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

● Использовать ConcurrentHashMap и CopyOnWriteArrayList.

● Преобразовать список в массив и перебирать массив.

● Блокировать изменения списка на время перебора с помощью блока synchronized.

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

 

50. Iterable & Iterator. Enumerated vs. Iterator.

Чем различаются Enumeration и Iterator?

Хотя оба интерфейса и предназначены для обхода коллекций между ними имеются существенные различия:

● с помощью Enumeration нельзя добавлять/удалять элементы;

● в Iterator исправлены имена методов для повышения читаемости кода (Enumeration.hasMoreElements() соответствует Iterator.hasNext(), Enumeration.nextElement() соответствует Iterator.next() и т.д);

● Enumeration присутствуют в устаревших классах, таких как Vector/Stack, тогда как Iterator есть во всех современных классах-коллекциях.

 

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

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

 

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

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

 

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

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

 

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

Классы, реализующие интерфейс Iterable, могут применяться в конструкции for-each, которая использует Iterator.

 

51. Comparator vs. Comparable.

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

Затем мы должны спросить себя, зачем использовать Comparator, если у нас уже есть Comparable?

Есть несколько причин, почему:

● Иногда мы не можем изменить исходный код класса, чьи объекты мы хотим отсортировать, что делает невозможным использование Comparable

● Использование компараторов позволяет нам избежать добавления дополнительного кода в классы нашего домена

● Мы можем определить несколько разных стратегий сравнения, что невозможно при использовании Comparable

 

52. Iterator vs. ListIterator.

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

● ListIterator расширяет интерфейс Iterator

● ListIterator может быть использован только для перебора элементов коллекции List;

● Iterator позволяет перебирать элементы только в одном направлении, при помощи метода next(). Тогда как ListIterator позволяет перебирать список в обоих направлениях, при помощи методов next() и previous();

● ListIterator не указывает на конкретный элемент: его текущая позиция располагается между элементами, которые возвращают методы previous() и next().

● При помощи ListIterator вы можете модифицировать список, добавляя/удаляя элементы с помощью методов add() и remove(). Iterator не поддерживает данного функционала.

 

53. ArrayList vs. Vector.

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

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

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

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

 

54. Queue vs. Deque.

Сравните интерфейсы Queue и Deque. Кто кого расширяет: Queue расширяет Deque, или Deque расширяет Queue?

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

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

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

 

55. PriorityQueue.

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

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

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

 

56. HashMap vs. HashTable.

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

● Методы класса Hashtable синхронизированы, что приводит к снижению производительности, а HashMap - нет;

● HashTable не может содержать элементы null, тогда как HashMap может содержать один ключ null и любое количество значений null;

● Iterator у HashMap, в отличие от Enumeration у HashTable, работает по принципу «fail-fast» (выдает исключение при любой несогласованности данных).

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

 

57. Устройство HashMap.

Как устроен HashMap?

HashMap состоит из «корзин» (bucket). С технической точки зрения «корзины» — это элементы массива, которые хранят ссылки на списки элементов. При добавлении новой пары «ключ-значение», вычисляет хэш-код ключа, на основании которого вычисляется номер корзины (номер ячейки массива), в которую попадет новый элемент. Если корзина пустая, то в нее сохраняется ссылка на вновь добавляемый элемент, если же там уже есть элемент, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется.

 

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

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

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

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

● линейное пробирование;

● квадратичное пробирование;

● двойное хэширование.

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

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

● Сложно организовать удаление элемента.

● Первые два метода открытой адресации приводят к проблеме первичной и вторичной группировок.

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

● отсутствие затрат на создание и хранение объектов списка;

● простота организации сериализации/десериализации объекта.

 

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

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