10 Сложность, структуры данных и коллекции в Java Flashcards
Что такое вычислительная сложность?
Вычисли́тельная сло́жность — понятие, обозначающее функцию зависимости объёма работы, от размера входных данных.
которая выполняется некоторым алгоритмом,
Какие ресурсы можно оценить с помощью вычислительной сложностью?
Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти.
O(1) – константная сложность O(n) - линейная сложность O(log n) - логарифмическая сложность O(n*log(n)) - квазилинейная сложность O(n2) - квадратичная сложность O(2^n) - экспоненциальная сложность.
Что такое структура данных?
Это программная единица,
позволяющая хранить и
обрабатывать данные
например массив
Какие операции оценивают в структурах данных?
● Доступ
● Вставка
● Поиск
● Удаление
Опишите структуру классов и интерфейсов Collections в java?
Коллекция - это контейнер однотипных элементов.
Collection: базовый интерфейс для всех коллекций и других интерфейсов коллекций (является обобщенным и расширяет интерфейс Iterable, поэтому все объекты коллекций можно перебирать в цикле по типу for-each.)
основные интерфейсы:
List: наследует интерфейс Collection и представляет функциональность простых списков
Queue: Очередь - АТД с дисциплиной доступа к элементам
«первый пришёл — первый вышел» (FIFO, first in,
first out). Добавление элемента возможно лишь в
конец очереди, выборка — только из начала
очереди, при этом выбранный элемент из очереди
удаляется.
Set: также расширяет интерфейс Collection и используется для хранения множеств уникальных объектов
остальные;
Deque: наследует интерфейс Queue и представляет функционал для двунаправленных очередей
SortedSet: расширяет интерфейс Set для создания сортированных коллекций
NavigableSet: расширяет интерфейс SortedSet для создания коллекций, в которых можно осуществлять поиск по соответствию
Классов коллекций - списки, множества, очереди, отображения и другие, среди которых можно выделить следующие:
ArrayList: простой список объектов
LinkedList: представляет связанный список
ArrayDeque: класс двунаправленной очереди, в которой мы можем произвести вставку и удаление как в начале коллекции, так и в ее конце
HashSet: набор объектов или хеш-множество, где каждый элемент имеет ключ - уникальный хеш-код
TreeSet: набор отсортированных объектов в виде дерева
LinkedHashSet: связанное хеш-множество
PriorityQueue: очередь приоритетов
HashMap: структура данных в виде словаря, в котором каждый объект имеет уникальный ключ и некоторое значение
TreeMap: структура данных в виде дерева, где каждый элемент имеет уникальный ключ и некоторое значение
Схематично всю систему коллекций вкратце можно представить следующим образом:
Интерфейсы коллекций в Java
2 интерфейса: Collection и Map. Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части
по типу хранения данных:
простые последовательные наборы элементов и наборы пар «ключ — значение» (словари).
Расскажите про интерфейсы Iterator и Iterable? В чем их особенность?
java.lang.Iterable — интерфейс стандартной библиотеки Java. все коллекции можно перебирать, организовав цикл for в стиле for each.
пример — массивы и коллекции (такая конструкция позволяет перечислить все элементы массива или коллекции).
Интерфейс Iterable содержит один метод iterator(), возвращающий объект типа Itaretor.
java.util.Iterator — интерфейс, описывающий свойства “итератора”. .Если в качестве объекта, по которому мы итерируемся, выступает, например, массив, то итератор может хранить индекс, на котором мы сейчас находимся.
Содержит 3 метода:
E next() — вернуть значение следующего элемента и сдвинуть итератор "вперед" boolean hasNext() — вернуть true, если пройдены еще не все элементы, и false в противном случае
void remove - удаление текущего эллимента
Collection является подинтерфейсом Iterable (т е по любой Collection можно проитерироваться, перебрав все элементы).
Какие реализации List вы знаете и чем они отличаются?
ArrayList и LinkedList
ArrayList это список, реализованный на основе массива, Размер по умолчанию - 10.
а LinkedList — это двунаправленный связный список , основанный на объектах с ссылками между ними, доступно добавление и удаление из середины, доступ по индексу.
обращение к значению происходит за линейное время O(n), а из начала и конца за константное O(1)
данную коллекцию можно использовать как стек или очередь.
ArrayList (реализует List): является реализацией динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента.
коллекция автоматически расширяется (размер*1.5 + 1). А когда из коллекции удаляются объекты, она может сокращаться (trimToSize()).
Данную реализацию следует применять, если в процессе работы с коллекцией предплагается частое обращение к элементам по индексу. Из-за особенностей реализации поиндексное обращение к элементам выполняется за константное время O(1). Но данную коллекцию рекомендуется избегать, если требуется частое удаление/добавление элементов в середину коллекции.
Какое поведение описывает интерфейс Map?
Map: предназначен для созданий структур данных в виде словаря, где каждый элемент имеет определенный ключ и значение. В отличие от других интерфейсов коллекций не наследуется от интерфейса Collection перебрать содержимое отображения, организовав цикл for в стиле for each, не удастся.
SortedMap: расширяет интерфейс Map. Он обеспечивает размещение записей
в отображении по порядку нарастания ключей.
NаvigableMap: расширяет интерфейс SortedMap и определяет поведение
отображения, поддерживающего извлечение записей из него по наиболее
точному совпадению с заданным ключом или несколькими ключами.
Сохранив значение по ключу, можно получить его обратно по этому же ключу.
они не реализуют интерфейс Iterable. Это означает, что перебрать содержимое отображения, организовав цикл for в стиле for each, не удастся.
абстрактный класс
AbstractMap: применяет интерфейс Map, предназначен для создания наборов по типу словаря с объектами в виде пары “ключ-значение”
Как внутри реализован HashMap?
HashMap — это ассоциативный массив. реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение).Ключи и значения могут быть любых типов, в том числе и null.
HashMap состоит из «корзин» - элементов массива, которые хранят ссылки на списки элементов. При добавлении новой пары ключ-значение, вычисляет хеш-код ключа, на основании которого вычисляется номер корзины (номер ячейки массива), в которую попадет новый элемент.
Если корзина пустая, то в нее сохраняется ссылка на вновь добавляемый элемент, если же там уже есть элемент, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент.
Если в списке был найден элемент с таким же ключом, то он заменяется. Добавление, поиск и удаление элементов выполняется за константное время.
хеш-функций должна равномерно распределять элементы по корзинам, в этом случае временная сложность для этих 3 операций будет не ниже lg N, а в среднем случае как раз константное время.
Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек.
HashMap содержит массив Node и Node может представлять класс, содержащий объекты: int — хэш K — ключ V — значение Node — следующий элемент
начальное 16 корзин
Как между собой связаны методы equals и hashCode?
hashCode позволяет определить корзину для поиска элемента, а equals используется для сравнения ключей элементов в списке внутри корзины и искомого ключа.
equals - сравнивает ссылки (что эквивалентно ==)
hashCode - возвращает номер ячейки в памяти, где хранится объект
В классе Object, который является родительским классом для объектов java, определен метод hashCode(), позволяющий получить уникальный целый номер для данного объекта. Когда объект сохраняют в коллекции типа HashSet, то данный номер позволяет быстро определить его местонахождение в коллекции и извлечь.
Поскольку Set содержит только уникальные объекты, то внутри HashSet должен быть только один экземпляр. Чтобы этого достичь, объекты должны возвращать одинаковый hashCode. То есть нам необходимо переопределить также функцию hashCode() вместе с equals().
Что такое Set и как он реализован внутри?
Интерфейс Set расширяет интерфейс Collection и представляет набор уникальных элементов. Set не добавляет новых методов, только вносит изменения в унаследованные. В частности, метод add() добавляет элемент в коллекцию и возвращает true, если в коллекции еще нет такого элемента
В этом интерфейсе не
определяется никаких дополнительных методов. Интерфейс Set является обобщенным
и объявляется приведенным ниже образом, где Е обозначает тип объектов,
которые должно содержать множество.
interface Set
Основаны на HashMap
