2.1. Структуры данных и алгоритмы Flashcards
(32 cards)
Что такое generics?
Generics — это механизм, позволяющий писать обобщённый код, работающий с различными типами данных, обеспечивая безопасность типов на этапе компиляции.
- Главное преимущество generics — обнаружение ошибок на этапе компиляции.
- Классы, интерфейсы и методы, использующие параметризованный тип, называются обобщенными.
Что такое wildcards?
Wildcard <?> - это подстановочный знак, передаваемый в качестве параметра типа, позволяющий работать с любым неизвестным типом.
- Можно читать данные как Object, но нельзя добавлять элементы (кроме null).
Что такое bounded wildcards?
Bounded wildcards — это ограничивающие подстановочные знаки, которые ограничивают допустимые типы параметров:
<? extends T> - ограничение типа сверху, реальный тип-параметр может быть T или его подкласс.
- Можно читать данные как T, но нельзя ничего добавлять (кроме null).
<? super T> - ограничение типа снизу, реальный тип-параметр может быть T и его суперкласс.
- Можно добавлять T и его подклассы, но читать только как Object.
Важно: не использовать wildcard, если нужно одновременно читать и добавлять.
Что такое unbounded wildcards?
Unbounded wildcards <?> представляют неизвестный тип без ограничений.
-
<?>- используется, когда тип данных неизвестен и не требуется изменять содержимое коллекции. - Можно только читать как Object, но нельзя добавлять элементы (кроме null).
Где хранится информация про Generics?
- Информация о Generics существует только в исходном коде и используется компилятором для проверки типов.
- При компиляции параметры типов стираются и заменяются на Object (или на ограничивающий тип), а компилятор добавляет приведения (cast) типов.
- В байт-коде Generics отсутствуют — это сделано для совместимости со старым кодом.
Как можно получить тип Generics?
- Параметр типа доступен с помощью рефлексии, но только если тип явно задан в суперклассе.
- Если параметр типа не указан явно (например
<T>или Wildcard<?>), тогда он в рантайм недоступен из-за стирания типов. - Получить тип суперкласса можно через метод getGenericSuperclass()
Что такое итератор? В чем разница между iterator и listIterator? Что такое fail-fast и fail-safe поведение итератора и в чем между ними разница? Когда возникает ConcurrentModificationException?
- Iterator - это специальный объект, реализующий интерфейс Iterator (hasNext(), next(), remove()) для последовательного перебора всех Collection.
- listIterator расширяет Iterator для двунаправленного перебора, только для List и добавляет методы add(), set(), nextIndex(), previousIndex().
Fail-fast и fail-safe - это тип поведения итератора:
- Fail-fast — выбрасывает ConcurrentModificationException, если коллекция изменена во время итерации без использования методов итератора.
- Fail-safe — работает в многопоточной среде, создаёт копию коллекции, но изменения не отражаются во время перебора, не выбрасывает ConcurrentModificationException.
modCount меняется при любом изменении коллекции. Если изменение сделано через итератор, expectedModCount обновляется, и ошибки не возникает. Эти значения сравниваются при каждом вызове next(), и если они различаются — выбрасывается ConcurrentModificationException.
Что такое коллекции?
Коллекции — это структуры данных для хранения ссылочных типов данных.
На вершине иерархии в Java Collections Framework располагаются два интерфейса: Iterable и Map.
Назовите базовые интерфейсы коллекций?
- Iterable – базовый интерфейс для всех коллекций (кроме Map).
- Collection - расширяет Iterable.
- List - элементы упорядочены, доступ по индексу, может содержать дубликаты.
- Set - не допускает дубликаты, не сохраняет порядок вставки, кроме LinkedHashSet и TreeSet (упорядочен по естественному порядку или компаратору).
-
Queue - очередь, реализованная по принципу FIFO.
Deque - двусторонняя очередь, поддерживает FIFO и LIFO.
Map - не расширяет Collection, предназначен для хранения пар ключ-значение, ключи уникальны.
Расскажите реализации интерфейса List?
List — упорядочен по порядку вставки элементов, допускаются дубликаты и доступ по индексу.
- ArrayList — основан на динамическом массиве, упорядочен, быстрый O(1) доступ по индексу.
- LinkedList – основан на двусвязном списке, упорядочен, доступ по индексу медленнее O(n), чем у ArrayList, но быстрое добавление/удаление O(1) в начало и конец списка.
- Vector - похож на ArrayList, но более медленный из-за синхронизации методов для потокобезопасности.
Расскажите реализации интерфейса Set?
Set - неупорядоченный набор уникальных элементов.
- HashSet - основан на хеш-таблице, неупорядочен, быстрый доступ к элементам O(1) за счет хеш-функции.
- LinkedHashSet - основана на хеш-таблице O(1) и двусвязном списке, упорядочен по порядку вставки элементов.
- TreeSet - основана на красно-чёрном дереве O(log n), упорядоченная по Natural Order или Comparator.
Расскажите реализации интерфейса Map?
Map - хранит пары “ключ-значение”, где каждый ключ уникален.
- HashMap – основан на хеш-таблице O(1), неупорядочен.
- LinkedHashMap – основана на хеш-таблице и двусвязном списке, время доступа O(1), упорядочен по порядку вставки элементов.
- TreeMap – основан на красно-чёрном дереве O(log n), ключи упорядочены по Natural Order или Comparator.
- WeakHashMap - основан на хеш-таблице O(1) с использованием weak references. GC автоматически удаляет элемент, если на ключ нет ссылок.
Отличие ArrayList от LinkedList?
- ArrayList — основан на динамическом массиве, быстрый доступ по индексу O(1), медленное удаление/вставка O(n) т.к. необходимо каждый раз сдвигать элементы.
- LinkedList – основан на двусвязном списке, упорядочен, доступ по индексу медленнее O(n), чем у ArrayList, но быстрое добавление/удаление O(1) в начало и конец списка. Требуется дополнительная память на хранение ссылок на предыдущий и следующий элемент из-за этого более затратный по памяти, чем ArrayList.
Отличие Set от List?
- Set - гарантирует уникальность элементов, неупорядочен, нет доступа по индексу.
- List - допускает дубликаты, хранит элементы в порядке добавления, поддерживает доступ по индексу.
Расскажите про методы Object hashCode и equals?
- equals() - проверяет два объекта на равенство.
- hashCode() - вычисляет хэш-код, который характеризует текущее состояние объекта. Необходим для работы с хеш-таблицами HashMap, HashSet.
Контракт между equals и hashCode:
- Если два объекта равны по equals, их хэш-код должен совпадать, поэтому при переопределении equals() всегда нужно переопределять и hashCode().
- Если у двух объектов одинаковый хэш-код, то они не обязательно равны по equals (разные объекты могут иметь одинаковый хэш-код).
Расскажите, что такое коллизии в Map? Как с ними бороться?
Коллизия – это ситуация, когда разные ключи попадают в один бакет хеш-таблицы, потому что их хеш-коды приводят к одинаковому индексу.
Причины коллизий:
- Одинаковый индекс бакета у разных ключей с разным хеш-кодом.
- Ограничение на количество значений типа int (2^32).
Решения:
- Следовать контракту между equals и hashCode: для этого при переопределении equals() всегда переопределять hashCode().
- Использовать метод Objects.hash() при переопределении hashCode(), учитывая только те поля, которые используются в equals().
Запомнить: Когда количество элементов в одном бакете превышает 8 и размер хеш-таблицы (capacity) больше 64, LinkedList в бакете заменяется на красно-черное дерево. O(n) → O(log n).
Расскажите, что такое анализ алгоритма?
Анализ алгоритма — это процесс оценки его эффективности по времени выполнения и затрачиваемой памяти в зависимости от размера входных данных.
Измеряется в нотации Big O:
- O(1) – константное время
- O(log n) – логарифмическое время
- O(n) – линейное время
- O(n²) – квадратичное время
- O(2^n) — экспоненциальное время
- O(n!) — факториальное время
Правила определения сложности:
- Операции, которые не зависят от количества обрабатываемых данных, не учитываются.
- Сложность операций, которые зависят от количества обрабатываемых данных, и расположены последовательно, складываются.
- Сложность операций, которые зависят от количества обрабатываемых данных, и расположены внутри друг друга, перемножаются.
- Постоянные коэффициенты перед одинаковыми сложностями не учитываются.
- В итоговой формуле оставляем только элемент с наибольшей сложностью.
Какая временная сложность алгоритмов (О-нотация) добавления, замены и удаления в каждой из коллекций? С чем связаны отличия?
List: упорядочен по порядку вставки элементов, допускаются дубликаты и доступ по индексу.
ArrayList основан на динамическом массиве:
- добавление (add): O(n) из-за сдвига.
- замена (set): O(1) быстрый доступ по индексу.
- удаление (remove): O(n) из-за сдвига.
LinkedList основан двусвязном списке:
- добавление (add): в начало/конец O(1), по индексу O(n) (обход списка).
- замена (set): O(n) (поиск узла).
- удаление (remove): в начале/конце O(1), по индексу O(n).
Set: неупорядоченный набор уникальных элементов, нет доступа по индексу.
HashSet основан на хеш-таблице:
- добавление (add): O(1), но O(log n) при коллизиях (Java 8+).
- замена (set): отсутствует (удалить и добавить заново).
- удаление (remove): O(1), при коллизиях O(log n).
LinkedHashSet основан на хеш-таблице и двусвязном списке, гарантирует порядок вставки элементов:
- добавление (add): O(1), как у HashSet.
- замена (set): отсутствует (удалить и добавить заново).
- удаление (remove): O(1).
TreeSet основан на красно-черном дереве, гарантирует упорядоченность ключей по NaturalOrder или Comparator:
- добавление (add): O(log n).
- замена (set): отсутствует (удалить и добавить заново).
- удаление (remove): O(log n).
Queue: упорядочена, работает по принципу FIFO или с приоритетом.
LinkedList основан на двусвязном списке:
- добавление (add/offer): O(1) в начало/конец.
- замена (set): O(n) (поиск узла).
- удаление (remove/poll): O(1) (начало/конец).
PriorityQueue основан на двоичной куче (Heap):
- добавление (add/offer): O(log n) (поддержка кучи).
- замена (set): отсутствует.
- удаление (remove/poll): O(log n).
ArrayDeque реализует двустороннюю очередь (Deque), поддерживает FIFO и LIFO:
- добавление (addFirst/addLast): O(1).
- замена (set): отсутствует.
- удаление (removeFirst/removeLast): O(1).
Map: хранит пары “ключ-значение”, каждый ключ уникален.
HashMap основан на хеш-таблице:
- добавление (put): O(1), но O(log n) при коллизиях.
- замена (put): O(1).
- удаление (remove): O(1), при коллизиях O(log n).
LinkedHashMap основан на хеш-таблице и двусвязном списке, гарантирует порядок вставки элементов:
- добавление (put): O(1), как у HashMap.
- замена (put): O(1).
- удаление (remove): O(1).
TreeMap основан на красно-чёрном дереве, гарантирует упорядоченность ключей по NaturalOrder или Comparator:
- добавление (put): O(log n).
- замена (put): O(log n).
- удаление (remove): O(log n).
Вывод
- Для быстрого доступа по индексу → ArrayList O(1).
- Для быстрого удаления и вставки → LinkedList, HashSet, HashMap O(1).
- Для уникальных элементов → Set (HashSet – без порядка, TreeSet – упорядоченный).
- Для гарантированной упорядоченности → TreeSet, TreeMap O(log n).
- Для приоритетной обработки → PriorityQueue O(log n).
- Для очередей (FIFO/LIFO) → LinkedList, ArrayDeque O(1).ч
Расскажите реализации данных очередей и стеков.
Для стеков и очередей лучше ArrayDeque, т.к. он использует массив в виде кольцевого буфера, что позволяет добавлять и удалять элементы с обоих концов за O(1).
Интерфейс Queue (FIFO) - очередь.
- ArrayDeque — предпочтительный вариант (быстрее, меньше памяти, кеш-френдли).
- LinkedList - хранит указатели (next и prev), что увеличивает расход памяти.
- PriorityQueue - реализована на бинарной куче (бинарное дерево), добавление/удаление — O(log n).
Интерфейс Deque (LIFO и FIFO) - двунаправленная очередь.
- ArrayDeque - быстрее и эффективнее LinkedList.
- LinkedList - хранит указатели (next и prev), что увеличивает расход памяти.
Расскажите про реализации деревьев.
- TreeSet - реализация Set на красно-черном дереве. Значения уникальны, отсортированы в естественном порядке или по компаратору. Время доступа всегда O(log n).
- TreeMap - реализация Map на красно-черном дереве. Ключи отсортированы в естественном порядке или по компаратору. Время доступа всегда O(log n).
Что такое loadFactor?
Load factor (коэффициент загрузки) — параметр в HashMap, который определяет, при какой заполненности нужно увеличить размер внутреннего массива.
- По умолчанию loadFactor = 0.75 (75%). Когда число элементов превышает 75% от текущей емкости, HashMap увеличивает размер в 2 раза и производит рехеширование.
- Высокий loadFactor увеличивает вероятность коллизий и снижает скорость, но экономит память.
- Низкий loadFactor уменьшает коллизии, но требует больше памяти.
Перечислите побитовые логические операции, которые Вы знаете? Расскажите, как они работают.
Побитовое OR (|):
- В результирующий бит будет записана 1, если хотя бы один из операндов равен 1.
Побитовое AND (&):
- В результирующий бит будет записана 1, если оба операнда равны 1.
Побитовое XOR «Исключающее ИЛИ» (^):
- В результирующий бит будет записана 1, если операнды различны (один 0, другой 1).
Побитовое NOT (~):
- Инвертирует все биты числа инвертируются (0 → 1, 1 → 0).
Расскажите про операции сдвига. Какие они бывают и что делают?
Сдвиг влево («) – эквивалентен умножению на 2.
- Младшие биты заполняются 0, старшие отбрасываются.
- 27 (11011) «_space;1 = 54 (110110).
Знаковый сдвиг вправо (») – эквивалентен делению на 2.
- Сохраняет знак, старшие биты дополняются 0 (для +) или 1 (для -).
- 24 (11000)»_space; 1 = 12 (1100).
Беззнаковый сдвиг вправо (»>) – эквивалентен делению на 2, но без сохранения знака.
- Старшие биты всегда дополняются 0.
Как хранится знак числа в Java? Как хранятся отрицательные числа?
В двоичном представлении числа используется дополнительный код (two’s complement), где старший бит хранит знак числа:
- 0 - для положительных чисел.
- 1 - для отрицательных чисел.
Чтобы преобразовать положительное число в отрицательное, нужно:
- Инвертировать все биты.
- Прибавить 1 к результату.
