Деревья списки хеш адресация это
Структуры данных — это специальные средства организации и хранения данных на компьютерах таким образом, чтобы операции над сохраненными данными можно было выполнять более эффективно. Они широко применяются в программировании.
Структуры данных используются практически в каждой программе. Это основа программирования. Поэтому неудивительно, что это ключевая тема для вопросов на собеседованиях на вакансию разработчика. Так что будучи этим самым разработчиком, вы должны хорошо разбираться в структурах данных.
В этой статье я коротко объясню, что из себя представляют 8 часто используемых структур данных, о которых должен знать каждый программист.
5. Хеш-таблицы
Хеш-таблица — это структура данных, которая хранит значения, доступ к которым получается с помощью связанного с этими значениями ключами. В хеш-таблицах эффективно работает поиск, при условии, что мы знаем ключ, связанный с нужным значением. Поэтому вставлять и искать данные при работе с хеш-таблицами — просто, независимо от размера этих данных.
Прямая адресация памяти использует взаимно-однозначное сопоставление между значениями и ключами, когда данные сохраняются в обычной таблице. Однако при большом количестве пар ключ-значение может возникнуть проблема. С таким количеством записей таблице будет огромной, поэтому ее будет непрактично и даже невозможно сохранить, учитывая объем доступной памяти на обычном компьютере. Чтобы избежать этой проблемы, мы и используем хеш-таблицы.
Операции над связными списками
- Поиск: найти первое вхождение элемента с ключом k в данном связанном списке простым линейным поиском и вернуть указатель на этот элемент.
- Вставка: вставить ключ в связанный список. Это можно сделать 3 разными способами: вставка в начало списка, вставка в конец списка и вставка в середину.
- Удаление: удалить элемент x из данного связного списка. Аналогично 3 способами: удалить из начала, конца и середины. Удалить узел за раз невозможно.
Массивы
Это наипростейшие и широко используемые структуры данных, в которых элементы следуют один за другим. Представляет собой контейнер, в котором может храниться фиксированное количество однотипных компонентов.
- элементами называют все компоненты, хранящиеся в массиве;
- индексы – местонахождение каждого элемента в массиве выражается целым числовым индексом, используемом для его идентификации.
Размерность массива определяет количество индексов в нем. Они бывают одномерными (называют векторами) и многомерными (массив в середине массива). Массивы могут объявляться разными способами на различных языках программирования.
Некоторые структуры являются производными массивов (стеки, очереди). В массиве каждый элемент имеет индекс (положительное целое числовое значение), соответствующий тому, какую позицию в массиве он занимает.
Язык программирования определяет, с какого значения в массиве начинается нумерация. Во многих языках начальным индексом массива определен 0.
- статическими — характеризуются однородностью данных;
- динамическими – характеризуются непостоянством размера, который может меняться в ходе выполнения программы. Это усложняет процесс, ухудшает быстроту действий, но работа с информацией становится более гибкой;
- гетерогенными – характеризуется неоднородностью данных.
Основные операции, которые поддерживаются массивами:
- Traverse – выставляет один за одним все компоненты массива;
- Insert – добавляет один или несколько элементов по указанному индексу;
- Get – производит возврат элемента по указанному индексу;
- Delete – выполняет удаление элемента по указанному индексу;
- Size – позволяет узнать общую численность элементов, содержащихся в массиве.
Какие бывают?
Линейные, элементы образуют последовательность или линейный список, обход узлов линеен. Примеры: Массивы. Связанный список, стеки и очереди.
Нелинейные, если обход узлов нелинейный, а данные не последовательны. Пример: граф и деревья.
3. Связный список (связанный, список узлов и ссылок или указателей) (Linked List)
Буквально, связный список — это цепочечная структура данных, где каждый узел состоит из двух частей: данных узла и указателя на следующий узел. Связный список и условный массив являются линейными структурами данных с сериализованным хранилищем. Отличия состоят в следующем:
Критерий | Массив | Список |
---|---|---|
Выделение памяти | Статическое, происходит последовательно во время компиляции | Динамическое, происходит асинхронно во время запуска (выполнения) |
Получение элементов | Поиск по индексу, высокая скорость | Поиск по всем узлам очереди, скорость менее высокая |
Добавление/удаление элементов | В связи с последовательным и статическим распределением памяти скорость ниже | В связи с динамическим распределением памяти скорость выше |
Структура | Одно или несколько направлений | Однонаправленный, двунаправленный или циклический |
Односвязный список имеет следующие методы:
- size: вернуть количество узлов
- head: вернуть первый элемент (head — голова)
- add: добавить элемент в конец (tail — хвост)
- remove: удалить несколько узлов
- indexOf: вернуть индекс узла
- elementAt: вернуть узел по индексу
- addAt: вставить узел в определенное место (по индексу)
- removeAt: удалить определенный узел (по индексу)
8. Графы
Граф состоит из конечного множества вершин (vertex) и множества ребер (edge), соединяющих эти вершины.
Порядком графа называется число вершин в графе. Размер графа — количество ребер.
Два ребра называются смежными (adjacent), если они соединены одним ребром.
1. Массив
Массив — это структура данных с фиксированным размером, которая может содержать элементы одного и того же типа. Массив может состоять из целых чисел, чисел с плавающей точкой, строк или даже других массивов (двумерные массивы). Элементы массива индексируются, что позволяет получать произвольный доступ к значениям.
8. Граф (график) (Graph)
Граф, также известный как сеть (Network), представляет собой коллекцию связанных между собой узлов. Бывает два вида графов — ориентированный и неориентированный, в зависимости от того, имеют ли ссылки направление. Графы используются повсеместно, например, для расчета наилучшего маршрута в навигационных приложениях или для формирования списка рекомендаций в социальных сетях.
Графы могут быть представлены в виде списка или матрицы.
Список
В данном случае все родительские узлы располагаются слева, а их дочерние элементы справа.
Матрица
В данном случае узлы распределяются по строкам и столбцам, пересечение строки и столбца показывает отношение между узлами: 0 означает, что узлы не связаны между собой, 1 — узлы связаны.
Поиск по графу осуществляется двумя методами — поиск в ширину (Breath-First-Search, BFS) и поиск в глубину (Depth-First-Search, DFS).
На этом у меня все. Надеюсь, вы нашли для себя что-то полезное. Счастливого кодинга!
Предлагаем укрепить (или получить) знания о базовых структурах данных. Эти понятия являются основой всего, что связано с программами. Вспомните азы, а если не знаете – получите их. Они пригодятся в работе, а если есть цель найти ее, то и при прохождении интервью. Укажите, что вы знаете составляющие структуры данных, их применение, и это поможет в поиске работы. Потратив немного времени, вы приятно удивите интервьюера, начальника или коллег по работе.
Хэш-таблицы
Это структуры, реализующие интерфейс Map, позволяющий сохранять пару (ключ/ значение). Хеширование применяется для нахождения в массиве значения индекса, по которому будет найдено нужное значение.
При детальном рассмотрении можно увидеть, что хэш-таблица является массивом. В нем хэш-функция является индексом.
Коллизией называют хеширование двух вводов, имеющих одинаковый цифровой выход. Цель – уменьшение числа коллизий.
Когда в хэш-таблицу вводится пара ключ/ значение, с уникальным ключом проводится хеширование, после чего он становится числом. Оно в последствии используется в качестве фактического ключа, в котором это значение хранится. При повторной попытке получить доступ к этому же ключу, хеш-функция проведет его обработку и вернет то же числовое значение, которое в дальнейшем будет использовано для нахождения связанного значения. Это способствует быстрому поиску.
Производительность хеширования зависит от:
- функций хеширования;
- параметров хэш-таблиц;
- методов устранения коллизий.
Массивы
Массив — это самая простая и широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов.
Изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).
Каждому элементу данных присваивается положительное числовое значение (индекс), который соответствует позиции элемента в массиве. Большинство языков определяют начальный индекс массива как 0.
Бывают
Одномерные, как показано выше.
Многомерные, массивы внутри массивов.
Основные операции
- Insert-вставляет элемент по заданному индексу
- Get-возвращает элемент по заданному индексу
- Delete-удаление элемента по заданному индексу
- Size-получить общее количество элементов в массиве
Вопросы
- Найти второй минимальный элемент массива
- Первые неповторяющиеся целые числа в массиве
- Объединить два отсортированных массива
- Изменение порядка положительных и отрицательных значений в массиве
Основополагающие сведения о структурах данных
Классическая структура данных представляет собой определенный способ организации этих самых данных для дальнейшего эффективного использования. Это если кратко. В более развернутом виде – она представляет собой некую упаковку, в которой данные сохраняются в определенной «моделе».
Структуры данных делятся на:
- линейные (стеки, очереди, массивы) – элементы выстраиваются в последовательность либо линейный список. Также линейны и обходы узлов;
- нелинейные (графы, деревья) – данные выстраиваются без какой-либо последовательности. Также не линейны и обходы узлов.
Коснемся основных действий. Данные можно получить, найти, добавить, удалить. Для реализации этих целей существует много разнообразных структур данных. Каждая отдельно взятая более эффективна в одних вопросах и менее эффективна в других. Потому разработчик должен понимать функциональные составляющие каждой структуры. Грамотное применение функциональных свойств структуры данных ускорит решение любой поставленной задачи.
Приходится часто искать информацию – укажите одну разновидность. Если нужно постоянно что-либо вставлять – укажите другую. А если частенько приходится выполнять действия по перестановке и удалению – укажите третье решение.
Неориентированный граф
Граф G называют неориентированным (undirected graph), если все его ребра не имеют заданного направления.
Если вершина не является концом ни для одного ребра, она называется изолированной.
Деревья
Дерево-это иерархическая структура данных, состоящая из узлов (вершин) и ребер (дуг). Деревья по сути связанные графы без циклов.
Древовидные структуры везде и всюду. Дерево скилов в играх знают все.
- N дерево
- Сбалансированное дерево
- Дерево Бинарного Поиска
«Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. » — Procs
Три способа обхода дерева
- В прямом порядке (сверху вниз) — префиксная форма.
- В симметричном порядке (слева направо) — инфиксная форма.
- В обратном порядке (снизу вверх) — постфиксная форма.
Вопросы
- Найти высоту бинарного дерева
- Найти N наименьший элемент в двоичном дереве поиска
- Найти узлы на расстоянии N от корня
- Найти предков N узла в двоичном дереве
Что такое структура данных?
Структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.
Применение
- Используется для реализации индексов базы данных.
- Используется для реализации ассоциативных массивов.
- Используется для реализации множества.
5. Хеш-таблица (таблица кэширования) (Hash Table)
Хеш-таблица — это структура данных, которая строится по принципу ключ-значение. Из-за высокой скорости поиска значений по ключам, она используется в таких структурах, как Map, Dictionary и Object. Как показано на рисунке, хеш-таблица имеет hash function, преобразующую ключи в список номеров, которые используются как имена (значения) ключей. Время поиска значения по ключу может достигать O(1). Одинаковые ключи должны возвращать одинаковые значения — в этом суть функции хэширования.
Хеш-таблица имеет следующие методы:
- add: добавить пару ключ/значение
- remove: удалить пару
- lookup: найти значение по ключу
1. Стек (вызовов) (Stack)
- push: добавить новый элемент
- pop: удалить верхний элемент, вернуть его
- peek: вернуть верхний элемент
- length: вернуть количество элементов в стеке
Основные структуры данных.
- Массивы
- Стеки
- Очереди
- Связанные списки
- Графы
- Деревья
- Префиксные деревья
- Хэш таблицы
Применение стеков
- Используется для оценки выражений (например, алгоритм сортировочной станции для анализа и оценки математических выражений).
- Используется для реализации вызовов функций в рекурсивном программировании.
Хеш-функция
Для решения этой проблемы или при использовании прямой адресации используют специальную функцию — hash function (h).
При прямом доступе значение с ключом k сохраняется в слоте k. Используя хеш-функцию, мы вычисляем индекс таблицы (слота), в которую попадает каждое конкретное значение. Значение, вычисленное с помощью хеш-функции для данного ключа, называется хеш-значением, которое указывает индекс таблицы, в которой отображается искомое значение.
h: хеш-функция.
k: ключ, хеш-значение которого мы хотим определить.
m: размер хеш-таблицы (количество доступных слотов). Хорошим выбором для этой переменной будет простое значение, которое не находится на числовой прямой рядом со степенью двойки.
Рассмотрим хеш-функцию h(k)=k%20, где размер хеш-таблицы равен 20. Имея некий набор ключей, мы хотим рассчитать хеш-значение для каждого из них, чтобы определить индекс, по которому конкретный ключ должен находиться в таблице. Допустим, у нас есть следующие значения ключей, хеша и индексов хеш-таблицы:
- 1 → 1%20 → 1
- 5 → 5%20 → 5
- 23 → 23%20 → 3
- 63 → 63%20 → 3
Вы можете увидеть, что если хеш-функция генерирует один и тот же индекс для более чем одного ключа, может возникнуть ошибка. Она решается выбором подходящей хеш-функции h и использованием метода цепочек или метода открытой адресации .
Какие проблемы можно решить с помощью структуры данных
В связи с тем, что приложения становятся все более сложными, а количество составляющей информации в них постоянно растет, то возникают три проблемы:
- замедление процесса поиска в связи с ростом данных;
- ограниченная скорость процессоров. Несмотря на то, что она достаточно высокая, с ростом объема информации и она ограничивается;
- многократные запросы через поиск на веб-серверах вызывают сбои в их работе.
Структуры данных помогают в решение вышеперечисленных проблем. Данные можно организовать в структуры таким образом, что поиск будет осуществляться практически мгновенно.
Графы
Граф-это набор узлов (вершин), которые соединены друг с другом в виде сети ребрами (дугами).
Бывают
Ориентированный, ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
Неориентированные, к каждому из ребер можно осуществлять переход в обоих направлениях.
Смешанные
Встречаются в таких формах как
Общие алгоритмы обхода графа
- Поиск в ширину – обход по уровням
- Поиск в глубину – обход по вершинам
Вопросы
- Реализовать поиск по ширине и глубине
- Проверить является ли граф деревом или нет
- Посчитать количество ребер в графе
- Найти кратчайший путь между двумя вершинами
3. Стеки
Стек — это LIFO-структура (Last In, First Out — «последним пришёл — первым ушёл», способ организации данных, при котором к последнему элементу можно получить доступ в первую очередь), которая часто встречается в языках программирования. Структура получила название stack (в переводе с английского куча, стопка), потому что она похожа на стопку тарелок в реальной жизни.
Ориентированный граф
Граф G называется ориентированным (directed graph), если все его ребра имеют заданное направление, указывающее, какая вершина — начальная, а какая — конечная.
Дуга (u, v) начинается в вершине u и кончается в вершине v.
Петля (self-loop) — это ребро, которое начинается и заканчивается в одной и той же вершине.
Очереди
Подобно стекам, очередь — хранит элемент последовательным образом. Существенное отличие от стека – использование FIFO (First in First Out) вместо LIFO.
Пример очереди – очередь людей. Последний занял последним и будешь, а первый первым ее и покинет.
Изображение очереди, в четыре элемента (1, 2, 3 и 4), где 1 находится наверху и будет удален первым
Основные операции
- Enqueue—) — вставляет элемент в конец очереди
- Dequeue () — удаляет элемент из начала очереди
- isEmpty () — возвращает значение true, если очередь пуста
- Top () — возвращает первый элемент очереди
Вопросы
- Реализовать cтек с помощью очереди
- Реверс первых N элементов очереди
- Генерация двоичных чисел от 1 до N с помощью очереди
Основные виды структур
К основным видам структуры данных относятся:
Вместо заключения
Матчасть так же интересна, как и сами языки. Возможно, кто-то увидит знакомые ему базовые структуры и заинтересуется.
Спасибо, что прочли. Надеюсь не зря потратили время =)
PS: Прошу извинить, как оказалось, перевод статьи уже был тут и очень недавно, я проглядел.
Если интересно, вот она, спасибо Hokum, буду внимательнее.
Некоторое время назад я сходил на собеседование в одну довольно большую и уважаемую компанию. Собеседование прошло хорошо и понравилось как мне, так и, надеюсь, людям его проводившим. Но на следующий день, в процессе разбора полетов, я обнаружил, что в ходе собеседования ответ на как минимум один вопрос был неверен.
Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?
Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!
На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.
Причиной неверного ответа было то, что я не удосужился досконально изучить те структуры, которые лежат в основе работы с коллекциями моего любимого языка. Правда, по результатам опроса нескольких знакомых разработчиков, оказалось что это не только моя проблема, очень многие вообще не задумываются, как работают коллекции в их любимых ЯП. А ведь используем мы их каждый день и не по разу. Так родилась идея этой статьи.
1. Array — он же индексированный массив.
Array — это коллекция фиксированного размера, состоящая из элементов одинакового типа.
- get_element_at(i): сложность O(1)
- set_element_at(i, value): сложность O(1)
Почему время доступа к элементу по индексу постоянно? Массив состоит из элементов одного типа, имеет фиксированный размер и располагается в непрерывной области памяти => чтобы получить j-й элемент массива, нам достаточно взять указатель на начало массива и прибавить к нему размер элемента умноженный на его индекс. Результат этого несложного вычисления будет указывать как раз на искомый элемент массива.
*aj = beginPointer + elementSize*j-1
2. List (список).
List — это список элементов произвольного типа переменной длины (то есть мы можем в любой момент добавить элемент в список или удалить его). Список позволяет перебирать элементы, получать элементы по индексу, а так же добавлять и удалять элементы. Реализации у List возможны разные, основные — это (Single/Bidirectional) Linked List и Vector. Классический List предоставляет возможность работы с ним напрямую и через итератор, интерфейсы обоих классов рассмотрим ниже.
- prepend(item): Добавить элемент в начало списка.
- append(item): Добавить элемент в конец списка.
- insert_after(List Iterator, item): Добавить элемент после текущего.
- remove_firts(): Удалить первый элемент.
- remove_after(List Iterator): Удалить элемент после текущего.
- is_empty(): Пуст ли List.
- get_size(): Возвращает размер списка.
- get_nth(n): Вернуть n-й элемент.
- set_nth(n, value): Задать значение n-му элементу.
- get_value(): получить значение текущего элемента.
- set_value(): задать значение текущему элементу.
- move_next(): переместиться к следующему элементу.
- equal(List Iterator): проверяет — ссылается ли другой итератор на тот же элемент списка.
Перейдем к реализациям списка.
2.1 Single Linked List
Однонаправленный связный список (односвязный список) представляет из себя цепочку контейнеров. Каждый контейнер содержит внутри себя ссылку на элемент и ссылку на следующий контейнер, таким образом, мы всегда можем переместиться по односвязному списку вперед и всегда можем получить значение текущего элемента. Контейнеры могут располагаться в памяти как им угодно => добавление в односвязный список нового элемента тривиально.
- prepend: O(1)
- insert_after: O(1)
- remove_first/remove_after: O(1)
- get_nth/set_nth: O(N)
Bidirectional Linked List мы подробно рассматривать не будем, вся разница между ним и Single Linked List заключается в том, что в контейнерах есть ссылка не только на следующий, но и на предыдущий контейнер, что позволяет перемещаться по списку не только вперед, но и назад.
2.2 Vector
Vector — это реализация List через расширение индексированного массива.
- prepend: O(N)
- append: Amort.O(1)
- insert_after: O(N)
- remove_first/remove_after: O(1)
- get_nth/set_nth: O(1)
Очевидно, что главное преимущество Vector'а — быстрый доступ к элементам по индексу, унаследовано им от обычного индексированного массива. Итерировать Vector так же достаточно просто, достаточно увеличивать некий счетчик на единицу и осуществлять доступ по индексу. Но за скорость доступа к элементам приходиться платить временем их добавления. Для того чтобы вставить элемент в середину Vector'a (insert-after) необходимо скопировать все элементы между текущим положением итератора и концом массива, как следствие время доступа в среднем O(N). То же и с удалением элемента в середине массива, и с добавлением элемента в начало массива. Добавление элемента в конец массива при этом может быть выполнено за O(1), но может и не быть — если опять таки потребуется копирование массива в новый, потому говорится, что добавление элемента в конец Vector'а происходит за Amort. O(1).
3. Ассоциативный массив(Словарь/Map)
Коллекция пар ключ=>значение. Элементы (значения) могут быть любого типа, ключи обычно только строки/целые числа, но в некоторых реализация диапазон объектов, которые могут быть использованы в качестве ключа, может быть шире. Размер ассоциативного массива можно изменять путем добавления/удаления элементов.
- add(key, value) — добавить элемент
- reassign(key, value) — заменить элемент
- delete(key) — удалить элемент
- lookup(key) — найти элемент
3.1 Hash Table
Как можно догадаться из названия, тут используются хэши. Механика работы Hash Table следующая: в основе лежит все тот же индексированный массив, в котором индексом работает значение хэша от ключа, а значением — ссылка на объект, содержащий ключ и хранимый элемент (bucket). При добавлении элемента — хэш функция вычисляет хэш от ключа и сохраняет ссылку на добавляемый элемент в ячейку массива с соответствующим индексом. Для получения доступа к элементу мы опять таки берем хэш от ключа и, работая так же как с обычным массивом получаем ссылку на элемент.
- Если хэш от ключа равен например 1928132371827612 — это ведь будет означать, что нам надо иметь массив соответствующего размера? А если у нас в нем всего 2 элемента?
- А если у нас хэши от двух разных ключей совпадут?
То есть, кроме значения ключа, она так же получает текущий размер массива, это необходимо для определения длины хэша: если мы храним всего 3 элемента — нет смысла делать хэш длиной в 32 разряда. Обратная сторона такого поведения хэш функции — возможность коллизий. Коллизии на самом деле характерны для Hash Table, и существует два метода их разрешения:
Chaining:
Каждая ячейка массива H является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.
Open addressing:
В массиве H хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива H в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.
- add: Amort.O(1)/O(N)
- reasign: Amort.O(1)/O(N)
- delete: Amort.O(1)/O(N)
- lookup: Amort.O(1)/O(N)
3.2 Binary Tree
На самом деле не просто Binary Tree, а Self-balancing Binary Tree. Причем следует отметить, что существует несколько различных деревьев, которые могут быть использованы для реализации Ассоциативного массива: red-black tree, AVL-tree и т.д. Мы не будем рассматривать каждое из этих деревьев в деталях, так как это возможно тема еще одной, отдельной статьи, а может и нескольких (если изучать деревья особо тщательно). Опишем только общие принципы.
Определение: двоичное дерево — древовидная структура данных в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. В случае, если у узла нет наследников — он называется листовым узлом.
- add: Amort.O(lgN)
- reasign: Amort.O(lgN)
- delete: Amort.O(lgN)
- lookup: Amort.O(lgN)
4. Множество (Set).
Сравнительные характеристики структур данных:
Структуры данных в различных языках программирования:
Ссылки:
Так же автор заглянул в исходники PHP и почитал доку по STL.
Upd. Да, в питоне есть обычный индексированный массив (array.array). Спасибо enchantner. С поправкой, тип не обязательно числовой, тип можно указывать.
Upd. Сделано много исправлений по тексту. idemura, zibada, tzlom, SiGMan, freeOne, Slaffko, korvindest, Laplace, enchantner спасибо за правки!
Upd.
Из комментариев zibada:
Да, вот как раз из-за отсутствия описания итерации по Map из статьи вообще непонятно, зачем, казалось бы, нужны деревья, когда есть хэши. (O(logN) против O(1)).
Нужны они затем, что перечислять элементы Map (или Set) можно хотеть:
— в любом, негарантированном порядке (HashMap, встроенные хэши в некоторых скриптовых языках);
— в порядке добавления (LinkedHashMap, встроенные хэши в некоторых других скриптовых языках);
— в порядке возрастания ключей + возможность перебрать только ключи в заданном диапазоне.
А вот для последнего случая альтернатива деревьям — только полная сортировка всей коллекции после каждого изменения или перед запросом.
Что долго и печально для больших коллекций, но вполне работает для небольших — поэтому в скриптовые языки деревья особо и не встраивают.
Звучит ли это знакомо: «Я начал заниматься веб разработкой после прохождения курсов»?
Возможно, вы хотите улучшить свои знания основ информатики в части структур данных и алгоритмов. Сегодня мы поговорим о некоторых наиболее распространенных структурах данных на примере JS.
2. Очередь (кью) (Queue)
Очередь напоминает стек. Разница состоит в том, что очередь следует принципу FIFO (First In First Out — первым вошел, первым вышел). Когда вы стоите в очереди, первый в ней всегда будет первым.
Очередь имеет следующие методы:
- enqueue: войти в очередь, добавить элемент в конец
- dequeue: покинуть очередь, удалить первый элемент и вернуть его
- front: получить первый элемент
- isEmpty: проверить, пуста ли очередь
- size: получить количество элементов в очереди
Порядок очередности (приоритет)
Очередь имеет продвинутую версию. Присвойте каждому элементу приоритет, и элементы будут отсортированы соответствующим образом:
Применение
- Используется при пирамидальной сортировке.
- Используется для реализации очередей с приоритетом, поскольку приоритетные значения можно упорядочить согласно свойству кучи.
- Функции очереди можно реализовать с помощью куч за время, равное O(log n).
- Используется для поиска k-того наименьшего или наибольшего значения в данном массиве.
Хэш таблицы
Хэширование — это процесс, используемый для уникальной идентификации объектов и хранения каждого объекта в заранее рассчитанном уникальном индексе (ключе).
Объект хранится в виде пары «ключ-значение», а коллекция таких элементов называется «словарем». Каждый объект можно найти с помощью этого ключа.
По сути это массив, в котором ключ представлен в виде хеш-функции.
Эффективность хеширования зависит от
- Функции хеширования
- Размера хэш-таблицы
- Метода борьбы с коллизиями
Вопросы
- Найти симметричные пары в массиве
- Найти, если массив является подмножеством другого массива
- Описать открытое хеширование
2. Связные списки
Связный список — динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и ссылки на другой узел списка. Поэтому обращаться к данным нужно последовательно, так что произвольный доступ невозможен. Связанные списки обеспечивают простое и гибкое представление динамических наборов данных.
Давайте рассмотрим основные термины. Для наглядности ниже все они изображены на рисунке.
- Элементы в связном списке называют узлами (nodes).
- Каждый узел содержит ключ и указатель на следующий узел, который называется next.
- Атрибут head указывает на первый элемент связного списка.
- Последний элемент связного списка называется tail.
Применение
- Используется в разработке компилятора для управления таблицей символов.
- Используется для переключения между программами с помощью Alt+Tab (реализовано с помощью кольцевого связного списка).
Случаи выполнения
Чтобы провести сравнение временных промежутков, необходимых для выполнения различной структуры, используются следующие случаи:
- худший – сценарий, при котором для выполнения конкретной операции потребуется максимальное время, которое только возможно;
- средний – сценарий, при котором на выполнение операции отводится среднее время;
- наилучший – сценарий, который отображает кратчайший промежуток времени, необходимый для выполнения операции.
4. Коллекция (значений) (Set)
Коллекция (множество) — одна из основных концепций математики: набор хорошо определенных и обособленных объектов. ES6 представил коллекцию, которая имеет некоторое сходство с массивом. Тем не менее, коллекция не допускает включения повторяющихся элементов и не содержит индексов.
Стандартная коллекция имеет следующие методы:
- values: вернуть все элементы в коллекции
- size: вернуть количество элементов
- has: проверить, имеется ли элемент в коллекции
- add: добавить элемент
- remove: удалить элемент
- union: вернуть область пересечения двух коллекций
- difference: вернуть отличия двух коллекций
- subset: проверить, является ли одна коллекция подмножеством другой
Применение
Все чаще замечаю, что современным самоучкам очень не хватает матчасти. Все знают языки, но мало основы, такие как типы данных или алгоритмы. Немного про типы данных.
Еще в далеком 1976 швейцарский ученый Никлаус Вирт написал книгу Алгоритмы + структуры данных = программы.
40+ лет спустя это уравнение все еще верно. И если вы самоучка и надолго в программировании пробегитесь по статье, можно по диагонали. Можно код кофе.
В статье так же будут вопросы, которое вы можете услышать на интервью.
Стеки
Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Это не массивы. Это очередь. Придумал Алан Тюринг.
Примером стека может быть куча книг, расположенных в вертикальном порядке. Для того, чтобы получить книгу, которая где-то посередине, вам нужно будет удалить все книги, размещенные на ней. Так работает метод LIFO (Last In First Out). Функция «Отменить» в приложениях работает по LIFO.
Изображение стека, в три элемента (1, 2 и 3), где 3 находится наверху и будет удален первым.
Основные операции
- Push-вставляет элемент сверху
- Pop-возвращает верхний элемент после удаления из стека
- isEmpty-возвращает true, если стек пуст
- Top-возвращает верхний элемент без удаления из стека
Вопросы
- Реализовать очередь с помощью стека
- Сортировка значений в стеке
- Реализация двух стеков в массиве
- Реверс строки с помощью стека
Деревья
Деревом является иерархическая структура данных. Она составлена из узлов (вершин) и дуг (ребер). При близком рассмотрении можно понять, что деревьями являются связанные графы, не имеющие цикличности.
От деревьев, встречающихся в природе, классическое математическое дерево отличается тем, что корень последнего расположен вверху. А его ветви «растут» сверху вниз.
Дереву присущи характеристики:
- Каждое имеет единственную вершину (корневой узел), расположенную сверху и не имеющую предков. Никакая вершина не ссылается на корень, а из него можно достичь любой имеющейся вершины дерева (это следствие свойства связанности древовидной структуры).
- Вершины, которые не имеют потомков (не ссылаются на иные) называются терминальными узлами (листьями).
- Объекты, которые располагаются между вершиной и листьями, называются промежуточными узлами.
- Каждая вершина древовидной структуры имеет лишь единого предка, а если он является корневым – не имеет ни одного предка.
- У корневого узла может быть от нуля или более потомков.
- У каждого дочернего узла может быть от нуля или более дочерних вершин.
Поддеревом называется часть древовидной структуры, которая имеет вершину и имеющиеся потомки.
Существует несколько типов деревьев. Чаще других встречается бинарное дерево. Оно представляет собой структуру данных с иерархией, в которой каждый узел имеет определенное значение (которое является ключом) вместе со ссылками на потомков (слева и справа).
Для деревьев используются следующие методы обхода:
- прямой – осуществляется сверху вниз (начинается с посещения предков и постепенно переходит к потомкам);
- обратный – обход осуществляется снизу вверх (прежде посещаются потомки, потом – предки);
- симметричный – обход осуществляется слева направо (по очереди осуществляется обход поддеревьев главного дерева).
Выражение информации в виде древовидных структур оправдано в том случае, если у нее есть явная иерархия. Иерархически выраженная структура потребуется при работе с данными о географических объектах, служебных должностях и т.д. В таких случаях информацию лучше представлять в виде классических математических деревьев.
Дерево двоичного (бинарного) поиска
Кроме вышеуказанных характеристик деревьев, дереву двоичного поиска характерны еще ряд характеристик:
- Узел может иметь не больше двух детей (потомков).
- Левые потомки меньше текущего узла, что меньше, чем у правых детей.
Бинарные деревья помогают существенно ускорить работу объектами (находить, удалять, добавлять их).
Префиксные деревья (Trie), боры, лучи
Префиксные деревья, именуемые иногда борами и лучами, являются разновидностью древовидных структур. Они особенно эффективны для работы со строками, т.к. обеспечивают быстрый поиск информации. По сути бор является деревом поиска.
Чаще всего боры используют для:
- поиска слов в словарях;
- автозавершений в поисковиках;
- IP-маршрутизации.
Бор хранит данные в узлах. Такие деревья часто используются для хранения слов. Они хранятся в борах сверху вниз – в каждом узле по букве.
Для записи слова необходимо проследовать по ветвям дерева, вписывая за раз по одной букве. Если порядок букв не похож на другие слова в дереве либо слово заканчивается, шаги начинают расходиться. В каждой вершине находится буква (данные) вместе с логическим значением, которое указывает на то, является ли данный узел в слове последним или нет.
Двоичная куча
Так называют полное дерево, у которого в каждом узле до двух детей. У двоичной кучи все уровни до последнего заполнены полностью. В последнем уровне заполнение ведется слева направо.
- максимальной – у родительских узлов ключи всегда больше либо равны тем ключам, которые у детей;
- минимальной – у родительских узлов ключи меньше либо равны ключам у дочерних элементов.
В двоичной куче прослеживается важность порядка между уровнями, но не между узлами одного уровня.
Это вся важная информация о структурах данных программы. Изучайте материал, находите новое и применяйте на практике. Если возникли вопросы – задавайте. Обязательно ответим на них.
6. Деревья
Дерево — структура, в которой данные организованы в иерархическом порядке и связаны друг с другом. Дерево отличается от связного списка тем, что во втором случае элементы связываются в линейном порядке.
Несколько последних десятилетий люди придумывали различные типы деревьев: для разных целей и в условиях разнообразных ограничений. Вот некоторые примеры: двоичное дерево поиска, B-дерево, декартово дерево (treap), красно-черное дерево, расширенное дерево, АВЛ-дерево и n-арное дерево.
Графы
Графом называют набор узлов (вершин), соединенных между собой связями (называют ребра, дуги).
- ориентированными – имеют ребра с единственно возможным направлением между парой связанных вершин;
- неориентированными – для каждой дуги переход между вершинами может происходить в любом направлении, а также из каждой вершины можно перейти в другую;
- смешанные – отличаются присутствием дуг, перечисленных выше.
Графы могут иметь различную форму:
- матрицы смежности – таблицы целых чисел, в которой каждая строка либо столбец являются другим узлом на графе. В месте пересечения столбца и строки находится число, указывающее на отношение. Нули указывают, что ребер нет, а единицы – что связи есть;
- матрицы инцидентности;
- списка смежности – представлен списком, в котором левая сторона выступает вершиной, а правая – перечнем всех иных узлов, соединенных с ней;
- списка ребер.
В графах используются алгоритмы обхода:
- в глубину (depth-first search) – обход осуществляется по узлам.
- в ширину (breadth-first search) – поиск осуществляется по уровням;
Стиль дуг граф может быть не только в виде прямой линии, а вершин – выражен в цифрах. Существуют графы, именуемые взвешенными, где ребрам соответствует определенное значение (именуемое его весом). При совпадении концов ребра его называют петлей.
Графы довольно часто используются в транспортных и компьютерных сетях, веб-технологиях. По принципу граф построены социальные сети, где люди являются узлами, а дуги – их связями.
4. Очереди
Очереди — структура с дисциплиной доступа к элементам FIFO («первый пришёл — первый вышел», доступ к первому элементу получается в первую очередь), которая часто встречается в языках программирования. Структура так называется, потому что напоминает реальные очереди — людей, выстроившихся в линию в ожидании своего череда.
Операции над стеками
Ниже представлены две базовые операции, которые можно производить над стеками. Чтобы лучше понять смысл их работы, рассмотрите картинку.
- Push: вставить элемент «на верх» стека.
- Pop: удалить самый верхний элемент и возвращаем его.
Помимо этого, для стека предусмотрены следующие дополнительные функции для проверки его состояния.
- Peek: вернуть верхний элемент стека, не удаляя его.
- isEmpty: проверить, пуст ли стек.
- isFull: проверить, заполнен ли стек.
7. Нагруженное (префиксное) дерево (Trie, читается как «try»)
Префиксное дерево — это разновидность поискового дерева. Данные в нем сохраняются последовательно (шаг за шагом) — каждый узел дерева представляет собой один шаг. Префиксное дерево используется в словарях, поскольку существенно ускоряет поиск.
Каждый узел дерева — буква алфавита, следование по ветке приводит к формированию слова. Оно также содержит «булевый индикатор» для определения того, что текущий узел является последней буквой.
Префиксное дерево имеет следующие методы:
- add: добавить слово в словарь
- isWord: проверить наличие слова
- print: вернуть все слова
6. Дерево (Tree)
Древовидная структура — это многослойная (многоуровневая) структура. Это также нелинейная структура, в отличие от массива, стека и очереди. Данная структура очень эффективна в части добавления и поиска элементов. Вот некоторые концепции древовидной структуры:
- root: корневой элемент, не имеет «родителя»
- parent node: прямой узел верхнего слоя (уровня), может быть только одним
- child node: прямой узел (узлы) нижнего уровня, может быть несколько
- siblings: дочерние элементы одного родительского узла
- leaf: узел без «детей»
- Edge: ветка или ссылка (связь) между узлами
- Path: путь (совокупность ссылок) от начального узла до целевого элемента
- Height of Tree (высота дерева): количество ссылок самого длинного пути от определенного элемента до узла, не имеющего потомков
- Depth of Node (глубина узла): количество ссылок от корневого узла до определенного элемента
- Degree of Node: количество потомков
Методами данного дерева являются следующие:
- add: добавить узел
- findMin: получить минимальный узел
- findMax: получить максимальный узел
- find: найти определенный узел
- isPresent: проверить наличие определенного узла
- remove: удалить узел
Операции над массивами
- Перебор массива: пройтись по каждому элементу и, например, вывести его.
- Поиск: найти элемент в массиве. Искать можно по индексу или по значению.
- Обновить: обновить значение существующего элемента по его индексу.
Просто вставить или удалить элементы в или из массива нельзя, поскольку у массивов есть фиксированный размер. Если вы хотите вставить элемент в массив, сначала придется создать новый массив с увеличенным размером (больше текущего на 1, если вам нужно вставить 1 элемент), скопировать существующие элементы оригинального массива и добавить новый элемент. То же самое касается удаления: понадобится новый массив уменьшенного размера.
Применение
- Используется для управления потоками в режиме многопоточности.
- Используется для реализации систем очередей (например, приоритетных очередей).
Характеристики
Важными характеристиками структур данных являются:
- Корректность – она должна грамотно реализовывать свой интерфейс.
- Сложность времени – должно использоваться минимальное количество времени на выполнение операций.
- Сложность пространства – при проведении операций память должна использоваться минимально.
Списки
Список является абстрактным типом данных. Существует несколько их разновидностей. Рассмотрим наиболее популярные:
Связные (связанные) списки
Связной список представляет собой массив с конечным множеством элементов (отдельных объектов) и указателями на них.
Каждый объект содержит:
- поле информации (тип данных может быть любым);
- ссылки (указатели) на последующий узел.
Таким образом упорядоченные элементы связного списка связаны друг с другом указателями. Вместе эти группы образуют последовательность.
Как и массив, список лежит в основе понятия классической структуры данных. Их функциональные особенности часто сравнивают, т.к. большинство других структур могут быть реализованы с помощью массивов или связных списков. Последний отличается от массива структурной гибкостью. Доступ к спискам осуществляется последовательно, а к массивам – произвольно.
Связанные списки бывают следующих видов:
- Однонаправленные (односвязные) – каждый узел сохраняет адрес либо ссылку на тот узел, который числится следующим. А узел, являющийся последним, содержит последующий адрес либо ссылку как NULL. Линейные однонаправленные списки встречаются чаще всего.
- Двунаправленные (двусвязные) – имеют две ссылки, которые связаны с каждым отдельным узлом (первая указывает на последующий, вторая – на предыдущий).
- Круговые (кольцевые) – все узлы списка соединены в круг при отсутствии в последнем NULL. Является подвидом двух предыдущих видов связных списков. Они могут быть одно- или двусвязными.
Чтобы односвязный список стал круговым, необходимо в его последний узел вставить указатель на первый элемент. Чтобы двунаправленный список преобразовать в кольцевой, следует добавить две ссылки на узлы: первый и последний.
Операции, являющиеся основными:
- InsertAtEnd – вставка заданного элемента в конце списка;
- InsertAtHead – вставка заданного элемента в начало списка;
- Delete – удаление заданного элемента из списка;
- DeleteAtHead – удаление первого элемента в списке;
- Search – возвращение заданного элемента из списка
- isEmpty – в тем случае, когда список пустой, производится возврат True.
Стеки
Являются базовой структурой, в которой реализовано лишь добавление и удаление объектов в начало стека (через его вершину). Представляет собой список элементов, которые организованы по принципу LIFO (на английском языке Last In – First Out, что в переводе означает «последним зашел – первым ушел»). По тому же принципу работает в приложениях функционал «Отменить».
Отличное сравнение – стопка тарелок. Чтобы из стопки взять тарелку, необходимо вначале снять верхние тарелки. А положить тарелку можно только на верх стопки.
- Push – вставка в стек элемента наверху;
- Pop – удаление верхнего элемента из стека;
- Pip – отображается содержимое;
- isEmpty – происходит возврат True в случае, когда стек пустой;
- Top – возвращает элемент сверху, не удаляя его из стека.
Чаще всего в программировании применяется:
- стек изменений в редакторе кода, позволяющий быстро делать отмену изменений и возвращаться к предыдущему состоянию;
- стек передвижения по страницам в браузере – позволяет быстро переходить по страницам.
Очереди
Является яркой аналогией с очередью в магазин. Порядок входа в него определяет то, в каком порядке была занята очередь. Первый занявший очередь зайдет первым, за ним – второй и т.д. В очереди используется принцип доступа к данным FIFO (на английском языке – First In First Out, в переводе означает «Первый вошел, первый ушел»).
Если кратко, то очередью является список, в котором добавление новых элементов допустимо строго в его конец, а извлечение – происходит строго с другого конца, который называют началом списка.
Элементы сохраняются последовательно. Но для очереди используется принцип FIFO, а не LIFO.
- Enqueue – вставка элемента в конец очереди;
- Dequeue – удаление элемента из начала очереди;
- isEmpty – будет возвращено значение True, если очередь пуста;
- Top – возвращает первый элемент из очереди.
Дек или двухсторонняя очередь
Дек (двухсторонняя очередь) – это вид списка (стека) с двумя концами. Он позволяет добавлять и извлекать элементы с двух сторон (как в начале, так и в конце).
Дек работает одновременно по FIFO и LIFO. Потому он и относится к отдельной программной единице, которая была получена в результате суммирования стека и очереди.
Связанный список
Связанный список – массив где каждый элемент является отдельным объектом и состоит из двух элементов – данных и ссылки на следующий узел.
Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Бывают
Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.
Двунаправленный, две ссылки, связанные с каждым узлом, одним из опорных пунктов на следующий узел и один к предыдущему узлу.
Круговой, все узлы соединяются, образуя круг. В конце нет NULL. Циклический связанный список может быть одно-или двукратным циклическим связанным списком.
Самое частое, линейный однонаправленный список. Пример – файловая система.
Основные операции
- InsertAtEnd — Вставка заданного элемента в конец списка
- InsertAtHead — Вставка элемента в начало списка
- Delete — удаляет заданный элемент из списка
- DeleteAtHead — удаляет первый элемент списка
- Search — возвращает заданный элемент из списка
- isEmpty — возвращает True, если связанный список пуст
Вопросы
- Реверс связанного списка
- Определение цикла в связанном списке
- Возврат N элемента из конца в связанном списке
- Удаление дубликатов из связанного списка
Список ресурсов
Двоичные деревья поиска
Двоичное дерево поиска, как следует из названия, представляет собой бинарное дерево, данные в котором хранятся в отсортированном порядке.
Каждый узел в двоичном дереве поиска содержит следующие атрибуты:
- key: значение, хранящееся в узле.
- left: указатель на левый узел-потомок (child).
- right: указатель на правый узел-потомок (child).
- p: указатель на узел-родителя (parent).
У бинарного дерева поиска есть уникальное свойство, которое отличает его от других деревьев.
Пусть x — узел в двоичном дереве поиска.
Если y является узлом в левом поддереве x, тогда y.key ≤ x.key.
Если y является узлом в правом поддереве x, то y.key ≥ x.key.
Базовые термины
Перед изучением структуры данных кратко коснемся их основы – терминов, а затем перейдем к применению. К ним относятся:
- Интерфейс – определенный набор операций, поддерживающих структуру данных. Он присущ каждой структуре. Интерфейс может предоставлять только перечень поддерживаемых операций, тип принимаемых параметров и возвращает тип этих операций.
- Реализация – обеспечивает внутреннее представление структуры данных, помогает в определении алгоритмов, которые используются в операциях.
Виды связных списков
- Односвязный список — передвигаться можно только в сторону конца списка.
- Двусвязный список — передвигаться можно в обе стороны. Узлы состоят из дополнительного указателя — prev. Он указывает на предыдущий узел.
- Кольцевой связный список — последний элемент кольцевого списка содержит указатель на первый, а первый — на последний.
Операции над очередями
Ниже представлены две основные операции, которые можно производить над очередями. Рассмотрите картинку, чтобы лучше понимать, как они работают.
- Enqueue (поставить в очередь): вставить элемент в конец очереди.
- Dequeue (убрать из очереди): удалить элемент из начала очереди.
Применение
- Двоичные деревья: используются для реализации парсеров выражений и их решателей.
- Двоичное дерево поиска: используется во многих поисковых приложениях, которые постоянно получают и отдают данные.
- Кучи: используются в JVM (Java Virtual Machine) для хранения java-объектов.
- Декартовы деревья: используются в беспроводных сетях.
7. Кучи
Куча (heap) — это частный случай двоичного дерева, в котором узлы-родители сравниваются по значениям с узлами-потомками и располагаются соответствующим образом.
Посмотрим, как можно изобразить кучи. Кучу можно представить как в виде дерева, так и в виде массива. Это показано на рисунках ниже.
Куча в виде двоичного дерева
Куча в виде массива
Кучи могут быть 2 видов.
- Min Heap — ключ родителя меньше или равен ключу потомков. Это называется свойством min-heap. Корень при этом будет содержать наименьшее значение кучи.
- Max Heap — ключ родителя больше или равен ключу потомков. Это называется свойством max-heap. Корень при этом содержит наибольшее значение кучи.
Trie ( префиксное деревое )
Разновидность дерева для строк, быстрый поиск. Словари. Т9.
Вот как такое дерево хранит слова «top», «thus» и «their».
Слова хранятся сверху вниз, зеленые цветные узлы «p», «s» и «r» указывают на конец «top», «thus « и «their» соответственно.
Вопросы
- Подсчитать общее количество слов
- Вывести все слова
- Сортировка элементов массива с префиксного дерева
- Создание словаря T9
Применение
- Используются в качестве строительных блоков для построения других структур данных: списков массивов, куч, хеш-таблиц, векторов и матриц.
- Используется для различных алгоритмов сортировки: сортировка вставками, быстрая сортировка, «пузырьковая» сортировка и сортировка слиянием.
Множества
Хранение данных во множество организовано беспорядочно и без повторяющихся значений. В них можно добавлять и удалять объекты, а также есть еще ряд важнейших функций, позволяющих работать одновременно с двумя наборами функций.
Так, при двух заданных множествах функции выполнят:
- Union (объединение множеств) – объединятся все элементы, принадлежащие им обеим. Результат будет возвращен в качестве нового (не имеющего дубликатов);
- Intersection (пересечение множеств) – будет возвращено новое множество, которому будут принадлежать объекты, имевшиеся в обеих заданных множествах;
- Difference (разница множеств) – будет возвращено множество с элементами, содержавшимися в одном и не повторявшиеся в другом;
- Subset (подмножество) – возвращает булево значение, демонстрирующее содержатся ли в множестве все объекты иного.
Map также именуют ассоциативный массив или словарь. Это структура данных, которая сохраняет данные в связке уникальный ключ/ значение. Чаще всего он используется, когда необходим быстрый поиск информации
С помощью Map можно:
- добавить пару;
- удалить пару;
- изменить пару;
- найти значения, которые связаны с определенными ключами.
Читайте также: