Хеширование, множества и словари
- Хеш-функуия — преобразование объекта в число
- Свойства хеш-функции:
- равномерность
- ограниченность
hash() — хеш-дайджест объекта, хешируемые объекты
- Свойство дайджеста — минимизация коллизий
- Упрощение сравнения больших объектов путём предварительного сравнения дайджестов
- Хеш-таблица: хранение и поиск хешируемых объектов
- вторичный хеш (в случае Python — остаток от деления)
- внешняя обработка коллизий: хранение списка объектов с одинаковыми хешами
- внутренняя обработка коллизий: повторное хеширование по другому алгоритму (например, поиск первой свободной записи в таблице, или генерация псевдослучайного смешения)
- Множества, операции над ними. Их реализация.
- Методы множеств
- Словарь — множество ключей с указателями на произвольный объект
- Работа со словарями
- Методы
Пара ссылок о том, как реализованы словари (и множества) в Python:
Домашнее задание
Условные обозначения
— тема по Linux
— тема повышенной сложности
— теоретическое задание
— тема для самостоятельного изучения