Документ Microsoft Word (2). Что такое generic и для чего они нужны
 Скачать 82.45 Kb.
|
|
Какое начальное количество корзин в HashMap? В конструкторе по умолчанию - 16, используя конструкторы с параметрами можно задавать произвольное начальное количество корзин. Какова оценка временной сложности операций над элементами из HashMap? Гарантирует ли HashMap указанную сложность выборки элемента? В общем случае операции добавления, поиска и удаления элементов занимают константное время. Данная сложность не гарантируется, т.к. если хэш-функция распределяет элементы по корзинам равномерно, временная сложность станет не хуже Логарифмического времени O(log(N)), а в случае, когда хэш-функция постоянно возвращает одно и то же значение, HashMap превратится в связный список со сложностью О(n). Возможна ли ситуация, когда HashMap выродится в список даже с ключами имеющими разные hashCode()? Это возможно в случае, если метод, определяющий номер корзины будет возвращать одинаковые значения. В каком случае может быть потерян элемент в HashMap? Допустим, в качестве ключа используется не примитив, а объект с несколькими полями. После добавления элемента в HashMap у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хэш-кода. В результате при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот equals уже не найдет указанный ключ в списке элементов. Тем не менее, даже если equals реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хэш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет в совершенно другую корзину и тогда уже потеряется совсем. Почему нельзя использовать byte[] в качестве ключа в HashMap? Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняется сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента. Какова роль equals() и hashCode() в HashMap? hashCode позволяет определить корзину для поиска элемента, а equals используется для сравнения ключей элементов в списке корзины и искомого ключа. Каково максимальное число значений hashCode()? Число значений следует из сигнатуры int hashCode() и равно диапазону типа int — 232. Какое худшее время работы метода get(key) для ключа, который есть в HashMap? O(N). Худший случай - это поиск ключа в HashMap, вырожденного в список по причине совпадения ключей по hashCode() и для выяснения хранится ли элемент с определённым ключом может потребоваться перебор всего списка. Но начиная с Java 8, после определенного числа элементов в списке, связный список преобразовывается в красно-черное дерево и сложность выборки, даже в случае плохой хеш-функции, не хуже логарифмической O(log(N)) Сколько переходов происходит в момент вызова HashMap.get(key) по ключу, который есть в таблице? ключ равен null: 1 - выполняется единственный метод getForNullKey(). любой ключ отличный от null: 4 - вычисление хэш-кода ключа; определение номера корзины; поиск значения; возврат значения. Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap? Один новый объект статического вложенного класса Entry Как и когда происходит увеличение количества корзин в HashMap? Помимо capacity у HashMap есть еще поле loadFactor, на основании которого, вычисляется предельное количество занятых корзин capacity * loadFactor. По умолчанию loadFactor = 0.75. По достижению предельного значения, число корзин увеличивается в 2 раза и для всех хранимых элементов вычисляется новое «местоположение» с учетом нового числа корзин. Объясните смысл параметров в конструкторе HashMap(int initialCapacity, float loadFactor). initialCapacity - исходный размер HashMap, количество корзин в хэш-таблице в момент её создания. loadFactor - коэффициент заполнения HashMap, при превышении которого происходит увеличение количества корзин и автоматическое перехэширование. Равен отношению числа уже хранимых элементов в таблице к её размеру. Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hashCode()? Да, будет, но в этом случае HashMap вырождается в связный список и теряет свои преимущества. Как перебрать все ключи Map? Использовать метод keySet(), который возвращает множество Set Как перебрать все значения Map? Использовать метод values(), который возвращает коллекцию Collection Как перебрать все пары «ключ-значение» в Map? Использовать метод entrySet(), который возвращает множество Set В чем отличия TreeSet и HashSet? TreeSet обеспечивает упорядоченно хранение элементов в виде красно-черного дерева. Сложность выполнения основных операций не хуже O(log(N)) (Логарифмическое время). HashSet использует для хранения элементов такой же подход, что и HashMap, за тем отличием, что в HashSet в качестве ключа и значения выступает сам элемент, кроме того, HashSet не поддерживает упорядоченное хранение элементов и обеспечивает временную сложность выполнения операций аналогично HashMap. Что будет, если добавлять элементы в TreeSet по возрастанию? В основе TreeSet лежит красно-черное дерево, которое умеет само себя балансировать. В итоге, TreeSet все равно в каком порядке вы добавляете в него элементы, преимущества этой структуры данных будут сохраняться. Чем LinkedHashSet отличается от HashSet? LinkedHashSet отличается от HashSet только тем, что в его основе лежит LinkedHashMap вместо HashMap. Благодаря этому порядок элементов при обходе коллекции является идентичным порядку добавления элементов (insertion-order). При добавлении элемента, который уже присутствует в LinkedHashSet (т.е. с одинаковым ключом), порядок обхода элементов не изменяется. Для Enum есть специальный класс java.util.EnumSet. Зачем? Чем авторов не устраивал HashSet или TreeSet? EnumSet - это реализация интерфейса Set для использования с перечислениями (Enum). В структуре данных хранятся объекты только одного типа Enum, указываемого при создании. Для хранения значений EnumSet использует массив битов (bit vector), - это позволяет получить высокую компактность и эффективность. Проход по EnumSet осуществляется согласно порядку объявления элементов перечисления. Все основные операции выполняются за O(1) и обычно (но негарантированно) быстрей аналогов из HashSet, а пакетные операции (bulk operations), такие как containsAll() и retainAll() выполняются даже гораздо быстрей. Помимо всего EnumSet предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров. Какие существуют способы перебирать элементы списка? Цикл с итератором Iterator while (iterator.hasNext()) { //iterator.next(); } Цикл for for (int i = 0; i < list.size(); i++) { //list.get(i); } Цикл while int i = 0; while (i < list.size()) { //list.get(i); i++; } «for-each» for (String element : list) { //element; } Каким образом можно получить синхронизированные объекты стандартных коллекций? С помощью статических методов synchronizedMap() и synchronizedList() класса Collections. Данные методы возвращают синхронизированный декоратор переданной коллекции. При этом все равно в случае обхода по коллекции требуется ручная синхронизация. Map m = Collections.synchronizedMap(new HashMap()); List l = Collections.synchronizedList(new ArrayList()); Начиная с Java 6 JCF был расширен специальными коллекциями, поддерживающими многопоточный доступ, такими как CopyOnWriteArrayList и ConcurrentHashMap. Как получить коллекцию только для чтения? При помощи: Collections.unmodifiableList(list); Collections.unmodifiableSet(set); Collections.unmodifiableMap(map). Эти методы принимают коллекцию в качестве параметра, и возвращают коллекцию только для чтения с теми же элементами внутри. Напишите однопоточную программу, которая заставляет коллекцию выбросить ConcurrentModificationException. public static void main(String[] args) { List list.add(1); list.add(2); list.add(3); for (Integer integer : list) { list.remove(1); } } Приведите пример, когда какая-либо коллекция выбрасывает UnsupportedOperationException. public static void main(String[] args) { List list.add(0); } Реализуйте симметрическую разность двух коллекций используя методы Collection (addAll(...), removeAll(...), retainAll(...)). Симметрическая разность двух коллекций - это множество элементов, одновременно не принадлежащих обоим исходным коллекциям. // Объединяем коллекции. Collection result.addAll(b); // Получаем пересечение коллекций. Collection intersection.retainAll(b); // Удаляем элементы, расположенные в обоих коллекциях. result.removeAll(intersection); return result; } Как, используя LinkedHashMap, сделать кэш c «invalidation policy»? Необходимо использовать LRU-алгоритм (Least Recently Used algorithm) и LinkedHashMap с access-order. В этом случае при обращении к элементу он будет перемещаться в конец списка, а наименее используемые элементы будут постепенно группироваться в начале списка. Так же в стандартной реализации LinkedHashMap есть метод removeEldestEntries(), который возвращает true, если текущий объект LinkedHashMap должен удалить наименее используемый элемент из коллекции при использовании методов put() и putAll(). public class LRUCache private static final int MAX_ENTRIES = 10; public LRUCache(int initialCapacity) { super(initialCapacity, 0.85f, true); } @Override protected boolean removeEldestEntry(Map.Entry return size() > MAX_ENTRIES; } } Стоит заметить, что LinkedHashMap не позволяет полностью реализовать LRU-алгоритм, поскольку при вставке уже имеющегося в коллекции элемента порядок итерации по элементам не меняется. Как одной строчкой скопировать элементы любой collection в массив? Object[] array = collection.toArray(); Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х? List Как одной строчкой преобразовать HashSet в ArrayList? ArrayList Как одной строчкой преобразовать ArrayList в HashSet? HashSet Сделайте HashSet из ключей HashMap. HashSet |