Хеширование, множества и словари
Повторение
Байтовые строки
Каждый элемент байтовой строки – это байт.
Тип bytearray — это изменяемая байтовая строка.
Если мы хотим преобразовать байтовую строку в простую строку, нам необходимо знать кодировку.
Поговорим о хешировании и хеш-функции
Хеширование – это не взаимно-однозначное преобразование двух множеств разной мощности. Речь идет о конечных множествах.
Хеш-функция – легко вычислимая функция, преобразующая исходное сообщения произвольной длины в сообщение фиксированное длины, для которой не существует эффективного алгоритма поиска коллизий.
Хеш-таблиица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Случай, при котором хеш-функция преобразует несколько разных сообщений в одинаковые сводки называется «коллизией». Вероятность возникновения коллизий используется для оценки качества хеш-функций.
Качественная хеш-функция должна удовлетворять условию простого равномерного хеширования.
Простыми словами, равномерное покрытие означает, что в идеале функция (к примеру) преобразует миллион значений в тысячу значений. Для каждых из этих 1000 значений соответствует 1000 исходных таблиц. В действительности так не бывает. Но чем преобразование равномернее, тем удобнее хеш-функция. Если исходное подмножество области определения не очень большое, то например, в нашей программе будем использовать некоторое количество объектов. Это количество объектов будет, к примеру, 10 000 тысяч. Это ничтожно малое число. Если у нас хорошая хеш-функция, то может так случится, что для этих 10 000 константных объектов ни разу хеш-функция не совпадает, так как область значений это огромное целое число. Мощность области значений во много раз превышает множество тех объектов из области определения, которое мы взяли. Сама область определения, а именно все возможные объекты Питона, актуально бесконечная. Всех возможных значений питона огромное количество штук. Это число даже не сможем записать. Но формально это возможно. Поэтому было бы хорошо, если бы функция хеширования для небольшого подмножества имела уникальное хеширование . Еще одно свойство функции кеширование – это не восстановимость исходного объекта из его хеша. Это важно например при проверке паролей. Что бы не светить пароль, мы на стороне клиента передаем хеш в сервер, если он пришел на сервер, то пароль введен как надо. Или пользователь чудесным образом подобрал другой пароль, что хеши совпали. Последнее свойство – равномерное покрытие. Представим себе ситуацию, миллион исходных объектов и тысяча хешей. Предположим исходные объекты - это миллион чисел. Берем остаток от деления на тысячу, или поделим на тысячу нацело. Поэтому для миллиона чисел получилось тысяча значений хешей. Если взять 500 случайных чисел из диапазона от 1 до 1 000 000 у нас будет равномерно покрыта хеш-таблица в разных местах. Но если они идут подряд, наши исходные числа, например от 12 500 до 13 500. То будет ровно два значения хеш-функции 12 000 и 13 000. Т.е. отдельно смотрим, что бы для почти похожих объектов из области определения обеспечилось хорошее не равенство в области значения.
Хеш существует для любых константных объектов.
Задача – обеспечить отсутствие коллизии.
Задача: проверить, был ли один из 500 исходных элементов.
Эта задача константной сложности.
Хранится 1 бит (встречаемый\ не встречаемый). Из 500 элементов каждый раз вычисляем хеш и ставим 1 или 0 (1 – если есть, 0 – если нет). У рассуждений есть недостаток – идеальных функций не существует. Т.е. из одной области определения возвращается два одинаковых элемента из области значения.
Есть 2 способа сохранить и не потерять эффективность. Они заключаются в том, что бы хранить один бит и сам элемент. То есть высчитываем хеш, смотрим в таблицу и сравниваем входной элемент с элементом в хеш-таблице, если 1.
Теперь о различиях способов.
- Хранить не один элемент, а ведро. Хеш-таблица работает даже когда она идеально переполнена.
- Этот способ хороший, когда нельзя идеальную хеш-функцию. В хеш-таблице вычисляется хеш входного элемента и если там запись, что элемент был, то делаем повторное хеширование. Таблица должна быть в 3 раза больше, чем элементов. Поиск по таблице линейный.
Множества
Описываем множество константных объектов. Из этих объектов составляется хеш-таблица.
Для поддержки эффективности поиска применяется метод, который применяется в списках. Область памяти увеличивается в два раза.
Методы множества
set.add(elem) - добавляет элемент в множество. set.pop() - удаляет первый элемент из множества. Так как множества не упорядочены, нельзя точно сказать, какой элемент будет первым.
Множества не поддерживают индексацию.
Множество является последовательностью, то есть его можно превратить в список, кортеж или распаковать в любом месте, где распаковка последовательностей.
Поддерживаются теоретико-множественные операции.
Множество нельзя хешировать. Но есть замороженное множество.
У множества есть циклический конструктор.
Словари
Словарь – это та же хеш-таблица, но с ключом. Слева ключ, справа значение.
Для словарей так же есть циклический конструктор.
Методы словарей
dict.items() - возвращает пары (ключ, значение). dict.keys() - возвращает ключи в словаре. dict.setdefault - возвращает значение ключа, но если его нет, не бросает исключение, а создает ключ с значением default (по умолчанию None). dict.values() - возвращает значения в словаре.