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