Ответы на вопросы на собеседование Java Collections Framework (часть 1).
- Что такое Коллекция?
Коллекции - это хранилища или контейнеры, поддерживающие различные способы накопления и упорядочения объектов с целью обеспечения возможностей эффективного доступа к ним. Они представляют собой реализацию абстрактных структур данных, поддерживающих три основные операции:
добавление нового элемента в коллекцию;
- удаление элемента из коллекции;
- изменение элемента в коллекции.
- Назовите основные интерфейсы коллекций и их имплементации.
List - хранит упорядоченные елементы(могут быть одинаковые); Имеет такие реализации как LinkedList, ArrayList и Vector.
- Vector синхронизирован, и по этому в одном потоке, он работает медленней остальных реализаций.
- ArrayList - его преимущество в навигации по коллекции.
- LinkedList - Его преимущество в во вставке и удалении элементов в коллекции.
Set - коллекции, которые не содержат повторяющихся элементов.
Основные реализации: HashSet, TreeSet, LinkedHashSet
- TreeSet - упорядочивает элементы по их значениям;
- HashSet - упорядочивает элементы по их хэш ключах, хотя на первый взляд может показаться что элементы хранятся в случайном порядке.
- LinkedHashSet - хранит элементы в порядке их добавления
Queue - интерфейс для реализации очереди в джава.
Основные реализации: LinkedList, PriorityQueue.
Очереди работают по принципу FIFO – first in first out.
Map - интерфейс для реализации так называемой карты, где элементы хранятся с их ключами.
Основные реализации: HashTable, HashMap, TreeMap, LinkedHashMap
- HashTable - синхронизированна, объявлена уставревшей.
- HashMap - порядок елементов рассчитывается по хэш ключу;
- TreeMap - элементы хранятся в отсортированном порядке
- LinkedHashMap - элементы хранятся в порядке вставки
Ключи в Мар не могут быть одинаковыми!
Синхронизировать не синхронизированные коллекции и карты можно посредством класса Collections.synchronizedMap(MyMap)\ synchronizedList(MyList).
- Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй?
Отличие заключается в способе хранения данных. ArrayList хранит в виде массива, а LinkedList - в виде списка (двунаправленного).
В ArrayList быстрее происходит сортировка, т.к. для ее выполнения данные списка копируются в массив (а копировать из массива ArrayList в массив для сортировки быстрее). При большом числе операций добавления и удаления LinkedList должен быть более удачным выбором, т.к. при этих операциях не приходится перемещать части массива.
Если при добавлении в ArrayList превышается его объем, размер массива увеличивается, новая емкость рассчитывается по формуле (oldCapacity * 3) / 2 + 1, поэтому лучше указывать размер при создании или, если он не известен, использовать LinkedList (но это может быть существенно при слишком уж больших объемах данных).
В ArrayList быстрее происходит сортировка, т.к. для ее выполнения данные списка копируются в массив (а копировать из массива ArrayList в массив для сортировки быстрее). При большом числе операций добавления и удаления LinkedList должен быть более удачным выбором, т.к. при этих операциях не приходится перемещать части массива.
Если при добавлении в ArrayList превышается его объем, размер массива увеличивается, новая емкость рассчитывается по формуле (oldCapacity * 3) / 2 + 1, поэтому лучше указывать размер при создании или, если он не известен, использовать LinkedList (но это может быть существенно при слишком уж больших объемах данных).
- Чем отличается HashMap от Hashtable?
Класс HashMap по функционалу очень похож на Hashtable. Главное отличие в том, что методы класса Hashtable синхронизированы, а HashMap - нет. Кроме этого класс HashMap в отличии от Hashtable разрешает использование null в качестве ключей и значений.
Наличие синхронизации в Hashtable уменьшает производительность кода, использующего данный класс. Поэтому классы JCF (Java Collections Framework, появившийся в Java 2), в том числе и HashMap, несинхронизированы. Если синхронизация все же нужна, можно использовать методы класса Collections: Collections.synchronizedMap(map), Collections.synchronizedList(list) или Collections.synchronizedSet(set).
Данные методы возвращают синхронизированный декоратор переданной коллекции. При этом все равно в случае итерирования по коллекции требуется ручная синхронизация.
Начиная с Java 6 JCF был расширен специальными коллекциями, поддерживающими многопоточный доступ, такими как CopyOnWriteArrayList и ConcurrentHashMap.
- Чем отличается ArrayList от Vector?
- Чем отличается ArrayList от Vector?
Методы класса Vector синхронизированы, в то время как ArrayList - нет.
- Как сравниваются елементы коллекций?
Для сравнения элементов коллекций используется метод equals() и hashcode();Эти методы унаследованы от класса Object.
- Если наш пользовательский класс переопределяет equals(), то он должен и переопределить hashcode()
- Если два объекта эквивалентны, то и хэш коды этих объектов тоже должны быть равны
- Если поле не используется в equals(), то оно и не должно использоваться в hashcode().
- Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection,Iterable, Iterator, NavigableSet, NavigableMap.
- Почему Map - это не Collection, в то время как List и Set являются Collection?
Коллекция (List и Set) представляет собой совокупность некоторых элементов (обычно экземпляров одного класса).Map -это совокупность пар "ключ"-"значение".
Соответственно некоторые методы интерфейса Collection нельзя использовать в Map. Например, метод remove(Object o) в интерфейсе Collection предназначен для удаления элемента, тогда как такой же метод remove(Object key) в интерфейсе Map - удаляет элемент по заданному ключу.
Итератор - объект, позволяющий перебирать элементы коллекции. Например foreach реализован с использованием итератора. Одним из ключевых методов интерфейса Collection является метод Iterator<E> iterator(). Он возвращает итератор - то есть объект, реализующий интерфейс Iterator.
Интерфейс Iterator имеет следующее определение:
- Дайте определение понятию "iterator".
Итератор - объект, позволяющий перебирать элементы коллекции. Например foreach реализован с использованием итератора. Одним из ключевых методов интерфейса Collection является метод Iterator<E> iterator(). Он возвращает итератор - то есть объект, реализующий интерфейс Iterator.Интерфейс Iterator имеет следующее определение:
- Что вы знаете об интерфейсе Iterable?
Все коллекции из java.util реализуют интерфейс Collection, который, в свою очередь, расширяет интерфейс Iterable. В интерфейсе Iterable описан только один метод:Iterator iterator();
Он возвращает Iterator, т.е. объект, который поочерёдно возвращает все элементы коллекции.
- Как одной строчкой преобразовать HashSet в ArrayList?
- Как одной строчкой преобразовать HashSet в ArrayList?
- Как одной строчкой преобразовать ArrayList в HashSet?
- Как перебрать все ключи Map учитывая, что Map - это не Iterable?
Использовать метод keySet(), который возвращает множество (Set<K>) ключей.
- Как перебрать все значения Map учитывая, что Map - это не Iterable?
Использовать метод values(), который возвращает коллекцию (Collection<V>) значений.
- Как перебрать все пары ключ-значение в Map учитывая, что Map - это не Iterable?
Использовать метод entrySet(), который возвращает множество (Set<Map.Entry<K, V>) пар "ключ"-"значение".
- В чем проявляется “сортированность” SortedMap, кроме того, что toString() выводит все по порядку?
Естественное упорядочивание (natural ordering) отражается при итерации по коллекции ключей или значений хэш-таблицы (возвращаемых методами keySet(), values() и entrySet()).
- Как одним вызовом копировать элементы из любой Collection в массив?
- Реализуйте симметрическую разность двух коллекций используя методы Collection (addAll(), removeAll(), retainAll()).
Симметрическая разность двух коллекций - это множество элементов, одновременно не принадлежащих обоим исходным коллекциям.
- Сравните Enumeration и Iterator.
Оба интерфейса предназначены для обхода коллекций. Интерфейс Iterator был введен несколько позднее в Java Collections Framework и его использование предпочтительнее.
Основные различия Iterator по сравнению с Enumeration:
- наличие метода remove() для удаления элемента из коллекции при обходе;
- исправлены имена методов для повышения читаемости кода.
- Как между собой связаны Iterable и Iterator?
Интерфейс Iterable имеет только один метод - iterator(), который возвращает итератор коллекции для её обхода.
- Как между собой связаны Iterable, Iterator и «for-each» введенный в Java 5?
Экземпляры классов, реализующих интерфейс Iterable, могут использоваться в конструкции foreach.
- Сравните Iterator и ListIterator.
- Сравните Iterator и ListIterator.
ListIterator расширяет интерфейс Iterator, позволяя клиенту осуществлять обход коллекции в обоих направлениях, изменять коллекцию и получать текущую позицию итератора.
При этом важно помнить, что ListIterator не указывает на конкретный элемент, а его текущая позиция располагается между элементами, которые возвращают методы previous() и next(). Таким образом, модификация коллекции осуществляется для последнего элемента, который был возвращен методами previous() и next().
- Что произойдет, если я вызову Iterator.next() не «спросив» Iterator.hasNext()?
Если итератор указывает на последний элемент коллекции, то возникнет исключение NoSuchElementException, иначе будет возвращен следующий элемент.
- Что произойдет, если я вызову Iterator.next() перед этим 10 раз вызвав Iterator.hasNext()? Я пропущу 9 элементов?
Нет, hasNext() осуществляет только проверку наличия следующего элемента.
- Если у меня есть коллекция и порожденный итератор, изменится ли коллекция, если я вызову iterator.remove()?
Вызов метода iterator.remove() возможен только после вызова метода iterator.next() хотя бы раз, иначе появится исключение IllegalStateException().
Если iterator.next() был вызван прежде, то iterator.remove() удалит элемент, на который указывает итератор.
- Если у меня есть коллекция и порожденный итератор, изменится ли итератор, если я вызовуcollection.remove(..)?
Итератор не изменится, но при следующем вызове его методов возникнет исключение ConcurrentModificationException.
- Зачем добавили ArrayList, если уже был Vector?
Обе структуры данных предназначены для хранения коллекции элементов, в том числе дупликатов и null. Они основаны на использовании массивов, динамически расширяющихся при необходимости.
Класс Vector был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Vector синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс ArrayList, методы которого не синхронизированы.
- В реализации класса ArrayList есть следующие поля: Object[] elementData, int size. Объясните, зачем хранить отдельно size, если всегда можновзять elementData.length?
Размер массива elementData представляет собой вместимость (capacity) ArrayList, которая всегда больше переменной size - реального количества хранимых элементов. С добавлением новых элементов вместимость автоматически возрастает при необходимости.
- LinkedList - это односвязный, двусвязный или четырехсвязный список?
Двухсвязный список: каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.
1). Чуть добавлю про Vector и Hashtable. Хоть они официально и не deprecated, их реализация оставляет желать лучшего. Синхронизация в них реализована для каждого метода по отдельности, а обычно требуется выполнить целую последовательность действий.
ОтветитьУдалитьВ результате пример:
Один поток итеративно проходит по Вектору, второй что-то пытается изменить -> ConcurrentModificationException.
В итоге оборачиваем Vector в еще один блок синхронизации -> двойной проигрыш в производительности.
Один вопрос к Вам:
посмотрел реализацию Collections.SynchronizedList
А чем это отличается от Vector за исключением того, что в SynchronizedList используют левый объект монитора, а в Vector синхронизируют методы (мьютекс - сам экземпляр класса)?
2). "ArrayList - его преимущество в навигации по коллекции." - будь я новичком, не понял бы. Лучше: доступ к элементам напрямую по индексу.
3). "И если при добавлении в ArrayList превышается его объем, размер массива увеличивается вдвое"
Не совсем, есть еще loadFactor (default - 0,75). То, есть capacity увеличится вдвое, когда кол-во элементов превысит loadFactor * capacity.
Vector это класс в Java, который уже устарел. Основная причина, по которой его еще используют это обратная совместимость с кодом разработанным на старых версиях Java.
УдалитьCollections.synchronziedList - это метод служебного класса Collections, который создает синхронизированную прокси для любой реализации List. Основное различие между Vector и SynchronizedList это способ использования. Для работы в многопоточной среде более рекомендуется использувать ArrayList с Collections.synchronizedList() чем Vector. Более подробно про их отличия можно почитать здесь.
2) Это про RandomAccess (подробнее здесь http://qaru.site/questions/380109/why-does-arraylist-implement-randomaccess-interface )
УдалитьВ ArrayList есть loadFactor? Где это проявляется?
УдалитьВ русском языке нет слова ихний исправьте
ОтветитьУдалитьНеобходимо, наверное, поправить вопрос о сравнении элементов коллекции, так как в зависимости от реализации не все используют equals() и hashcode(). Так, например, TreeMap сравнивает элементы с помощью compareTo() обьектов или compare() Comparator`a
ОтветитьУдалитьПривет, TreeMap - не коллекция)
Удалить"Почему Map не Collection?" - Все Collection реализуют интерфейс Iterable; Map - нет.
ОтветитьУдалитьВсе Collection реализуют интерфейс Collection.
Удалить