Вопросы по java (коллекции)

Иерархия коллекций.

 

Чем отличается ArrayList от LinkedList?
ArrayList - по сути массив объектов определенного типа. По умолчанию размерность (capacity) 10 элементов. При заполнении создается новый массив размерностью 3/2 * (старая размерность), и значения старого массива копируются в новый System.arraycopy(); При добавлении(удалении) элемента в середину, значения массива сдвигаются опять же посредством System.arraycopy(); Если при вставке размерности массива не хватает , System.arraycopy() вызывается дважды. При удалении capacity не уменьшается - что приводит к своеобразным утечкам памяти. Поэтому не стоит пренебрегать методом trimToSize(). Доступ по индексу O(1), доступ по значению О(n)

LinkedList - двунаправленный связанный список. Вставка(удаление) в начало\конец за O(1), в середину O(n). Выборка не из начала\ конца - O(n).

Что вы обычно используете (ArrayList или LinkedList)? Почему?
Что быстрее работает ArrayList или LinkedList?
Зависит от специфики задачи. LinkedList может пригодиться при необходимости очереди; если известно, что добавление в список только в начало\конец, нет необходимости в произвольном доступе.
Как происходит удаление элементов из ArrayList? Как меняется в этом случае размер ArrayList?
Сдвиг массива с помощью System.arraycopy(), никак не мяняется.
Предложите эффективный алгоритм удаления нескольких элементов из середины списка, реализуемого ArrayList.
removeAll, removeRange
Необходимо добавить 1млн. элемент, какую структуру вы используете?
вопрос некорректен. Требуется уточнить требования к задаче (какой доступ к элемента, как будет происходить добавление)



Как устроена HashMap?
Новоявленный объект hashmap, содержит ряд свойств:

• table — Массив типа Entry[], который является хранилищем ссылок на списки (цепочки) значений;
• loadFactor — Коэффициент загрузки. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных;
• threshold — Предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
• size — Количество элементов HashMap-а

При добавлении элемента, последовательность шагов следующая:

  1. проверка на null, putForNullKey(value) если true

  2 Далее генерируется хэш на основе ключа. Для генерации используется метод hash(hashCode), в который передается key.hashCode().

static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }

метод hash(key) гарантирует что полученные хэш-коды, будут иметь только ограниченное количество коллизий

  3. С помощью метода indexFor(hash, tableLength), определяется позиция в массиве, куда будет помещен элемент.
  4. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Хэш и ключ нового элемента поочередно сравниваются с хэшами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается.
   5.  Если же предыдущий шаг не выявил совпадений, будет вызван метод addEntry(hash, key, value, index) для добавления нового элемента.

Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов.  resize(capacity) и transfer(newTable)
У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается.
Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии. Среднее же время работы будет Θ(1 + α), где α — коэффициент загрузки. В самом худшем случае, время выполнения может составить Θ(n) (все элементы в одной цепочке);




Какое начальное количество корзин в HashMap?
16Какая оценка временной сложности выборки элемента из HashMap?
зависит от hash-функции. см. выше
Гарантирует ли HashMap указанную сложность выборки элемента?
гарантирует Θ(1 + α)
Роль equals и hashCode в HashMap?
hashCode участвует в определении "корзины", и затем в сравнении элементов в цепочке участвуют hashCode  и equals 
Максимальное число значений hashCode()?
int  от -2.147.483.648 до 2.147.483.647
Как и когда происходит увеличение количества корзин в HashMap?
при добавлении     if (size++ >= threshold)

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


WeakHashMap - при отсутствии других ссылок на ключ элемента, элемент готов к удалению gc. (т.е. ссылка внутри WeakHashMap как бы не в счет)