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

• Хеш-функуия — преобразование объекта в число
• Свойства хеш-функции:
  • равномерность
  • ограниченность

• hash() — хеш-дайджест объекта, хешируемые объекты

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

Пара ссылок о том, как реализованы словари (и множества) в Python:

• На stackoverflow

• На laurentluce

Домашнее задание

1. прочитать про множества и словари в учебнике

2. Дорешать задачу о спиральном заполнении массива
3. Решить с помощью множеств следующую задачу. Ввести строку, разбить её на слова. Составить множества слов:
   • содержащих букву «b»
   • длиннее 5 букв
   • имеющих повторяющиеся буквы (например, «baobab»)
   • не имеющих гласных (будем считать, что гласные — это «aouie» Вывести без повторений все слова без «b» длиннее 5 букв вместе со словами с гласными и повторяющимися буквами
4. Ввести текст и посчитать количество вхождений каждого слова в него (использовать словарь). Найти самое частое слово.

Условные обозначения

• — тема по Linux

• ­— тема повышенной сложности

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh