Что такое коллизия java

Почему возникают коллизии?

Как известно, ситуация, когда у разных объектов одинаковые хеш-коды называется — коллизией. Вероятность возникновения коллизии зависит от используемого алгоритма генерации хеш-кода. Но вот вопрос, почему она возникает? Неужели тяжко придумать «защиту» от возникновения коллизии? Кто что думает?

Отслеживать
задан 30 окт 2017 в 22:06
432 2 2 золотых знака 6 6 серебряных знаков 14 14 бронзовых знаков
Результат хеш-функции может быть короче ее аргумента. Коллизий избежать невозможно.
– user239133
30 окт 2017 в 22:11
Вообще, есть perfect hash function (идеальная хэш-функция)
31 окт 2017 в 0:33

Вероятность возникновения коллизии зависит от используемого алгоритма генерации хеш-кода. Нет. Если алгоритмы хэширования не содержат статистических, математических и прочих погрешностей, вероятность коллизии зависит только от длины формируемого хэша.

31 окт 2017 в 5:01

Неужели тяжко придумать «защиту» от возникновения коллизии? Да элементарно. Просто длина хэша должна быть не меньше максимальной длины хэшируемых данных (с учётом пэддинга).

31 окт 2017 в 5:02

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Хеш код в java создается методом

 public int hashCode() 

У integer диапазон от -2147483648 до 2147483647, т.е. округлив получаем 4 миллиарда разных целых чисел.

А теперь представим ситуацию, у вас 8-10 миллиардов объектов. Вопрос: как каждому из них дать уникальный хеш код используя диапазон в 4 миллиарда?

При этом вы не знаете сколько объектов вашего класса могут создать пользователи.

Если ваш класс будет использоваться в Hash структурах как ключ, вы так же должны постараться обеспечить объекты такими хеш кодами, чтобы они попадали в разные корзины и получить равномерное заполнение структуры.

Коллизии HashCode

Представьте, вы пишите мессенжер или почтовый клинт. Вам придется работать с кучей повторяющихся строковых значений. Например в чате — какой-то влюбленный Вася может спамить десятки аналогичных признаний в любви своей даме сердца Насте. Но мы то знаем, что все Насти шлю** Наверняка мы захотим как-то кэшировать эти сообщения. Для этого подойдет HashMap или HashSet, например. Все знают, что эти структуры данных, ссылаются на хэш значение объекта, которое не бесконечно, а ограничено 32 битами. Но проблемы могут начаться уже с пары строк.

Пример такой коллизии:

fun main()  ​//generates 310265957 as hashcode ​​print("I have a common prefixDB".hashCode()) //generates 310265957 as hashcode print("I have a common prefixCa".hashCode()) >

Вообще если длина строк одинаковая и выполняется:

31*(b[n-2] — a[n-2]) == (a[n-1] — b[n-1])

то, хэши всегда будут одинаковыми, не буду вдаваться в подробности почему так 😀

Окей, хэши могут быть одинаковыми на ровном месте, но по какому принципу они рассчитываются?

Стандартная реализация hashCode

Посмотри сгенерированный idea hashCode() для простого POJO класса.

class Lover( private val id: Long, private val name: String, private val mum: Mum? )  // Также генерится реализация equals, зачем она нужна узнаем ниже override fun equals(other: Any?): Boolean  if (this === other) return true if (javaClass != other?.javaClass) return false other as Lover if (id != other.id) return false if (name != other.name) return false if (mum != other.mum) return false return true > override fun hashCode(): Int  var result = id.hashCode() result = 31 * result + name.hashCode() result = 31 * result + (mum?.hashCode() ?: 0) // Если объект null, он не влияет return result > >

У String, кстати свой алгоритм: h(s)=∑(s[index] * 31 ^(n-1-index)) Смысл тот же, только проходим по всем char

31

Как вы заметили везде используется это непонятное число 31. Вопрос: А че не 41 или 97, например?

А по каким критериям оно отбирается?

• Число должно быть простым и нечетным, чтобы уменьшить вероятность коллизий.
• Число должно занимать мало места в памяти
• Умножение должно выполняться быстро

