Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы

Операции над списками

Random Access Memory
У каждой ячейки свой адрес
Быстрый доступ к ячейке по

Array
Сплошной массив элементов в памяти
Задан адрес начального элемента
Быстрое вычисление адреса элемента

Linked lists once again….
Произвольное расположение элементов
Возможность расширения
Медленный доступ по индексу:

Формулировка проблемы

Необходимость быстрого поиска данных в огромных массивах
Где применить:
Справочники
Базы данных пользователей
Реализация

Создание баз данных логинов-паролей

Огромное количество пользователей системы
Время доступа – критический

База данных телефонных номеров

Ограниченное количество всевозможных номеров
Ключевой параметр – скорость поиска
Каждый

База данных телефонных номеров

Решение – список
Проблемы:
Очень долгий поиск
Решение – огромный массив

База данных телефонных номеров

Решение – список
Проблемы:
Очень долгий поиск
Решение – огромный массив
Проблемы:
Массив

Концепция Хеш-таблицы

Массив фиксированной длинны
Положение элемента определяется хеш-функцией
Отображение элементов на множество индексов

Организация хеш-таблицы и проблема коллизий

Решение проблемы коллизий

Метод цепочек (закрытая адресация)

Элементы оформлены в список
Поиск элемента в

Закрытая адресация

Закрытая адресация

Открытая адресация

Открытая адресация

Последовательность проб: пробивание

Линейное пробирование

Квадратичное пробирование

Последовательность проб: double hashing

Хеширование

Хеширование (англ. hashing) — преобразование массива входных данных произвольной длины в

Хеш-функции

Хеш-функции

Результат применения хеш-функции имеет фиксированную длину
При небольшом изменении входных данных существенно

Хорошие хеш-функции

Свойства «хорошоих» хеш-функций:
Минимальное количество коллизий
Равномерное распределение ответов
Быстрое вычисление
Идеальная хеш-функция –

Применение хеш-функций

Хранение и поиск данных
Компьютерная графика
Контрольные суммы
Информационная безопасность

Примеры хеш-функций

Примеры хеш-функций

Примеры хеш-функций

XOR – хеширование
Не криптостойкий
Отсутствует лавинный эффект

Примеры хеш-функций

Примеры хеш-функций

Семейство MD (Message Digest)
MD4 (взломан)
MD5 (взломан)
MD6
Семейство SHA (Secure Hash Algorithm)
SHA-1 (взломан)
SHA-2 (взломан)
SHA-224,

Сравнение производительности Добавление 10000 элементов

Сравнение производительности Поиск несуществующего элемента

Сравнение производительности Поиск 1000 случайных элементов

Сравнение производительности Поиск 1000 существующих элементов

Встроенные хеш-таблицы в Python

Словари (dict)
Ассоциативный массив
Хранит пары ключ-значение
Быстрый поиск по ключам
Множества