Ответы на вопросы на собеседование Java Collections Framework (часть 2).
- Какое худшее время работы метода contain() для элемента, который есть в LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.
- Какое худшее время работы метода contain() для элемента, который есть в ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
O(N). Время поиска элемента линейно пропорционально количеству элементов с списке.O(N). Здесь стоит заметить, что добавление элемента в конец списка с помощью методом add(value), addLast(value) и добавление в начало списка с помощью addFirst(value) выполняется за время O(1).
O(N) - будет при добавление элемента в отсортированный список, а также при добавлении элемента с помощью метода add(index, value).
- Какое худшее время работы метода add() для ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
O(N). Вставка элемента в конец списка осуществляется за время O(1), но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый.
- Сколько выделяется элементов в памяти при вызове ArrayList.add()?
Если в массиве достаточно места для размещения нового элемента, то дополнительное место в памяти не выделяется. Иначе происходит создание нового массива с размером:
Другими словами, создается новый массив, размер которого вычисляется как умножение старого размера на 1.5 (это верно для JDK 1.7, в более ранних версиях вычисления отличаются).
- Сколько выделяется элементов в памяти при вызове LinkedList.add()?
Создается один новый экземпляр вложенного класса Node.
- Оцените количество памяти на хранение одного примитива типа byte в LinkedList?
Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные. Для x32 систем каждая ссылка занимает 32 бита (4 байта). Сам объект типа Node занимает приблизительно 8 байт. Размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типа byte занимает 1 байт памяти, но в списке примитивы упаковываются, соответственно получаем еще 8 байт. Таким образом, в x32 JVM около 32 байтоввыделяется для хранения одного значения типа byte в LinkedList.
Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт). Вычисления аналогичны.
- Оцените количество памяти на хранение одного примитива типа byte в ArrayList?
ArrayList основан на массиве. Каждый элемент массива хранит примитивный тип данных - byte, размер которого 1 байт.
- Я добавляю элемент в середину List-а: list.add(list.size()/2, newElem). Для кого эта операция медленнее — для ArrayList или для LinkedList?
Для ArrayList:
- проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив ( O(N) );
- копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо ( O(N/2));
- вставка элемента ( O(1) ).
Для LinkedList:
- поиск позиции вставки ( O(N/2) );
- вставка элемента ( O(1) ).
В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет системного метода System.arraycopy().
- Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)?
Использовать обратный итератор. Для этого в LinkedList есть метод descendingIterator().
- Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?
- Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.hashCode() == ref1.hashCode()?
Да, могут. Метод hashCode() не гарантирует уникальность возвращаемого значения.
- Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.equals(ref1) == true?
Да, могут. Для этого в классе этих объектов должен быть переопределен метод equals().
Если используется метод Object.equals(), то для двух ссылок x и y метод вернет true тогда и только тогда, когда обе ссылки указывают на один и тот же объект (т.е. x == y возвращает true).
- Могут ли у разных ссылок на один объект в памяти (ref0 == ref1) быть ref0.equals(ref1) == false?
Нет, не может. Метод equals() должен гарантировать свойство рефлексивности: для любых ненулевых ссылок xметод x.equals(x) должен возвращать true.
- Есть класс Point{int x, y;}. Почему хэш-код в виде 31 * x + y предпочтительнее чем x + y?
Множитель создает зависимость значения хэш-кода от очередности обработки полей, а это дает гораздо лучшую хэш-функцию.
- Если у класса Point{int x, y;} «правильно» реализовать метод equals (return ref0.x == ref1.x && ref0.y == ref1.y), но сделать хэш-код в виде int hashCode() {return x;}, то будут ли корректно такие точки помещаться и извлекаться из HashSet?
HashSet использует HashMap для хранения элементов (в качестве ключа используется сам объект). При добавлении элемента в HashMap вычисляется хэшкод и позиция в массиве, куда будет вставлен новый элемент. У всех экземпляров класса Point одинаковый хэшкод, что приводит в вырождению хэш-таблицы в список. При возникновении коллизии осуществляется проверка на наличие уже такого элемента в текущем списке:
Если элемент найден, то его значение перезаписывается. В нашем случае для разных объектов метод equals() будет возвращать false. Соответственно новый элемент будет добавлен в HashSet. Извлечение элемента также будет осуществляться успешно.
Но производительность такого кода будет низкой и преимущества хэш-таблиц использоваться не будут.
- equals() порождает отношение эквивалентности. Какими из свойств обладает такое отношение: коммутативность, симметричность, рефлексивность, дистрибутивность, ассоциативность, транзитивность?
Метод equals() должен обеспечивать:
- симметричность (для любых ненулевых ссылок x и y метод x.equals(y) должен возвращать true тогда и только тогда, когда y.equals(x) возвращает true);
- рефлексивность (для любых ненулевых ссылок x метод x.equals(x) должен возвращать true.);
- транзитивность (для любых ненулевых ссылок x, y и z, если x.equals(y) возвращает true и y.equals(z)возвращает true, тогда и x.equals(z) должен возвращать true).
Также есть ещё два свойства: постоянство и неравенство null.
- Можно ли так реализовать equals(Object that) {return this.hashCode() == that.hashCode()}?
Строго говоря нельзя, поскольку метод hashCode() не гарантирует уникальность значения для каждого объекта. Однако для сравнения экземпляров класса Object такой код допустим, т.к. метод hashCode() в классе Object возвращает уникальные значения для разных объектов (вычисления основаны на использовании адреса объекта в памяти).
- В equals требуется проверять, что аргумент (equals(Object that)) такого же типа как и сам объект. В чем разница между this.getClass() == that.getClass() и that instanceof MyClass?
Оператор instanceof сравнивает объект и указанный тип. Его можно использовать для проверки является ли данный объект экземпляром некоторого класса, либо экземпляром его дочернего класса, либо экземпляром класса, который реализует указанный интерфейс.
getClass() = ... проверяет два типа на идентичность.
Для корректной реализации контракта метода equals() необходимо использовать точное сравнение с помощью getClass().
- Можно ли реализовать метод equals класса MyClass вот так: class MyClass {public boolean equals(MyClass that) {return this == that;}}?
Реализовать можно, но данный метод не переопределяет метод equals() класса Object, а перегружает его.
- Будет ли работать HashMap, если все ключи будут возвращать int hashCode() {return 42;}?
Да, будет. Но тогда хэш-таблица вырождается в связный список и теряет свои преимущества.
- Зачем добавили HashMap, если уже был Hashtable?
Класс Hashtable был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Hashtable синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс HashMap, методы которого не синхронизированы.
Помимо этого класс HashMap обладает некоторыми другими отличиями: например, позволяет хранить один null ключ и множество null значений.
- Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресацией и на основе метода цепочек. Как реализована HashMap? Почему так сделали (по вашему мнению)? В чем минусы и плюсы каждого подхода?
Класс HashMap реализован с использованием метода цепочек, т.е. каждой ячейке массива соответствует свой связный список и при возникновении коллизии осуществляется добавление нового элемента в этот список.
Для метода цепочек коэффициент заполнения может быть больше 1, с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов, либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения.
Среди методов открытой реализации различают:
- линейное пробирование;
- квадратичное пробирование;
- двойное хеширование.
Основные недостатки структур с методом открытой адресации:
- Количество элементов в таблице не может превышать размера массива. По мере увеличения числа элементов в таблице и повышения коэффициента заполнения (load factor) производительность структуры резко падает, поэтому необходимо проводить перехеширование.
- Сложно организовать удаление элемента.
- Также первые два метода открытой адресации приводят к проблеме первичной и вторичной группировок.
Основное преимущество хэш-таблицы с открытой адресацией - это отсутствие затрат на создание и хранение объектов списка. Также проще организовать сериализацию/десериализацию объекта.
- Сколько переходов по ссылкам происходит, когда вы делаете HashMap.get(key) по ключу, который есть в таблице?
Возможно, я неправильно понял этот вопрос. За переходы по ссылке в данном ответе я считаю вызовы методов.
Рассмотрим первый случай, когда ключ равен null: выполняем метод getForNullKey().
В цикле foreach проходимся по списку значений для ключа и возвращаем нужное значение. Таким образом, получаем 1 переход.
Второй случай: ключ не равен null. Выполняем метод getEntry(key).
Вычисляется хэш-код ключа (метод hash(key)), затем определяется индекс ячейки массива, в которой будем искать значение (метод indexFor(hash, table.length)).
После того, как нашли нужную пару "ключ-значение" возвращаем значение (метод entry.getValue()). Таким образом, получаем 4 перехода.
- Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap?
- Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap?
Один новый объект статического вложенного класса Entry<K,V>.
- Как работает HashMap при попытке сохранить в нее два элемента по ключам с одинаковым hashCode, но для которых equals == false?
По значению hashCode вычисляется индекс ячейки массива, в список которой будет происходить добавление элемента. Перед добавлением осуществляется проверка на наличие уже элементов в этой ячейке. Если элементов нет, то происходит добавление. Если возникает коллизия, то итеративно осуществляется обход списка в поисках элемента с таким же ключом и хэш-кодом. Если такой элемент найден, то его значение перезаписывается, а старое - возвращается. Поскольку в условии сказано, что добавляемые ключи - разные, то второй элемент будет добавлен в начало списка.
- HashMap может выродиться в список даже для ключей с разным hashCode. Как это возможно?
Это возможно в случае, если метод, определяющий номер ячейки массива по hashCode будет возвращать одинаковое значение.
- Какое худшее время работы метода get(key) для ключа, которого нет в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
O(N). Худший случай - это поиск ключа в таблице, вырожденной в список, перебор ключей которой занимает линейно пропорциональное время количеству хранимых элементов.
- Какое худшее время работы метода get(key) для ключа, который есть в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
O(N). Аналогичные рассуждения, что и для предыдущего вопроса.
- Объясните смысл параметров в конструкторе HashMap(int initialCapacity, float loadFactor).
int initialCapacity - исходный размер HashMap (количество корзин в хэш-таблице в момент её создания), по умолчанию имеет значение 16.
float loadFactor - коэффициент заполнения HashMap. Равен отношению числа хранимых элементов в таблице к её размеру. loadFactor - является мерой заполнения таблицы элементами, при превышении количества хранимых таблицей значений , происходит автоматическое перехеширование. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных.
float loadFactor - коэффициент заполнения HashMap. Равен отношению числа хранимых элементов в таблице к её размеру. loadFactor - является мерой заполнения таблицы элементами, при превышении количества хранимых таблицей значений , происходит автоматическое перехеширование. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных.
Поясните пожалуйста последний пункт.
ОтветитьУдалитьЯ думал превышение количества хранимых таблицей значений над её размером возможно только при коллизиях, когда в одной корзине хэш-таблицы хранится связный список из более чем одного элемента. Иначе мне не понятно как размер таблицы может оказаться меньше количества хранимых элементов (разве что элементы с разными хэшами будут храниться в одной корзине, но тогда по какому принципу всё это происходит??). И также не ясно как перехеширование поможет исправить ситуацию с превышением loadFactor, из вики понял что перехеширвоание это выбор новой хэш-функции для пересчёта хэшей с целью уменьшить размеры цепочек/кластеризацию; но тогда получается что вовсе не обязательно будет использован определённый в Object или переопределённый в MyClass hash() ? мне казалось что просто должно быть расширено initialCapacity
Здесь более подробно как работает HashMap.
УдалитьГрубое представление, что происходит. HashMap представляет из себя массив записей (Map.Entry). При добавлении новых значений проверяется, не превышен ли порог количества элементов. Порог(threshold) определяется как capacity * loadFactor. Если он превышается, то capacity (т.е. массив записей) увеличивается, соответственно все хранящиеся значения заново добавляются в HashMap(происходит перехеширование).
Спасибо
УдалитьКакое худшее время работы для метода ADD() в LinkedList, исправте O(1) на O(N), при вставке в середину, будет происходить итерация до нужного элемента, O(1) будет только при вставке в начало, либо в конец.
ОтветитьУдалитьСпасибо поправил в ответе. Также добавлю что O(N) - будет при добавление элемента в отсортированный список, а также при добавлении элемента с помощью метода add(index, value). Более подробную информацию можно найти здесь.
УдалитьПри добавлении в ArrayList если будет расширяться массив время не O(n). При расширении массива конструкторы созданных элементов не вызываются. Копирование происходит низкоуровневой функцией копирования, которая переносит сразу блок памяти. Так что тут сложно сказать какая сложность будет в общем случае.
ОтветитьУдалитьВремя работы HashMap Get(Key) для ключа которого нет в таблице.
ОтветитьУдалитьO(1) в данном случае, не будет обхода списка потому что по данному ключу не будет списка. Или я не прав?
Хэшкод не гарантирует уникальность, кроме того, в бакетах хранятся не просто по хеш кодам. Поэтому мы можем попасть в бакет, пройти его весь, и даже несколько раз вызвать метод equals при коллизии хэшкодов.
УдалитьПоясните пожалуйста что значит О(n), O(1) и тд, это степень?
ОтветитьУдалитьЭтот комментарий был удален автором.
УдалитьВикипедия -> Временная сложность алгоритма
УдалитьЭээ...
ОтветитьУдалитьПри сравнении вставки середину ArrayList и LinkedList аргумент в пользу большей скорости ArrayList - более быстрое копирование элементов. А зачем при вставке в LinkedList вообще копировать элементы ? Разве он не меняет лишь связи с соседями выставляя ссылку на след элемент и предыдущий ? За счет отсутствия этого копирования LinkedList и быстрее
не понял по количеству переходов по ссылке.
ОтветитьУдалитьна мой взгляд это не возможно сказать, т.к. кто знает - сколько переходов по ссылке будет во время расчета хэша ключа, и сколько будет переходов при обходе списка/дерева связанного с бакетом
или я что-то не так понял?