Оказывается 31 идеальный кандидат ведь:

• Оно простое и нечетное
• Занимает всего 1 байт в памяти
• Уго умножение можно заменить на быстрый побитовой сдвиг. 31 * i == (i

Побитовой сдвиг влево на x позиций. Работает точно также как умножить какое-то число на 2 x раз.

println(n.shl(1)) // 6 println(n.shl(2)) // 12 println(n.shl(3)) // 24

Вернемся к сути.

Окей, выяснили, по какому принципу считается HashCode и что в любой момент может произойти коллизия и данные перетрутся. Так че делать?

Да ничего, HashMap и HashSet самоcтоятельно обрабытывают такие ситуации. Важно только правильно переопределить метод equals(o) у класса.

Логика работы такая:

1. Кладем в список объект по ключу “cat”
2. Кладем в него другой по этому же ключу
3. HashMap/Set проверяет равны ли эти объекты в методе equals
4. Если равны — заменяет, если нет, создает в этой ячейке связный список, а например в седьмой джаве бакет в HashMap, при появлении в нём более семи объектов, меняет начинку со связного списка на дерево.

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

Поэтому если все же решили использовать String в качестве ключа, можно за основу брать 2 простых числа, скажем 17 и 37. Ребята из Project Lombok придумали здесь

fun main(args: ArrayString>)  val first = BetterHashString("I have a common prefixDB") val second = BetterHashString("I have a common prefixCa") println(first.hashCode()) // 177503352 println(second.hashCode()) // 177503346 > class BetterHashString(val value: String)  override fun hashCode(): Int  val prime = 37 var result = 17 value.chars().forEach  c -> result = prime * result + c > return result > >

Минуточку

Переопределил я hashCode() , но как-же теперь JVM узнает, на какой адрес в памяти ссылается этот объект?

На самом деле у каждого объекта есть идентификационный хеш (identity hash code). Если класс переопределил hashCode() , всегда можно вызвать System.identityHashCode(o) .

Да и вообще, hashCode() не возвращает какой-либо адрес объекта в памяти, что бы это не значило. В версиях java 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока. Подробнее об этом можно почитать здесь

Разрешение коллизий

Разрешение коллизий (англ. collision resolution) в хеш-таблице, задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это увеличивает время работы с хеш-таблицами.

Разрешение коллизий с помощью цепочек

Разрешение коллизий при помощи цепочек.

Каждая ячейка [math]i[/math] массива [math]H[/math] содержит указатель на начало списка всех элементов, хеш-код которых равен [math]i[/math] , либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.

В зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, то мы используем список, время вставки в который будет в худшем случае равна [math]O(1)[/math] . Иначе мы проверяем есть ли в списке данный элемент, а потом в случае его отсутствия мы его добавляем. В таком случае вставка элемента в худшем случае будет выполнена за [math]O(n)[/math]

Время работы поиска в наихудшем случае пропорционально длине списка, а если все [math]n[/math] ключей захешировались в одну и ту же ячейку (создав список длиной [math]n[/math] ) время поиска будет равно [math]\Theta(n)[/math] плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех [math]n[/math] элементов.

Удаления элемента может быть выполнено за [math]O(1)[/math] , как и вставка, при использовании двухсвязного списка.

Линейное разрешение коллизий

Пример хеш-таблицы с открытой адресацией и линейным пробированием.

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

Стратегии поиска

Последовательный поиск

При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+1, i+2, i+3[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.

Линейный поиск

Выбираем шаг [math]q[/math] . При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+(1 \cdot q), i+(2 \cdot q), i+(3 \cdot q)[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент. По сути последовательный поиск — частный случай линейного, где [math]q=1[/math] .

Квадратичный поиск

Шаг [math]q[/math] не фиксирован, а изменяется квадратично: [math]q = 1,4,9,16. [/math] . Соответственно при попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math] i+1, i+4, i+9[/math] и так далее, пока не найдём свободную ячейку.

Проверка наличия элемента в таблице

Проверка осуществляется аналогично добавлению: мы проверяем ячейку [math]i[/math] и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.

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

Проблемы данных стратегий

Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров — последовательностей занятых ячеек.

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

Удаление элемента без пометок

Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на [math]q[/math] позиций назад. При этом:

• если в цепочке встречается элемент с другим хешем, то он должен остаться на своём месте (такая ситуация может возникнуть если оставшаяся часть цепочки была добавлена позже этого элемента)
• в цепочке не должно оставаться «дырок», тогда любой элемент с данным хешем будет доступен из начала цепи

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

function delete(Item i): j = i + q while table[j] == null or table[j].key != table[i].key if table[j] == null table[i] = null return j += q table[i] = table[j] delete(j)

Хеш-таблицу считаем зацикленной

Асимптотически время работы [math]\mathrm[/math] и [math]\mathrm[/math] совпадают

Вариант с зацикливанием мы не рассматриваем, поскольку если [math]q[/math] взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных позиций

Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.

• В редактируемой цепи не остаётся дырок

Докажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце [math]\mathrm[/math] (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.

• Элементы, которые уже на своих местах, не должны быть сдвинуты.

• В других цепочках не появятся дыры

Противное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на [math]q[/math] позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно.

Двойное хеширование

Двойное хеширование (англ. double hashing) — метод борьбы с коллизиями, возникающими при открытой адресации, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.

Принцип двойного хеширования

При двойном хешировании используются две независимые хеш-функции [math] h_1(k) [/math] и [math] h_2(k) [/math] . Пусть [math] k [/math] — это наш ключ, [math] m [/math] — размер нашей таблицы, [math]n \bmod m [/math] — остаток от деления [math] n [/math] на [math] m [/math] , тогда сначала исследуется ячейка с адресом [math] h_1(k) [/math] , если она уже занята, то рассматривается [math] (h_1(k) + h_2(k)) \bmod m [/math] , затем [math] (h_1(k) + 2 \cdot h_2(k)) \bmod m [/math] и так далее. В общем случае идёт проверка последовательности ячеек [math] (h_1(k) + i \cdot h_2(k)) \bmod m [/math] где [math] i = (0, 1, \; . \;, m — 1) [/math]

Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за [math]O(1)[/math] , в худшем — за [math]O(m)[/math] , что не отличается от обычного линейного разрешения коллизий. Однако в среднем, при грамотном выборе хеш-функций, двойное хеширование будет выдавать лучшие результаты, за счёт того, что вероятность совпадения значений сразу двух независимых хеш-функций ниже, чем одной.

[math]\forall x \neq y \; \exists h_1,h_2 : p(h_1(x)=h_1(y))\gt p((h_1(x)=h_1(y)) \land (h_2(x)=h_2(y)))[/math]

Выбор хеш-функций

[math] h_1 [/math] может быть обычной хеш-функцией. Однако чтобы последовательность исследования могла охватить всю таблицу, [math] h_2 [/math] должна возвращать значения:

• не равные [math] 0 [/math]
• независимые от [math] h_1 [/math]
• взаимно простые с величиной хеш-таблицы

Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а [math] h_2 [/math] возвращает натуральные числа, меньшие [math] m [/math] . Второй — размер таблицы является степенью двойки, а [math] h_2 [/math] возвращает нечетные значения.

Например, если размер таблицы равен [math] m [/math] , то в качестве [math] h_2 [/math] можно использовать функцию вида [math] h_2(k) = k \bmod (m-1) + 1 [/math]

Вставка при двойном хешировании

Пример

Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:

[math] h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod 13 [/math]

[math] h_1(k) = k \bmod 13 [/math]

[math] h_2(k) = 1 + k \bmod 11 [/math]

Мы хотим вставить ключ 14. Изначально [math] i = 0 [/math] . Тогда [math] h(14,0) = (h_1(14) + 0\cdot h_2(14)) \bmod 13 = 1 [/math] . Но ячейка с индексом 1 занята, поэтому увеличиваем [math] i [/math] на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При [math] i = 2 [/math] получаем [math] h(14,2) = (h_1(14) + 2\cdot h_2(14)) \bmod 13 = 9 [/math] . Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Таким образом, основная особенность двойного хеширования состоит в том, что при различных [math] k [/math] пара [math] (h_1(k),h_2(k)) [/math] дает различные последовательности ячеек для исследования.

Простая реализация

Пусть у нас есть некоторый объект [math] item [/math] , в котором определено поле [math] key [/math] , от которого можно вычислить хеш-функции [math] h_1(key)[/math] и [math] h_2(key) [/math]

Так же у нас есть таблица [math] table [/math] величиной [math] m [/math] , состоящая из объектов типа [math] item [/math] .

function add(Item item): x = h1(item.key) y = h2(item.key) for (i = 0..m) if table[x] == null table[x] = item return x = (x + y) mod m table.resize()// ошибка, требуется увеличить размер таблицы

Item search(Item key): x = h1(key) y = h2(key) for (i = 0..m) if table[x] != null if table[x].key == key return table[x] else return null x = (x + y) mod m return null 

Реализация с удалением

Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив [math]deleted[/math] типов [math]bool[/math] , равный по величине массиву [math]table[/math] . Теперь при удалении мы просто будем помечать наш объект как удалённый, а при добавлении как не удалённый и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.

function add(Item item): x = h1(item.key) y = h2(item.key) for (i = 0..m) if table[x] == null or deleted[x] table[x] = item deleted[x] = false return x = (x + y) mod m table.resize()// ошибка, требуется увеличить размер таблицы

Item search(Item key): x = h1(key) y = h2(key) for (i = 0..m) if table[x] != null if table[x].key == key and !deleted[x] return table[x] else return null x = (x + y) mod m return null 

function remove(Item key): x = h1(key) y = h2(key) for (i = 0..m) if table[x] != null if table[x].key == key deleted[x] = true else return x = (x + y) mod m

Альтернативная реализация метода цепочек

В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию сбалансированного дерева. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан линейный порядок. То есть при использовании данныx типа [math]\mathbf[/math] или [math]\mathbf[/math] имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с [math]O(n)[/math] до [math]O(\log(n))[/math] . Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.

См. также

• Хеширование
• Хеширование кукушки
• Идеальное хеширование

Источники информации

• Бакнелл Дж. М. «Фундаментальные алгоритмы и структуры данных в Delphi», 2003
• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом «Вильямс», 2010.— Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
• Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» — «Вильямс», 2007 г.— ISBN 0-201-89685-0
• Седжвик Р. «Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск», 2003
• Handle Frequent HashMap Collisions with Balanced Trees
• Wikipedia — Double_hashing
• Разрешение коллизий
• Пример хеш таблицы
• Пример хеш таблицы с двойным хешированием

Часть первая ответника, Java

Не так давно моя хорошая подруга Веселина Зацепина опубликовала список вопросов, которые часто задают на собеседованиях на должность разработчика приложений для платформы Android. Это благородное, очень правильное начинание. Наличие списка вопросов даёт уже даёт толику уверенности перед собеседованием.
Сегодня мне хотелось бы опубликовать первую часть списка ответов на эти часто задаваемые вопросы. Разумеется, ответы эти краткие: предназначены только чтобы зазубрить и озвучить текст. Да, просто текст. Не для обучения или понимания; Просто чтобы сопоставить множество текстовых вопросов и текстовых ответов. Получится карта, из которой нужно будет лишь выдавать по ключу соответствующие значения.

Первым блоком идут вопросы о языке программирования Java.

1. Модификаторы доступа Java (в порядке от private до public):

private — ограничивает видимость данных и методов пределами одного класса.

protected — Поля и методы, обозначенные модификатором доступа protected, будут видны в пределах всех классов, находящихся в том же пакете, что и наш и в пределах всех классов-наследников нашего класса.

default (package visible) — default или, как его еще называют, package visible . Он не обозначается ключевым словом, поскольку установлен в Java по умолчанию для всех полей и методов. Действует также, как и protected, за исключением наследования.

public — Не накладывает никаких ограничений на доступ; предназначаются для конечного пользователя.

2. Реализация «кучи» (где хранятся объекты):

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

Эта область памяти разбита на несколько более мелких частей, называемых поколениями:

Young Generation — область где размещаются недавно созданные объекты. Когда она заполняется, происходит быстрая сборка мусора.

Old (Tenured) Generation — здесь хранятся долгоживущие объекты. Когда объекты из Young Generation достигают определенного порога “возраста”, они перемещаются в Old Generation.

Permanent Generation — эта область содержит метаинформацию о классах и методах приложения, но начиная с Java 8 данная область памяти была упразднена.

Помимо рассмотренных ранее, куча имеет следующие ключевые особенности:Когда эта область памяти полностью заполняется, Java бросает java.lang.OutOfMemoryError Доступ к ней медленнее, чем к стеку. Эта память, в отличие от стека, автоматически не освобождается. Для сбора неиспользуемых объектов используется сборщик мусора. В отличие от стека, куча не является потокобезопасной и ее необходимо контролировать, правильно синхронизируя код.

3. Где и как используются методы equals() и hashcode():

Метод equals() являются ли два объекта одного происхождения логически равными. Создатель класса сам определяет характеристики, по которым проверяется равенство объектов этого класса.

Объекты должны быть экземплярами одного класса и не должны быть null. Переопределяя метод equals(), обязательно соблюдение этих требований:

Рефлексивность: Любой объект должен быть equals() самому себе.

Симметричность: Если a.equals(b) == true, то и b.equals(a) должно возвращать true.

Транзитивность: Если два объекта равны какому-то третьему объекту, значит, они должны быть равны друг и другу. Если a.equals(b) == true и a.equals(c) == true, значит проверка b.equals(c) тоже должна возвращать true.

Постоянность: Результаты работы equals() должны меняться только при изменении входящих в него полей. Если данные двух объектов не менялись, результаты проверки на equals() должны быть всегда одинаковыми.

Сравнение с null для любого объекта a.equals(null) должно возвращать false.

Метод hashCode() возвращает для любого объекта 32-битное число типа int. Если два объекта равны (т.е. метод equals() возвращает true), у них должен быть одинаковый хэш-код. Проверка по hashCode() должна идти первой для повышения быстродействия. Если метод hashCode() вызывается несколько раз на одном и том же объекте, каждый раз он должен возвращать одно и то же число. Одинаковый хэш-код может быть у двух разных объектов. Методы equals и hashCode необходимо переопределять вместе.

4. Что будет, если не переопределить метод hashcode():

Тогда с точки зрения метода equals два объекта будут логически равны, в то время как с точки зрения метода hashCode они не будут иметь ничего общего.

5. Реализация HashMap:

HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Сначала ключ проверяется на равенство с null. Если это проверка вернула true, будет вызван метод putForNullKey(value). Далее генерируется хэш на основе ключа. Для генерации используется метод hash(hashCode), в который передается key.hashCode(). С помощью метода indexFor(hash, tableLength), определяется позиция в массиве, куда будет помещен элемент. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Хэш и ключ нового элемента поочередно сравниваются с хэшами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается. Если же предыдущий шаг не выявил совпадений, будет вызван метод addEntry(hash, key, value, index) для добавления нового элемента.

6. Как разрешается коллизия в HashMap (метод цепочек или открытая адресация):

Разрешение коллизий при помощи цепочек. Каждая ячейка массива H является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.

7. Виды исключений в Java:

Unchecked(Error, RunTimeException); Checked(Exception)

8. Виды коллекций Java (перечисляете всё, что знаете):

List, Set, Queue, Deque, Map.

9. Типы ссылок Java и где используются, в порядке убывания жёсткости:

Сильные, они же обычные, нужны для указания на объекты, которые должны обязательно оставаться в памяти всё то время, что эти ссылки на него существуют. Если не складывается, получите OutOfMemoryError.

Мягкие ссылки полезны для кэшей, чувствительных к доступному объёму оперативной памяти. Объекты по ним могут зачиститься, но только в случае необходимости. Например, если нужно насоздавать ещё объектов с сильными ссылками, а уже негде, лучше освободить кэш и замедлить работу, чем уронить процесс напрочь.

Слабые ссылки полезны для сопоставления объектов чему-нибудь без удерживания их от зачистки когда они больше не нужны (а-ля Map>). На возможность зачистки они не влияют вообще никак, слабые ссылки будут очищены при очередном запуске сборщика.

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

10. Способы синхронизации Java:

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

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

Блокировка уровня класса предотвращает ввод нескольких потоков в синхронизированный блок в любом из всех доступных экземпляров во время выполнения. Это означает, что если во время выполнения есть 100 экземпляров DemoClass, то только один поток сможет выполнить demoMethod() в любом из экземпляров одновременно, а все остальные экземпляры будут заблокированы для других потоков.

11. Volatile — что это:

Запрещает помещать значение переменной в кэш. Ключевое слово volatile указывается для поля для того, чтобы указать компилятору, что все операции присвоения этой переменной и все операции чтения из неё должны быть атомарными. Более того, присвоение значения этой переменной имеет связь happens-before (произошло-до) для последующих чтений из этой переменной для любых потоков, то есть после присвоения нового значения переменной все потоки увидят это новое значение.

Дело в том, что Java позволяет потокам в целях производительности сохранять локальные копии переменной для каждого потока, который её использует (например в кешах или регистрах процессора). В таком случае после записи другим потоком нового значения в исходную переменную, первый поток будет видеть свою локальную копию со старым значением.

Использование ключевого слова volatile гарантирует, что все потоки всегда будут использовать общее, исходное значение, и они будут видеть изменения этого исходного значения другими потоками сразу же. Аналогично все изменения переменных, произошедшие внутри sychronized-методов и synchronized-блоков, а также блоков с другими блокировками вроде реализаций интерфейса java.util.concurrent.locks.Lock после выхода из блокировки будут гарантировано видны любым другим потокам после взятия блокировки над тем же самым объектом, но если более сложные блокировки не нужны, то можно использовать volatile.

12. StringBuilder vs String:

Благодаря неизменности, хэшкод экземпляра класса String кэшируется. Его не нужно вычислять каждый раз, потому что значения полей объекта никогда не изменятся после его создания. Это дает высокую производительность при использовании данного класса в качестве ключа для HashMap.

StringBuilder — изменяемый класс, поэтому при работе с ним не возникает такого же количества мусора в памяти, как со String. Поэтому если над строками проводится много модификаций, лучше использовать StringBuilder.

13. Назовите синхронизированную версию HashMap (Hashtable, но устарела):

SynchronizedMap и ConcurrentHashMap.

Методы SynchronizedMap удерживают блокировку на объекте, в то время как ConcurrentHashMap есть понятие «чередование блокировок», когда вместо блокировок удерживаются блоки содержимого. Таким образом улучшается масштабируемость и производительность.

14. Реализация ArrayList в Java (на базе массива):

Класс ArrayList реализует интерфейс List и может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null. Внутри у него находится массив, в котором и хранятся элементы. УArrayListʼa есть специальный механизм по работе с ним: Когда этот внутренний массив заполняется, ArrayList создает внутри себя новый массив. Его размер = (размер старого массива * 1,5) +1. Все данные копируются из старого массива в новый Старый массив удаляется сборщиком мусора.

15. Модификатор final в Java — где используется и что даёт:

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

Кроме того, хотелось бы добавить вопрос из своего опыта:

Какие методы имеются у класса Object?

public String toString() — Возвращает строковое представление объекта.

public native int hashCode() и public boolean equals(Object obj) — Пара методов, которые используются для сравнения объектов.

public final native Class getClass() — Возвращает специальный объект, который описывает текущий класс.

public final native void notify(),
public final native void notifyAll(),
public final native void wait(long timeout),
public final void wait(long timeout, intnanos),
public final void wait() — Методы для контроля доступа к объекту из различных нитей. Управление синхронизацией нитей.

protected void finalize() — Метод позволяет «освободить» родные не-Java ресурсы: закрыть файлы, потоки и т.д.

protected native Object clone() — Метод позволяет клонировать объект: создает дубликат объекта.

Все ответы собраны из следующих источников: