Хеширование, множества и словари
Разбор Д/З
Повторение: строки
- как последовательности (+особенности)
- строковые методы
- байтовые строки и кодировки
Хеширование
Определение: (f(x)=y: {y} << {x})
- Возможные свойства и их применение:
- равномерное покрытие ОЗ — хеш-таблицы
- вероятная однозначность на небольшом подмножестве ОО — идентификация
невосстановимость x из y — шифрование
разброс (в т. ч. для почти похожих x) — много где
hash()
- только константные объекты
- Понятие об идеальной хеш-таблице, поиск в ней
- Разрешение коллизий ключей в хеш-таблице: «вёдра» vs повторное хеширование
Множества
- (это хеш-таблиы, как они есть)
- Конструктор (в т. ч. циклический)
- операции и методы
- использование
- …
+frozenset
Словари
Хешируется ключ, а хранится произвольный объект ⇒ ассоциативный массив, хеш ключа в качестве индекса объекта
- Конструктор словаря (+циклический)
- методы
- использование
- …
почему нет frozendict?
Устройство современных (Python3.6+) словарей (описано здесь): прямая таблица объектов + хеш-таблица индексов + пометка на удаление вместо удаления + переупаковка
- (если успеем) вся правда о пространствах имён
- (если успеем) именные параметры функций
Д/З
- Почитать
Про хеширование в документации, и далее п ссылкам
требуемые свойства метода .__hash__()
отмена рандомизации хеша с помощью переменной окружения PYTHONHASHSEED
Про множества в учебнике и в документации
Про словари в учебнике и в документации
Разобраться с кодом, имитирующим хеш-таблицы
- Задать вопросы, если что непонятно
TODO
- разбор задачи