- Вопросы про методы
Equals,hashcodeи их связь сHashMap. - Вопросы про списки: какие есть, алгоритмическая сложность, какой брать для вставки в середину, в конец, в огурец.
- Перечислите методы класса
Object. - Что можно положить и достать из
List<? extends Number>, а что сList<? super Number>? Что такое ковариантность, контрвариантность, инвариантность? - Что внутри и как работают TreeSet/TreeMap? В чем идея Красно-черного дерева?
Контракт. Далее разговор переходит к устройству HashMap. Как устроена внутри? А происходит в случае возникновения коллизии? Назовите алгоритмические сложности поиска, чтения, удаления из элемента мапы. А что если ключ - это массив байтов? А может быть так, что мы положим элемент в мапу, а потом не найдем? Обсасывают бедную мапу со всех сторон. Самая популярная тема для обсуждения.
Контракт equals и hashcode:
- Для одного и того же объекта хэшкоды одинаковые.
- Если объекты равны по equals, то и хэшкоды одинаковые.
- Если же хэшкоды равны, то объекты могут быть не равны по equals (коллизия).
- Если хэшкоды разные, то и объекты разные.
В статье на Хабре это подробно разобрано, если кому-то покажется мало.
Про HashMap и вопросы по ним есть несколько отличных статей на Хабре (в картинках, с дополнениями из Java 8, а тут вопросы-ответы про коллекциям). Кроме того, можно посмотреть исходный код в вашей любимой IDE. Можете сделать себе конспект и повесить на стену :)
Вопросы про списки: какие есть, алгоритмическая сложность, какой брать для вставки в середину, в конец, в огурец.
По сути это вопрос про ArrayList vs LinkedList. Опять же, заезженная пластинка, разобранная на Хабре - вопросы-ответы про коллекциям, ArrayList в картинках, LinkedList в картинках, Что «под капотом» у LinkedList. Посмотреть исходники тоже полезно. Например, можно понтануться тем, что вставка в середину в ArrayList выполняется с помощью нативно реализованной функции System.arraycopy, поэтому не всё так плохо, как могло бы быть в этом случае.
Этот вопрос далее перетекает либо в обсуждение HashMap, либо в основы многопоточного программирования на Java.
Чтобы вы вдруг внезапно не забыли каких-то методов (как это сделал я :D), привожу вам список и ссылку на JavaDoc:
- clone
- equals
- finalize (Deprecated)
- getClass
- hashCode
- toString
- notify
- notifyAll
- wait
Также можно почитать, что там вообще есть в исходниках Object в статье на Хабре.
Что можно положить и достать из List<? extends Number>, а что с List<? super Number>? Что такое ковариантность, контрвариантность, инвариантность?
Тут речь пойдёт про PECS - Producer extends, Consumer super (Joshua Bloch, Effective Java). А также вариантность — перенос наследования исходных типов на производные от них типы (контейнеры, делегаты, обобщения).
Ковариантность (covariance) - перенос наследования исходных типов на производные от них типы в прямом порядке.
Переменной типа List<? extends T> разрешено присвоить экземпляр списка, параметризованного T или его подклассом, но не родительским классом. В список типа List<? extends T> нельзя добавить никакой объект (можно только null) - нельзя гарантировать какого именно типа экземпляр списка будет присвоен переменной, поэтому нельзя гарантировать, что добавляемый объект разрешён в таком списке. Однако, из списка можно прочитать объект и он будет типа T и экземпляром либо T, либо одного из подклассов T.
Соответственно, List<? extends Number> можно присвоить ArrayList<Number> или ArrayList<Integer>, но не ArrayList<Object>. Метод get возвращает Number, за которым может скрываться экземпляр Integer или другого наследника Number.
Массивы также ковариантны.
Переопределение методов, начиная с Java 5, ковариантно относительно типа результата и исключений.
List<?> аналогичен List<? extends Object> со всеми вытекающими.
Контрвариантность (contravariance) - перенос наследования исходных типов на производные от них типы в обратном порядке.
Переменной типа List<? super T> разрешено присвоить экземпляр списка, параметризованного T или его родительским классом, но не его подклассом. В список типа List<? super T> можно добавить экземпляр T или его подкласса, но нельзя добавить экземпляр родительских для T классов. Из такого списка с гарантией можно прочитать только Object, за которым может скрываться неизвестно какой его подкласс.
Соответственно, List<? super Number> можно присвоить либо ArrayList<Number>, либо ArrayList<Object>, но не список наследников Number(т.е. никаких ArrayList<Integer>). Можно добавить экземпляр Integer или Double (можно было бы Number, но он абстрактный), но нельзя - Object. Метод get возвращает Object - точнее сказать нельзя.
Инвариантность - наследование исходных типов не переносится на производные. Переменной типа List разрешено присвоить экземпляр списка, параметризованного только T. В список можно добавить экземпляр T или его подкласса. Список возвращает T, за которым может скрываться экземпляр его подкласса.
Соответственно, List<Number> можно присвоить ArrayList<Number>, но не ArrayList<Integer> или ArrayList<Object>. Можно добавить экземпляр Integer или Double (можно было бы Number, но он абстрактный), но нельзя - Object. Метод get возвращает Number, за которым может скрываться экземпляр Integer или другого наследника Number.
Подробнее:
- На Хабре: Погружаемся в Generics, Используем в API, изучаем вариантность в программировании
- Посмотреть доклад Александра Маторина Неочевидные Дженерики
- В одном из ответов на вопрос Generics FAQ
- Как ограничивается тип generic параметра?
- Что такое ковариантность и контравариантность?
- В одном из объяснений на StackOverflow: раз, два, три
- Ковариантность и контравариантность с точки зрения математики, теории категорий и программирования
- Ковариантность и контравариантность в Wikipedia
- Wildcards в официальном туториале Oracle
TreeMap - реализация NavigableMap, основанная на красно-чёрном дереве. Элементы отсортированы по ключам в натуральном порядке или с помощью Comparator, указанного при создании мапы, в зависимости от использовавшегося конструктора. Гарантирует логарифмическое время выполнения методов containsKey, get, put и remove.
TreeSet - реализация NavigableSet, основанная на TreeMap. Элементы отсортированы в натуральном порядке или с помощью Comparator, указанного при создании множества, в зависимости от использовавшегося конструктора. Гарантирует логарифмическое время выполнения методов add, contains и remove.
Обе коллекции НЕ synchronized и итератор по ним может выбросить ConcurrentModificationException.
Если в эти коллекции при использовании натурального порядка сортировки в качестве ключа попытаться положить null, то получим NullPointerException. В случае с компаратором поведение с null будет зависеть от реализации компаратора. До 7-й Java с добавлением null в TreeMap и TreeSet был баг.
Самая важная особенность красно-чёрного дерева в том, что оно умеет само себя балансировать, поэтому не важно в каком порядке будут добавляться в него элементы, преимущества этой структуры данных будут сохраняться. Сбалансированность достигается за счёт поддержания правил красно-чёрной раскраски вершин:
- Вершина может быть либо красной, либо чёрной и имеет двух потомков
- Красная вершина не может быть дочерней для красной вершины
- Количество чёрных вершин от корня до листа включительно одинаково для любого листа
- Корень дерева является чёрным
- Все листья — чёрные и не содержат данных
Подробнее:
- Статья про сбалансированные бинарные деревья на Хабре
- Java собеседование. Коллекции на Хабре
- Java TreeMap vs HashMap
- 10 TreeMap Java Interview Questions и TreeSet Interview Questions
- Internal Working of TreeMap in Java
- A Guide to TreeMap in Java и A Guide to TreeSet in Java на Bealdung
- Красно-черные деревья: коротко и ясно на Хабре
- Балансировка красно-чёрных деревьев — Три случая на Хабре
- Красно-чёрное дерево
- Визуализация красно-чёрного дерева. И ещё. А вот исходники