Грязные трюки-2: использование хеша
- Задачи, требующие хеширования данных
- Хеш-таблицы: сегменты и ячейки
- Хеш-функция и её свойства: равномерность, соотношение ОО и ОЗ
- Хорошие и плохие хеш-функции
Функция hash(), реализация словаря в Python
Домашнее задание
Прочитать про хеширование на Википедии - Придумать свою хеш-функцию для:
- длинных строк
- косинусов произвольных углов
Написать программу, поиска строк с одинаковым значением hash()
- Убедиться, что метод «в лоб» не находит таких строк
С другой стороны, хеш длинной строки явно короче самой строки, следовательно хеши длинных строк могут совпадать. Как бы их найти? А вот и нет! Чем строка длиннее, тем длиннее hash(), так что они, похоже, однозначные! -- FrBrGeorge
Решить предыдущее Д/З
Условные обозначения
— тема по Linux - — тема повышенной сложности
- — теоретическое задание
— тема для самостоятельного изучения