Хеширование, множества и словари
Разбор Д/З
Повторение: строки
- как последовательности (+особенности)
- строковые методы
- байтовые строки и кодировки
Хеширование
Определение: (f(x)=y: {y} << {x})
- Возможные свойства и их применение:
- равномерное покрытие ОЗ — хеш-таблицы
- вероятная однозначность на небольшом подмножестве ОО — идентификация
невосстановимость x из y — шифрование
разброс (в т. ч. для почти похожих x) — много где
hash()
- только константные объекты
- Понятие об идеальной хеш-таблице, поиск в ней
- Разрешение коллизий ключей в хеш-таблице: «вёдра» vs повторное хеширование
Множества
- (это хеш-таблиы, как они есть)
- Конструктор (в т. ч. циклический)
- операции и методы
- использование
- …
+frozenset
Словари
Хешируется ключ, а хранится произвольный объект ⇒ ассоциативный массив, хеш ключа в качестве индекса объекта
- Конструктор словаря (+циклический)
- методы
- использование
- …
почему нет frozendict?
Устройство современных (Python3.6+) словарей (описано здесь): прямая таблица объектов + хеш-таблица индексов + пометка на удаление вместо удаления + переупаковка
- (если успеем) вся правда о пространствах имён
- (если успеем) именные параметры функций
Д/З
- Почитать
Про хеширование в документации, и далее п ссылкам
требуемые свойства метода .__hash__()
отмена рандомизации хеша с помощью переменной окружения PYTHONHASHSEED
Про множества в учебнике и в документации
Про словари в учебнике и в документации
Разобраться с кодом, имитирующим хеш-таблицы
- Задать вопросы, если что непонятно
EJudge: ThreeSquares 'Три квадрата'
Ввести произвольную последовательность (не обязательно кортеж) натуральных чисел, не превышающих 1000000. Вывести, сколько среди них различных чисел, являющихся суммой трёх квадратов.
Пояснение. Поскольку входная последовательность обрабатывается eval(), она может быть, например, такой: (1+i%10 for i in range(100000)), в этом случае ответ — тоже 3
3, 4, 2, 9, 1, 5, 6, 7, 8, 3, 6
3
TODO
- разбор задачи