Содержание
- 2. Операции над списками
- 3. Random Access Memory У каждой ячейки свой адрес Быстрый доступ к ячейке по адресу Поддержка адресной
- 4. Array Сплошной массив элементов в памяти Задан адрес начального элемента Быстрое вычисление адреса элемента по индексу
- 5. Linked lists once again…. Произвольное расположение элементов Возможность расширения Медленный доступ по индексу:
- 6. Формулировка проблемы Необходимость быстрого поиска данных в огромных массивах Где применить: Справочники Базы данных пользователей Реализация
- 7. Создание баз данных логинов-паролей Огромное количество пользователей системы Время доступа – критический параметр Огромное количество возможных
- 8. База данных телефонных номеров Ограниченное количество всевозможных номеров Ключевой параметр – скорость поиска Каждый номер уникален
- 9. База данных телефонных номеров Решение – список Проблемы: Очень долгий поиск Решение – огромный массив
- 11. База данных телефонных номеров Решение – список Проблемы: Очень долгий поиск Решение – огромный массив Проблемы:
- 12. Концепция Хеш-таблицы Массив фиксированной длинны Положение элемента определяется хеш-функцией Отображение элементов на множество индексов не взаимно-однозначное
- 13. Организация хеш-таблицы и проблема коллизий
- 14. Решение проблемы коллизий Метод цепочек (закрытая адресация) Элементы оформлены в список Поиск элемента в списке Произвольный
- 15. Закрытая адресация
- 16. Закрытая адресация
- 17. Открытая адресация
- 18. Открытая адресация
- 19. Последовательность проб: пробивание Линейное пробирование Квадратичное пробирование
- 20. Последовательность проб: double hashing
- 22. Хеширование Хеширование (англ. hashing) — преобразование массива входных данных произвольной длины в битовую строку фиксированной длины,
- 23. Хеш-функции
- 24. Хеш-функции Результат применения хеш-функции имеет фиксированную длину При небольшом изменении входных данных существенно меняется результат Нет
- 25. Хорошие хеш-функции Свойства «хорошоих» хеш-функций: Минимальное количество коллизий Равномерное распределение ответов Быстрое вычисление Идеальная хеш-функция –
- 26. Применение хеш-функций Хранение и поиск данных Компьютерная графика Контрольные суммы Информационная безопасность
- 27. Примеры хеш-функций
- 28. Примеры хеш-функций
- 29. Примеры хеш-функций XOR – хеширование Не криптостойкий Отсутствует лавинный эффект
- 30. Примеры хеш-функций
- 31. Примеры хеш-функций Семейство MD (Message Digest) MD4 (взломан) MD5 (взломан) MD6 Семейство SHA (Secure Hash Algorithm)
- 36. Сравнение производительности Добавление 10000 элементов
- 37. Сравнение производительности Поиск несуществующего элемента
- 38. Сравнение производительности Поиск 1000 случайных элементов
- 39. Сравнение производительности Поиск 1000 существующих элементов
- 41. Встроенные хеш-таблицы в Python Словари (dict) Ассоциативный массив Хранит пары ключ-значение Быстрый поиск по ключам Множества
- 43. Скачать презентацию