10. Сложность, структуры данных и коллекции в Java Flashcards
Что такое вычислительная сложность?
Вычисли́тельная сло́жность — понятие, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.
Какие ресурсы можно оценить с помощью вычислительной сложностью?
Оценивается время исполнения алгоритма (временнАя сложность алгоритма) и объём необходимой памяти (пространственная сложность алгоритма)
Что такое структура данных?
Это программная единица, позволяющая хранить и обрабатывать данные
Какие операции оценивают в структурах данных?
● Доступ
● Вставка
● Поиск
● Удаление
Опишите структуру классов и интерфейсов Collections в java?
В основе всех коллекций лежит применение того или иного интерфейса, который определяет базовый функционал.
Среди этих интерфейсов можно выделить следующие:
Collection: базовый интерфейс для всех коллекций и других интерфейсов коллекций
Queue: наследует интерфейс Collection и представляет функционал для структур данных в виде очереди
Deque: наследует интерфейс Queue и представляет функционал для двунаправленных очередей
List: наследует интерфейс Collection и представляет функциональность простых списков
Set: также расширяет интерфейс Collection и используется для хранения множеств уникальных объектов. Основаны на HashMap
SortedSet: расширяет интерфейс Set для создания сортированных коллекций
NavigableSet: расширяет интерфейс SortedSet для создания коллекций, в которых можно осуществлять поиск по соответствию
Помимо перечисленных выше интерфейсов, для составления коллекций используются
интерфейсы Comparator, RandomAccess, Iterator, ListIterator и Spliterator. Если кратко, то интерфейс Comparator определяет два сравниваемых объекта, а интерфейсы Iterator, ListIterator и Spliterator перечисляют объекты в коллекции. Если же список реализует интерфейс RandomAccess, то тем самым
он поддерживает эффективный произвольный доступ к своим элементам.
———————————————————————————-
Map: Интерфейс Mapотображает однозначные ключи на значения. Ключ - это объект,
используемый для последующего извлечения данных. Задавая ключ и значение,
можно размещать значение в отображении, представленном объектом типа
Map. Сохранив значение по ключу, можно получить его обратно по этому же ключу.
Интерфейс Mapявляется обобщенным и объявляется приведенным ниже образом,
где К обозначает тип ключей, а V - тип хранимых в отображении значений.
interface Map
В отношении отображений необходимо иметь в виду следующее: они не реализуют интерфейс Iterable. Это означает, что перебрать содержимое отображения, организовав цикл for в стиле for each, не удастся.
SortedMap: расширяет интерфейс Map. Он обеспечивает размещение записей
в отображении по порядку нарастания ключей.
NаvigableMap: расширяет интерфейс SortedMap и определяет поведение
отображения, поддерживающего извлечение записей из него по наиболее
точному совпадению с заданным ключом или несколькими ключами.
С помощью применения вышеописанных интерфейсов и абстрактных классов в Java реализуется широкая палитра классов коллекций - списки, множества, очереди, отображения и другие, среди которых можно выделить следующие:
ArrayList (реализует List): поддерживает динамические массивы, которые наращиваются по мере надобности.
LinkedList (реализует List, Deque): представляет связанный список.
ArrayDeque (реализует Deque): класс создает динамический массив, не имеющий ограничений по ёмкости. Имеет структуру двунаправленной очереди.
HashSet (реализует Set): набор объектов или хеш-множество (используется хеш таблица), где каждый элемент имеет ключ - уникальный хеш-код. Хеш код используется как индекс, по которому сохраняются данные.
TreeSet (реализует NavigableSet): набор отсортированных по нарастающей объектов в виде дерева. Время доступа и извлечения элементов достаточно мало, благодаря чему класс T r e e S e t оказывается отличным выбором для хранения больших объемов отсортированных данных, которые должны быть быстро найдены.
LinkedHashSet (реализует HashSet): связанное хеш-множество. В классе LinkedHashSet поддерживается связный список элементов хеш-множества в том порядке, в каком они введены в него. Это позволяет организовать итерацию с вводом элементов в определенном порядке.
PriorityQueue (реализует Queue): Он служит для создания очереди по приоритетам на основании компаратора очереди.
HashMap: расширяет класс AbstractMap и реализует интерфейс Map. В нем используется хеш-таблица для хранения хешируемого отображения, и благодаря этому обеспечивается постоянное время выполнения методов get() и put() даже при манипулировании крупными отображениями.
TreeMap: расширяет класс AbstractMap и реализует интерфейс NаvigableMap. В нем создается отображение, размещаемое в древовидной структуре. В классе TreeMap предоставляются эффективные средства для хранения пар “ключ - значение” в отсортированном порядке и обеспечивается их быстрое извлечение. Следует, однако, иметь в виду, что, в отличие от хеш-отображения, древовидное отображение гарантирует, что его элементы будут отсортированы по порядку нарастания ключей.
LinkedHashMap: расширяет класс HashMap. Он создает связный список элементов, располагаемых в отображении в том порядке, в котором они вводились в него. Это позволяет организовать итерацию с вводом элементов в отображение
в определенном порядке. Следовательно, при итерации представления отображения типа LinkedHashMap в виде коллекции его элементы будут возвращаться в том порядке, в котором они вводились в него. Можно также создать отображение
типа LinkedHashMap, возвращающее свои элементы в том порядке, в котором
к ним осуществлялся доступ в последний раз.
Hashtable: Он подобен классу HashMap, но синхронизирован. Является конкретной
реализацией класса Dictionary.
Расскажите про интерфейсы Iterator и Iterable? В чем их особенность?
Интерфейс Collection расширяет интерфейс Iterable. Это означает, что все коллекции можно перебирать, организовав цикл for в стиле for each.
Только те классы, которые реализуют интерфейс Iterable, позволяют перебирать их элементы в этом цикле. имеет всего один метод public Iterator iterator().
Интерфейс Iterator, определяющий итератор, который обеспечивает общий, стандартизованный
способ поочередного доступа к элементам коллекций. Иными словами, итератор предоставляет способ перебора содержимого коллекций. А поскольку каждая коллекция предоставляет свой итератор, то элементы любого класса коллекций могут быть доступны с помощью методов, определенных в интерфейсе Iterator. Таким образом, код, перебирающий в цикле элементы множества,
можно с минимальными изменениями применить, например, для перебора элементов списка.
Какие реализации List вы знаете и чем они отличаются?
ArrayList (реализует List): поддерживает динамические массивы, которые наращиваются по мере надобности. Размер по умолчанию - 10.
По существу, класс ArrayList представляет собой списочный
массив объектных ссылок переменной длины. Это означает, что размер объекта типа ArrayList может динамически увеличиваться или уменьшаться. Списочные массивы создаются с некоторым начальным размером. Когда же этого первоначального размера оказывается недостаточно, коллекция автоматически расширяется (размер*1.5 + 1). А когда
из коллекции удаляются объекты, она может сокращаться (trimToSize()).
LinkedList (реализует List, Deque): представляет связанный список.
Какое поведение описывает интерфейс Map?
Интерфейс Mapотображает однозначные ключи на значения. Ключ - это объект,
используемый для последующего извлечения данных. Задавая ключ и значение,
можно размещать значение в отображении, представленном объектом типа
Map. Сохранив значение по ключу, можно получить его обратно по этому же ключу.
Интерфейс Mapявляется обобщенным и объявляется приведенным ниже образом,
где К обозначает тип ключей, а V - тип хранимых в отображении значений.
interface Map
В отношении отображений необходимо иметь в виду следующее: они не реализуют интерфейс Iterable. Это означает, что перебрать содержимое отображения, организовав цикл for в стиле for each, не удастся.
Как внутри реализован HashMap?
Этот класс реализует интерфейс Map. В нем используется хеш-таблица для хранения хешируемого отображения, и благодаря
этому обеспечивается постоянное время выполнения методов get ( ) и put () даже при манипулировании крупными отображениями. Класс HashMap является
обобщенным и объявляется приведенным ниже образом, где К обозначает тип ключей, а V - тип хранимых в отображении значений.
class HashMap
В классе HashMap определены следующие конструкторы:
HashMap()
HashMap(Map extends К, ? extends V> т)
HashMap(int емкость)
HashMap(int емкость, float коэффициент_заполнения)
В первой форме конструктора создается хеш-отображение по умолчанию. Во второй форме конструктора хеш-отображение инициируется элементами заданного отображения т. В третьей форме задается емкость хеш-отображения.
А в четвертой форме емкость и коэффициент_заполнения хеш-отображения
задаются в качестве аргументов конструктора. Назначение емкости и коэффициента
заполнения такое же, как и в описанном ранее классе HashSet. По умолчанию емкость составляет 16, а коэффициент заполнения - 0.75.
Класс HashMap реализует интерфейс Map и расширяет класс AbstractMap, не дополняя их своими методами. Следует, однако, иметь в виду, что хеш-отображение не гарантирует порядок расположения своих элементов. Следовательно, порядок, в котором элементы вводятся в хеш-отображение, не обязательно соответствует тому порядку, в котором они извлекаются итератором.
Как между собой связаны методы equals и hashCode?
В классе Object, который является родительским классом для объектов java, определен метод hashCode(), позволяющий получить уникальный целый номер для данного объекта. Когда объект сохраняют в коллекции типа HashSet, то данный номер позволяет быстро определить его местонахождение в коллекции и извлечь.
Поскольку Set содержит только уникальные объекты, то внутри HashSet должен быть только один экземпляр. Чтобы этого достичь, объекты должны возвращать одинаковый hashCode. То есть нам необходимо переопределить также функцию hashCode() вместе с equals().
Что такое Set и как он реализован внутри?
В интерфейсе Set определяется множество. Он расширяет интерфейс Collection и определяет поведение коллекций, не допускающих дублирования элементов. Таким образом, метод
add () возвращает логическое значение false
при попытке ввести в множество дублирующий элемент. В этом интерфейсе не
определяется никаких дополнительных методов. Интерфейс Set является обобщенным
и объявляется приведенным ниже образом, где Е обозначает тип объектов,
которые должно содержать множество.
interface Set
Основаны на HashMap
