1. Что такое дженерики
 Скачать 0.84 Mb.
|
|
new ArrayDeque<>(); stack.push(1); stack.push(2); stack.push(3); while (!stack.isEmpty()) { System.out.println(stack.pop()); } Результат: 3 2 1 Выводы На основании рассмотренных нами интерфейсов и реализаций можно сделать вывод, что для самой простой реализации очереди Queue следует выбрать LinkedList. Eсли требуется как-то сортировать элементы внутри очереди, то подойдёт PriorityQueue. Если же нам нужна функциональность стека, то надо использовать интерфейс Deque и одну из его реализаций: LinkedList или ArrayDeque 27. Какая коллекция реализует FIFO? Queue 28. Какая коллекция реализует LIFO? Stack 29. Оцените количество памяти на хранение одного примитива типа byte в LinkedList? Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные. private static class Node E item; Node Node //... } Для 32-битных систем каждая ссылка занимает 32 бита (4 байта). Сам объект (заголовок) вложенного класса Node занимает 8 байт. 4 + 4 + 4 + 8 = 20 байт, а т.к. размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типа byte занимает 1 байт памяти, но в JCF примитивы упаковываются: объект типа Byte занимает в памяти 16 байт (8 байт на заголовок объекта, 1 байт на поле типа byte и 7 байт для кратности 8). Также напомню, что значения от -128 до 127 кэшируются и для них новые объекты каждый раз не создаются. Таким образом, в x32 JVM 24 байта тратятся на хранение одного элемента в списке и 16 байт - на хранение упакованного объекта типа Byte. Итого 40 байт. Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны: 8 + 8 + 8 + 16 = 40байт и 24 байта (объект). Итого 64 байта. 30. Оцените количество памяти на хранение одного примитива типа byte в ArrayList? ArrayList основан на массиве, для примитивных типов данных осуществляется автоматическая упаковка значения, поэтому 16 байт тратится на хранение упакованного объекта и 4 байта (8 для x64) - на хранение ссылки на этот объект в самой структуре данных. Таким образом, в x32 JVM 4 байта используются на хранение одного элемента и 16 байт - на хранение упакованного объекта типа Byte. Для x64 - 8 байт и 24 байта соотвтетсвенно. х32=20байт х64=32байт 31. Какие существуют реализации Map? Hashtable — реализация такой структуры данных, как хэш-таблица. Она не позволяет использовать null в качестве значения или ключа. Эта коллекция была реализована раньше, чем Java Collection Framework, но в последствии была включена в его состав. Как и другие коллекции из Java 1.0, Hashtable является синхронизированной (почти все методы помечены как synchronized). Из-за этой особенности у неё имеются существенные проблемы с производительностью и, начиная с Java 1.2, в большинстве случаев рекомендуется использовать другие реализации интерфейса Map ввиду отсутствия у них синхронизации. HashMap — коллекция является альтернативой Hashtable. Двумя основными отличиями от Hashtable являются то, что HashMap не синхронизирована и HashMap позволяет использовать null как в качестве ключа, так и значения. Так же как и Hashtable, данная коллекция не является упорядоченной: порядок хранения элементов зависит от хэш-функции. Добавление элемента выполняется за константное время O(1), но время удаления, получения зависит от распределения хэш-функции. В идеале является константным, но может быть и линейным O(n). LinkedHashMap — это упорядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap, порядок итерирования равен порядку добавления элементов. Данная особенность достигается благодаря двунаправленным связям между элементами (аналогично LinkedList). Но это преимущество имеет также и недостаток — увеличение памяти, которое занимет коллекция. TreeMap — реализация Map основанная на красно-чёрных деревьях. Как и LinkedHashMap является упорядоченной. По-умолчанию, коллекция сортируется по ключам с использованием принципа "natural ordering", но это поведение может быть настроено под конкретную задачу при помощи объекта Comparator, который указывается в качестве параметра при создании объекта TreeMap. WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references. Другими словами, Garbage Collector автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элеметна нет жёстких ссылок. HashMap LinkedHashMap TreeMap Порядок хранения данных Случайный. Нет гарантий, что порядок сохранится на протяжении времени В порядке добавления В порядке возрастания или исходя из заданного компаратора Время доступа к элементам O(1) O(1) O(log(n)) Имплементированные интерфейсы Map Map NavigableMap SortedMap Map Имплементация на основе структуры данных Корзины (buckets) Корзины (buckets) Красно-чёрное дерево (Red-Black Tree) Возможность работы с null- ключем Можно Можно Можно, если не используется компаратор Потокобезопасна Нет Нет Нет O(1) можно прочитать как «сложность порядка 1» (order 1), или «алгоритм выполняется за постоянное/константное время» (constant time).O(1) алгоритмы самые эффективные. O(n), или «сложность порядка n (order n)». Здесь нужно перебрать все элементы, т.е. операция на каждый элемент. Чем больше массив, тем больше операций. O(n^2) Алгоритмы с вложенными циклами по той же коллекции всегда O(n^2). Итерирование массива это O(n). У нас есть вложенный цикл, для каждого элемента мы еще раз итерируем — т.е. O(n^2) или «сложность порядка n квадрат». O(log n) Т.е. в худшем случае делаем столько операций, сколько раз можем разделить массив на две части. Например, сколько раз мы можем разделить на две части массив из 4 элементов? 2 раза. А массив из 8 элементов? 3 раза. Т.е. кол-во делений/операций = log2(n) (где n кол-во элементов массива). В алгоритме «бинарный поиск» на каждом шаге мы делим массив на две части. 32. Как устроена HashMap, сложность основных операций? (Расскажите про принцип корзин) HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек. Особенности: — Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки; — Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии. Среднее же время работы будет Θ(1 + α), где α — коэффициент загрузки. В самом худшем случае, время выполнения может составить Θ(n) (все элементы в одной цепочке); — Ключи и значения могут быть любых типов, в том числе и null. Для хранения примитивных типов используются соответствующие классы-оберки; — Не синхронизирован. Создание объекта: Map Новоявленный объект hashmap, содержит ряд свойств: - table — Массив типа Entry[], который является хранилищем ссылок на списки (цепочки) значений; - loadFactor — Коэффициент загрузки. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных; - threshold — Предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor); size — Количество элементов HashMap-а; Добавление элементов в объект HasMap: - Сначала ключ проверяется на равенство null. Если это проверка вернула true, будет вызван метод putForNullKey(value) - Далее генерируется хэш на основе ключа. Для генерации используется метод hash(hashCode), в который передается key.hashCode() - С помощью метода indexFor(hash, tableLength), определяется позиция в массиве, куда будет помещен элемент. - Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Хэш и ключ нового элемента поочередно сравниваются с хэшами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается. - Если же предыдущий шаг не выявил совпадений, будет вызван метод addEntry(hash, key, value, index) для добавления нового элемента. Разрешение коллизий с помощью метода цепочек: Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов с помощью методов resize(capacity) и transfer(newTable). Метод transfer() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву. У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается. И если в ArrayList предусмотрен метод trimToSize(), то в HashMap таких методов нет. HashMap имеет встроенные итераторы, такие, что вы можете получить список всех ключей keySet(), всех значений values() или же все пары ключ/значение entrySet(). Ниже представлены некоторые варианты для перебора элементов: // 1. все ключи-значения for (Map.Entry System.out.println(entry.getKey() + " = " + entry.getValue()); // 2. все ключи for (String key: hashmap.keySet()) System.out.println(hashmap.get(key)); // 3. получить все пары ключ/значений Iterator System.out.println(itr.next()); 33. Что такое LinkedHashMap? LinkedHashMap - у порядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap, порядок итерирования равен порядку добавления элементов. Данная структура может слегка уступать по производительности родительскому HashMap, при этом время выполнения операций add(), contains(), remove() остается константой — O(1). Понадобится чуть больше места в памяти для хранения элементов и их связей, но это совсем небольшая плата за дополнительные фишечки. Он также принимает нулевой ключ, а также нулевые значения. LinkedHashMap не синхронизирована. Вообще, из-за того что всю основную работу на себя берет родительский класс, серьезных отличий в реализации HashMap и LinkedHashMap не много. Можно упомянуть о парочке мелких: Методы transfer() и containsValue() устроены чуть проще из-за наличия двунаправленной связи между элементами; В классе LinkedHashMap.Entry реализованы методы recordRemoval() и recordAccess() (тот самый, который помещает элемент в конец при accessOrder = true). В HashMap оба этих метода пустые. Map linkedHashMap.put(1, "obj1"); linkedHashMap.put(15, "obj15"); Только что созданный объект linkedHashMap, помимо свойств унаследованных от HashMap (такие как table, loadFactor, threshold, size, entrySet и т.п.), так же содержит два доп. свойства: header — «голова» двусвязного списка. При инициализации указывает сам на себя; accessOrder — указывает каким образом будет осуществляться доступ к элементам при использовании итератора. При значении true — по порядку последнего доступа. При значении false доступ осуществляется в том порядке, в каком элементы были вставлены. 34. Как устроена TreeMap, сложность основных операций? Класс TreeMap Время доступа и извлечения элементов достаточно мало, что делает класс TreeMap блестящим выбором для хранения больших объемов отсортированной информации, которая должна быть быстро найдена. Класс TreeMap имеет следующие конструкторы: - TreeMap(): создает пустое отображение в виде дерева - TreeMap(Map map): создает дерево, в которое добавляет все элементы из отображения map - TreeMap(SortedMap - TreeMap(Comparator comparator): создает пустое дерево, где все добавляемые элементы впоследствии будут отсортированы компаратором. Кроме собственно методов интерфейса Map класс TreeMap реализует методы интерфейса NavigableMap. Например, мы можем получить все объекты до или после определенного ключа с помощью методов headMap и tailMap. Также мы можем получить первый и последний элементы и провести ряд дополнительных манипуляций с объектами SortedMap — интерфейс, который расширяет Map и добавляет методы, актуальные для отсортированного набора данных: • firstKey(): возвращает ключ первого элемента мапы; • lastKey(): возвращает ключ последнего элемента; • headMap(K end): возвращает мапу, которая содержит все элементы текущей, от начала до элемента с ключом end; • tailMap(K start): возвращает мапу, которая содержит все элементы текущей, начиная с элемента start и до конца; • subMap(K start, K end): возвращает мапу, которая содержит все элементы текущей,начиная с элемента start и до элемента с ключом end. NavigableMap — интерфейс, который расширяет SortedMap и добавляет методы для навигации между элементами мапы: • firstEntry(): возвращает первый пару “ключ-значение”; • lastEntry(): возвращает последнюю пару “ключ-значение”; • pollFirstEntry(): возвращает и удаляет первую пару; • pollLastEntry(): возвращает и удаляет последнюю пару; • ceilingKey(K obj): возвращает наименьший ключ k, который больше или равен ключу obj. Если такого ключа нет, возвращает null; • floorKey(K obj): возвращает самый большой ключ k, который меньше или равен ключу obj. Если такого ключа нет, возвращает null; • lowerKey(K obj): возвращает наибольший ключ k, который меньше ключа obj. Если такого ключа нет, возвращает null; • higherKey(K obj): возвращает наименьший ключ k, который больше ключа obj. Если такого ключа нет, возвращает null; • ceilingEntry(K obj): аналогичен методу ceilingKey(K obj), только возвращает пару “ключ-значение” (или null); • floorEntry(K obj): аналогичен методу floorKey(K obj), только возвращает пару “ключ-значение” (или null); • lowerEntry(K obj): аналогичен методу lowerKey(K obj), только возвращает пару “ключ-значение” (или null); • higherEntry(K obj): аналогичен методу higherKey(K obj), только возвращает пару “ключ-значение” (или null); • descendingKeySet(): возвращает NavigableSet, содержащий все ключи, отсортированные в обратном порядке; • descendingMap(): возвращает NavigableMap, содержащую все пары, отсортированные в обратном порядке; • navigableKeySet(): возвращает объект NavigableSet, содержащий все ключи в порядке хранения; • headMap(K upperBound, boolean incl): возвращает мапу, которая содержит пары от начала и до элемента upperBound. Аргумент incl указывает, нужно ли включать элемент upperBound в возвращаемую мапу; • tailMap(K lowerBound, boolean incl): функционал похож на предыдущий метод, только возвращаются пары от lowerBound и до конца; • subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): как и в предыдущих методах, возвращаются пары от lowerBound и до upperBound, аргументы lowIncl и highIncl указывают, включать ли граничные элементы в новую мапу. 35. Что такое WeakHashMap? является реализацией интерфейса Map на основе хеш-таблиц, с ключами из WeakReference тип. Запись в WeakHashMap будет автоматически удалена, если ее ключ больше не используется в обычном режиме. Это означает, что не существует ни одной ссылки, указывающая на этот ключ. Когда процесс сборки мусора (GC) отбрасывает ключ, его запись эффективно удаляется с карты, поэтому этот класс ведет себя несколько иначе, чем другие реализации Map. Применение – реализация простого кэша. 36. Как работает HashMap при попытке сохранить в него два элемента по ключам с одинаковым hashCode(), но для которых equals() == false? По значению hashCode() вычисляется индекс ячейки массива, в список которой этот элемент будет добавлен. Перед добавлением осуществляется проверка на наличие элементов в этой ячейке. Если элементы с таким hashCode() уже присутствует, но их equals() методы не равны, то элемент будет добавлен в конец списка. 37. Что будет, если мы кладем в HashMap ключ, у которого equals и hashCode определены некорректно? Некорректно equals и hashcode - не найдем корзину и не найдем элемент Если некорректно equals – как минимум найдем корзину хэш-таблицы, в которой объект будет лежать, Если некорректно hascode - помещая некий объект в хэш-таблицу, мы рискуем не получить его обратно по ключу 38. Возможна ли ситуация, когда HashMap выродится в список даже с ключами имеющими разные hashCode()? Это возможно в случае, если метод indexFor(hash, tableLength), определяющий номер корзины будет возвращать одинаковые значения 39. Почему нельзя использовать byte[] в качестве ключа в HashMap? Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняется сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом- массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента 40. Будет ли работать HashMap, если все добавляемые ключи будут иметь одинаковый hashCode()? Да, будет, но в этом случае HashMap вырождается в связный список и теряет свои преимущества |