Коллекции. Потоки Байтовые потоки InputStream и OutputStream. Символьные потоки Reader и Writer
 Скачать 32.99 Kb.
|
|
Что вы знаете о коллекциях типа HashMap? HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек. Как устроен HashMap?(часть 1) Вычисляется хэш ключа. Если ключ null, хэш считается равным 0. Чтобы достичь лучшего распределения, результат вызова hashCode() «перемешивается»: его старшие биты XOR-ятся на младшие. Как устроен HashMap?(часть 2) Значения внутри хэш-таблицы хранятся в специальных структурах данных - нодах, в массиве. Из хэша высчитывается номер бакета - индекс для значения в этом массиве. Полученный хэш обрезается по текущей длине массива. Длина - всегда степень двойки, так что для скорости используется битовая операция & Как устроен HashMap?(часть 3) В бакете ищется нода. В ячейке массива лежит не просто одна нода, а связка всех нод, которые туда попали. Исполнение проходит по этой связке (цепочке или дереву), и ищет ноду с таким же ключом. Ключ сравнивается с имеющимися сначала на == (ссылке), затем на equals. Как устроен HashMap?(часть 4) Если нода найдена - её значение просто заменяется новым. Работа метода на этом завершается. Как устроен HashMap?(часть 5) Если ноды с таким же ключом в бакете пока нет - добавляемая пара ключ-значение запаковывается в новый объект типа Node, и прикрепляется к структуре существующих нод бакета. Ноды составляют структуру за счет того, что в ноде хранится ссылка на следующий элемент (для дерева - следующие элементы). Кроме самой пары и ссылок, чтобы потом не считать заново, записывается и хэш ключа. Как устроен HashMap?(часть 6) В случае, когда структурой была цепочка а не дерево, и длина цепочки превысила 7 элементов - происходит процедура treeification - превращение списка в самобалансирующееся дерево. В случае коллизии это ускоряет доступ к элементам на чтение с O(n) до O(log(n)). У comparable-ключей для балансировки используется их естественный порядок. Другие ключи балансируются по порядку имен их классов и значениям identityHashCode-ов. Для маленьких хэш-таблиц (< 64 бакетов) «одеревенение» заменяется увеличением (см. п.8). Как устроен HashMap?(часть 7) Если новая нода попала в пустую ячейку, заняла новый бакет - увеличивается счетчик структурных модификаций. Изменение этого счетчика сообщит всем итераторам контейнера, что при следующем обращении они должны выбросить ConcurrentModificationException. Как устроен HashMap?(часть 8) Когда количество занятых бакетов массива превысило пороговое (capacity * load factor), внутренний массив увеличивается вдвое, а для всего содержимого выполняется рехэш - все имеющиеся ноды перераспределяются по бакетам по тем же правилам, но уже с учетом нового размера. Чем отличается метод Put и Get для HashMap? Put вставляет новый элемент в ноду или перезаписывает имеющийся. Метод Get позволяет получить имеющуюся пару, тем же образом что и запись, только без добавления. Как решается коллизия HashMap? При совпадении хеш кода, объект сравнивается на равенство ссылок а затем по equals. Если Совпадение найдено то значение у ключа перезаписывается. Если не найдено, то создается новая нода и прикрепляется к структуре существующих нод бакета. Чем отличается Map от HashMap? Map это интерфейс, HashMap это реализация этого интерфейса. Условия перестроения в красно-черное дерево (одеревенение) HashMap? Как только длина связного списка переходит превышает 7 элементов происходит процедура treeification - превращение списка в самобалансирующееся дерево. Для маленьких хэш-таблиц (< 64 бакетов) «одеревенение» заменяется увеличением. В чем отличие Map от Set? Map состоит из пар «ключ-значение». Ключи уникальны, а значения могут повторяться. Порядок элементов не гарантирован. Может иметь 1 null ключ и несколько null значений. Set состоит из ключей. Которые должны быть уникальны. В HashSet элементы не упорядочены и хранятся в удобном для HashSet порядке (можно сказать случайном). Может хранить 1 null значение. Что вы знаете о коллекциях типа HashSet? Хеш сет представляет собой таблицу хеш кодов, которая генерируется при добавлении элемента. Элементами хеш сета могут быть только уникальные значения ключа, и одно null значение. Как работает HashSet? HashSet основан на HashMap, и так же представляет собой массив. HashSet использует хеш таблицы. В начале вычисляется хеш код объекта. На основании хеша и размера массива вычисляется индекс массива. По этому индексу кладется объект. Если происходит коллизия ( эта ячейка не пустая), то в эту же ячейку ложится новый объект и используется односвязный список между ними. Что в HashSet используется вместо значений HashMap? new Object. Почему в HashSet используется new Object а не null для value значений? Если не использовать null значение, до при создании и удалении элементов, не будет видно выполнилось действие или нет, т.к. до и после ссылка будет равна null. Что вы знаете о коллекциях типа TreeSet? TreeSet — коллекция, которая хранит свои элементы вв отсортированном и возрастающем порядке. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n). Что вы знаете о коллекциях типа TreeMap? Имплементирует интерфейсы NavigableMap и SortedMap, TreeMap получает дополнительный функционал, которого нет в HashMap, но с меньшей производительностью. В TreeMap элементы хранятся в естественном(по возрастанию) порядке или согласно компаратору. В основе лежит Красно-чёрное дерево (Red-Black Tree). Возможность работы с null-ключом если он разрешен компаратором. Что такое красно-черное дерево? Структура для хранения данных. Если в кратце, то у любого дерева есть корень. Если нужное значение меньше чем корень, то поиск идет в левой части, если больше то в правой. Что вы знаете о коллекциях типа LinkedHashSet? LinkedHashSet наследуется от HashSet. Храненит элементы в порядке добавления. Имеет двухсвязный список между элементами. Что вы знаете о коллекциях типа LinkedHashMap? LinkedHashMap наследуется от HashMap. Храненит элементы в порядке добавления. Имеет двухсвязный список между элементами. На что указывают крайние ссылки в двухсвязном списке? на null Что такое двухсвязный и односвязный список? двухсвязный список - когда элемент имеют ссылку на предыдущий и следующий. односвязный список - когда элемент имеют ссылку на следующий. Основные реализации List? ArrayList Список LinkedList Список Vector Вектор Stack Стек Основные реализации Set? HashSet TreeSet LinkedHashSet Основные реализации Map? HashMap TreeMap LinkedHashMap Hashtable Что вы знаете о коллекциях типа LinkedList? LinkedList - реализует интерфейс List. Является двунаправленным списком, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. Реализует методы получения, удаления и вставки в начало, середину и конец списка. Позволяет добавлять любые элементы в том числе и null. Хранит Элементы в порядке добавления. Какие реализации SortedSet вы знаете и в чем их особенность? TreeSet - реаализации SortedSet. Реализации этого интерфейса, следит за уникальностью хранимых объектов и поддерживают их в порядке возрастания. Отношение порядка между объектами может быть определено, помощью метода compareTo интерфейса Comparable В чем отличия/сходства List и Set? Оба унаследованы от Collection, а значит имеют одинаковый набор и сигнатуры методов. List хранит объекты в порядке вставки, элемент можно получить по индексу. Set не может хранить одинаковых элементов, доступ по ключу. Что разного/общего у классов ArrayList и LinkedList? ArrayList реализован внутри в виде обычного массива, доступ по индексу и вставка в конец происходит очень быстро. Для вставки в середину или начало приходится сначала сдвигать на один все элементы после него, а уже затем в освободившееся место вставлять новый элемент. LinkedList реализован в виде двухсвязного списка. Каждый элемент знает предыдущий и следующий за ним. Вставка осуществляется быстро за счет простого изменения ссылок на соседние элементы. А обход по всем элементам занимает много времени. Когда лучше использовать ArrayList, а когда LinkedList? Часто указывается что там где нужно добавлять и удалять много элементов из середины нужно использовать LinkedList. А там где нужен доступ по индексу и добавление в конец - ArrayList. Но по факту лучше стараться почти всегда использовать ArrayList. Т.к в большинстве случаев LinkedList проигрывает по потребляемой памяти и по скорости выполнения операций ArrayList. LinkedList предпочтительно применять, когда происходит активная работа (вставка/удаление) с серединой списка или в случаях, когда необходимо гарантированное время добавления элемента в список. Что будет, если в Map положить два значения с одинаковым ключом? Последнее значение перезапишет предыдущее. Что такое HashtTable, чем она отличается от HashMap? HashtTable- deprecated. Не рекомендована к использованию. Основные отличия HashtTable - синхронизирована и медленнее работает и не позволяет иметь null ключей и значений. Порядок следования в коллекциях? HashMap/HashSet - "случайный" порядок(удобный для Map/Set) хранения элементов. ТгееМар/ТгееSet - хранит эл-ты в порядке возрастания элементов. LinkedHashMap/LinkedHashSet - хранит эл-ты в порядке добавления элементов. Дайте определение понятию "итератор"? Iterator Итератор — объект, позволяющий перебирать элементы коллекции. Методы Iterator? next(); boolean hasNext(); void remove(); Какую функциональность представляет класс Collections? Collections.sort() - cсортировка Collections.shuffle() - Перемешивает коллекцию в случайном порядке. Collections.reverse() - Переворачивает коллекцию в обратном порядке. Collections.binarySearch() - Поиск в коллекции по ключу с использованием бинарного поиска. Collections.copy() - Копирует коллекцию источник src в dest. Collections.frequency() - Возвращает число вхождений объекта в коллекции. Collections.synchronizedCollection() - Возвращает синхронизированную (потокобезопасную) коллекцию. Какие коллекции синхронизированы? Для этого используется пакет Concurrent. @Deprecated HashTable, Vector. Как получить синхронизированную коллекцию из не синхронизированной? Collections.synchronizedList(list); Collections.synchronizedSet(set); Collections.synchronizedMap(map); Все они принимают коллекцию в качестве параметра, и возвращают потокобезопасную коллекцию с теми же элементами внутри. Как получить коллекцию только для чтения? Используйте следующие методы: Collections.unmodifiableList(list); Collections.unmodifiableSet(set); Collections.unmodifiableMap(map); Все они принимают коллекцию в качестве параметра, и возвращают коллекцию только для чтения с теми же элементами внутри. В чем разница между Iterator и Enumeration? Enumeration в два раза быстрее Iterator и использует меньше памяти. Iterator потокобезопасен, т.к. не позволяет другим потокам модифицировать коллекцию при переборе. Enumeration можно использовать только для read-only коллекций. Так же у него отсутствует метод remove(); |