хеш-таблицы (1)

1. Информатика (3 семестр) Алгоритмы и структуры данных

ИНФОРМАТИКА
(3 семестр)
Алгоритмы и структуры данных
Ассоциативный массив. Хеш-таблицы.
Амортизационный анализ.
Идет подготовка презентации…

2. Ассоциативный массив

Ассоциативный массив (сокр. АМ, также иногда – ассоциативная память) – способ
организации данных, при котором данные организуются в пары ключ - значение и каждому
ключу единственным образом сопоставлено значение.
В качестве значения часто выступают объекты более чем с одним полем.
Каждому значению должен соответствовать уникальный ключ. В качестве ключа может
выступать уникальный идентификатор UID либо уникальная совокупность полей.
Идет показ слайда…
2 из 15

3. Ассоциативный массив

Ассоциативный массив можно охарактеризовать как абстрактную поисковую СД.
Абстрактная – ее можно реализовать разными способами.
Поисковая – ее основное предназначение (и самая частая операция) – поиск данных по
ключу. Также очень важны операции вставки и удаления элемента. Мы хотим, чтобы все эти
три операции выполнялись быстро.
Идет показ слайда…
3 из 15

4. Ассоциативный массив

Несколько примеров задания ключей.
1)Ключ как UID (уникальный идентификатор):
• Глобальный счетчик - при каждом новом добавлении элемента увеличивается на 1
• Текущее время в системе (при сбросе времени могут возникнуть дубликаты)
• UUID (universally unique identifier) – стандарт идентификации, генерирует универсальный
идентификатор (часто используется на практике)
Пример: 123e4567-e89b-12d3-a456-426655440000
2)Ключ как уникальные поля хранимых данных: номер телефона, никнейм пользователя,
ФИО + дата рождения + адрес регистрации и т.д.
UUID: https://digitalbunker.dev/understanding-how-uuids-are-generated/
UUID генератор: https://www.uuidgenerator.net/
Идет показ слайда…
4 из 15

5. Ассоциативный массив. Двоичное дерево поиска

Один из эффективных способов реализации АМ – двоичное дерево поиска (BST).
Оценка сложности операций:
• поиск элемента – O(logn)
• вставка элемента – O(logn)
• удаление элемента – O(logn)
Сюда же можно отнести и другие способы
реализации АМ на основе двоичных деревьев:
Если в дереве n элементов,
• AVL-дерево
то высота дерева ≈