ОглавлениеCore
 Скачать 1.53 Mb.
|
|
Согласно Кнуту и Кормену существует две основных реализации хеш- таблицы: на основе открытой адресации и на основе метода цепочек. Как реализована HashMap? Почему, по вашему мнению, была выбрана именно эта реализация? В чем плюсы и минусы каждого подхода? HashMap реализован с использованием метода цепочек, т. е. каждой ячейке массива (корзине) соответствует свой связный список и при возникновении коллизии осуществляется добавление нового элемента в этот список. Для метода цепочек коэффициент заполнения может быть больше 1, и с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения. Среди методов открытой реализации различают: • линейное пробирование; • квадратичное пробирование; • двойное хэширование. Недостатки структур с методом открытой адресации: • количество элементов в хеш-таблице не может превышать размера массива: по мере увеличения числа элементов и повышения коэффициента заполнения производительность структуры резко падает, поэтому необходимо проводить перехеширование; • сложно организовать удаление элемента; • первые два метода открытой адресации приводят к проблеме первичной и вторичной группировок. Преимущества хеш-таблицы с открытой адресацией: • отсутствие затрат на создание и хранение объектов списка; • простота организации сериализации/десериализации объекта. Как работает HashMap при попытке сохранить в него два элемента по ключам с одинаковым hashCode(), но для которых equals() == false? По значению hashCode() вычисляется индекс ячейки массива, в список которой этот элемент будет добавлен. Перед добавлением осуществляется проверка на наличие элементов в этой ячейке. Если элементы с таким hashCode() уже присутствует, но их equals() методы не равны, то элемент будет добавлен в конец списка. Какое начальное количество корзин в 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 2 32 Какое худшее время работы метода get(key) для ключа, который есть в HashMap? O(N). Худший случай – это поиск ключа в HashMap, вырожденного в список по причине совпадения ключей по hashCode() и для выяснения, хранится ли элемент с определенным ключом, может потребоваться перебор всего списка. Сколько переходов происходит в момент вызова 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 «ключ-значение». В чем разница между HashMap и IdentityHashMap? Для чего нужна IdentityHashMap? IdentityHashMap – это структура данных, также реализующая интерфейс Map и использующая при сравнении ключей (значений) сравнение ссылок, а не вызов метода equals(). Другими словами, в IdentityHashMap два ключа k1 и k2 будут считаться равными, если они указывают на один объект, т. е. выполняется условие k1 == k2. IdentityHashMap не использует метод hashCode(), вместо него применяется метод System.identityHashCode(), по этой причине IdentityHashMap по сравнению с HashMap имеет более высокую производительность, особенно если последний хранит объекты с дорогостоящими методами equals() и hashCode(). Одним из основных требований к использованию HashMap является неизменяемость ключа, а т. к. IdentityHashMap не использует методы equals() и hashCode(), то это правило на него не распространяется. IdentityHashMap может применяться для реализации сериализации/клонирования. При выполнении подобных алгоритмов программе необходимо обслуживать хеш-таблицу со всеми ссылками на объекты, которые уже были обработаны. Такая структура не должна рассматривать уникальные объекты как равные, даже если метод equals() возвращает true. В чем разница между HashMap и WeakHashMap? Для чего используется WeakHashMap? В Java существует 4 типа ссылок: сильные (strong reference), мягкие (SoftReference), слабые (WeakReference) и фантомные (PhantomReference). Особенности каждого типа ссылок связаны с работой Garbage Collector. Если объекта можно достичь только с помощью цепочки WeakReference (то есть на него отсутствуют сильные и мягкие ссылки), то данный объект будет помечен на удаление. WeakHashMap – это структура данных, реализующая интерфейс Map и основанная на использовании WeakReference для хранения ключей. Таким образом, пара «ключ-значение» будет удалена из WeakHashMap, если на объект-ключ более не имеется сильных ссылок. В качестве примера использования такой структуры данных можно привести следующую ситуацию: допустим, имеются объекты, которые необходимо расширить дополнительной информацией, при этом изменение класса этих объектов нежелательно либо невозможно. В этом случае добавляем каждый объект в WeakHashMap в качестве ключа, а в качестве значения – нужную информацию. Таким образом, пока на объект имеется сильная ссылка (либо мягкая), можно проверять хеш-таблицу и извлекать информацию. Как только объект будет удален, то WeakReference для этого ключа будет помещен в ReferenceQueue и затем соответствующая запись для этой слабой ссылки будет удалена из WeakHashMap. В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences? SoftHashMap представлена в сторонних библиотеках, например, в Apache Commons. В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences? PhantomReference при вызове метода get() возвращает всегда null, поэтому тяжело представить назначение такой структуры данных. В чем отличия 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 предоставляет множество статических методов инициализации для упрощенного и удобного создания экземпляров. LinkedHashMap – что в нем от LinkedList, а что от HashMap? Реализация LinkedHashMap отличается от HashMap поддержкой двухсвязного списка, определяющего порядок итерации по элементам структуры данных. По умолчанию элементы списка упорядочены согласно их порядку добавления в LinkedHashMap (insertion-order). Однако порядок итерации можно изменить, установив параметр конструктора accessOrder в значение true. В этом случае доступ осуществляется по порядку последнего обращения к элементу (access-order). Это означает, что при вызове методов get() или put() элемент, к которому обращаемся, перемещается в конец списка. При добавлении элемента, который уже присутствует в LinkedHashMap (т. е. с одинаковым ключом), порядок итерации по элементам не изменяется. NavigableSet Интерфейс унаследован от SortedSet и расширяет методы навигации, находя ближайшее совпадение по заданному значению. Как и в родительском интерфейсе, в NavigableSet не может быть дубликатов. Многопоточка Чем процесс отличается от потока? Процесс – экземпляр программы во время выполнения, независимый объект, которому выделены системные ресурсы (например, процессорное время и память). Каждый процесс выполняется в отдельном адресном пространстве: один процесс не может получить доступ к переменным и структурам данных другого. Если процесс хочет получить доступ к чужим ресурсам, необходимо использовать межпроцессное взаимодействие. Это могут быть конвейеры, файлы, каналы связи между компьютерами и многое другое. Для каждого процесса ОС создает так называемое «виртуальное адресное пространство», к которому процесс имеет прямой доступ. Это пространство принадлежит процессу, содержит только его данные и находится в полном его распоряжении. Операционная система отвечает за то, как виртуальное пространство процесса проецируется на физическую память. Поток (thread) – способ выполнения процесса, определяющий последовательность исполнения кода в процессе. Потоки всегда создаются в контексте какого-либо процесса, и вся их жизнь проходит только в его границах. Потоки могут исполнять один и тот же код и манипулировать одними и теми же данными, а также совместно использовать описатели объектов ядра, поскольку таблица описателей создается не в отдельных потоках, а в процессах. Так как потоки расходуют существенно меньше ресурсов, чем процессы, в ходе выполнения работы выгоднее создавать дополнительные потоки и избегать создания новых процессов. Чем Thread отличается от Runnable? Когда нужно использовать Thread, а когда Runnable? Thread – это класс, некоторая надстройка над физическим потоком. Runnable – это интерфейс, представляющий абстракцию над выполняемой задачей. Помимо того, что Runnable помогает разрешить проблему множественного наследования, несомненный плюс от его использования состоит в том, что он позволяет отделить логику выполнения задачи от непосредственного управления потоком. В классе Thread имеется несколько методов, которые можно переопределить в порожденном классе. Из них обязательному переопределению подлежит только метод run(). Этот же метод должен быть определен и при реализации интерфейса Runnable. Некоторые программисты считают, что создавать подкласс, порожденный от класса Thread, следует только в том случае, если нужно дополнить его новыми функциями. Так, если переопределять любые другие методы из класса Thread не нужно, то можно ограничиться только реализацией интерфейса Runnable. Кроме того, реализация интерфейса Runnable позволяет создаваемому потоку наследовать класс, отличающийся от Thread. Что такое монитор? Как монитор реализован в java? Монитор – механизм синхронизации потоков, обеспечивающий доступ к неразделяемым ресурсам. Частью монитора является mutex, который встроен в класс Object и имеется у каждого объекта. Удобно представлять mutex как id захватившего его объекта. Если id равен 0 – ресурс свободен. Если не 0 – ресурс занят. Можно встать в очередь и ждать его освобождения. В Java монитор реализован с помощью ключевого слова synchronized. Что такое синхронизация? Какие способы синхронизации существуют в Java? Синхронизация – это процесс, который позволяет выполнять потоки параллельно. В Java все объекты имеют блокировку, благодаря которой только один поток одновременно может получить доступ к критическому коду в объекте. Такая синхронизация помогает предотвратить повреждение состояния объекта. Способы синхронизации в Java: 1. Системная синхронизация с использованием wait()/notify(). Поток, который ждет выполнения каких-либо условий, вызывает у этого объекта метод wait(), предварительно захватив его монитор. На этом его работа приостанавливается. Другой поток может вызвать на этом же самом объекте метод notify(), предварительно захватив монитор объекта, в результате чего ждущий на объекте поток «просыпается» и продолжает свое выполнение. В обоих случаях монитор надо захватывать в явном виде через synchronized- блок, потому как методы wait()/notify() не синхронизированы! 2. Системная синхронизация с использованием join(). Метод join(), вызванный у экземпляра класса Thread, позволяет текущему потоку остановиться до того момента, как поток, связанный с этим экземпляром, закончит работу. 3. Использование классов из пакета java.util.concurrent.Locks – механизмы синхронизации потоков, альтернативы базовым synchronized, wait, notify, notifyAll: |