Хеширование, множества и словари

Разбор Д/З

Повторение: строки

• как последовательности (+особенности)
• строковые методы
• байтовые строки и кодировки

Хеширование

• Определение: (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

  Input:

  3, 4, 2, 9, 1, 5, 6, 7, 8, 3, 6

  Output:

  3

TODO

• разбор задачи