Хеш-функция — это функция, которая принимает входные данные (ключ) и возвращает фиксированное число, называемое хешем (или хеш-значением). Основная цель хеш-функции — преобразовать произвольные данные в числовое значение определенного диапазона.
🚩Основные свойства хеш-функции:
🟠 Детерминированность: Хеш-функция всегда должна возвращать одно и то же хеш-значение для одного и того же входного значения.
🟠Равномерное распределение: Хорошая хеш-функция должна равномерно распределять хеш-значения по всему диапазону, чтобы минимизировать количество коллизий.
🟠Быстрота вычисления: Хеш-функция должна быть достаточно быстрой, чтобы не замедлять общую производительность алгоритмов, которые её используют.
🟠Минимизация коллизий: Коллизия возникает, когда два разных входных значения дают одно и то же хеш-значение. Хорошая хеш-функция должна минимизировать вероятность таких случаев.
🚩Применение хеш-функций:
🟠Хеш-таблицы: Используются для вычисления индекса массива, где будет храниться значение, связанное с ключом. Это позволяет быстро выполнять операции вставки, удаления и поиска.
🟠Криптография: Криптографические хеш-функции (например, SHA-256, MD5) используются для обеспечения целостности данных, создания цифровых подписей и безопасного хранения паролей.
🟠Контроль целостности данных: Хеш-функции применяются для проверки целостности данных при передаче или хранении, позволяя выявлять ошибки или изменения в данных.
🟠Генерация уникальных идентификаторов: Хеш-функции используются для генерации уникальных идентификаторов (например, UUID), основываясь на входных данных.
🚩Примеры хеш-функций
🟠Простая хеш-функция: Эта функция возвращает остаток от деления длины ключа на размер таблицы. Она проста, но не обеспечивает равномерное распределение.
def simple_hash(key, table_size):
return len(key) % table_size
🟠Хеш-функция для строк (например, DJB2):
def djb2_hash(key):
hash_value = 5381
for char in key:
hash_value = ((hash_value << 5) + hash_value) + ord(char) # hash_value * 33 + ord(char)
return hash_value
🚩Методы разрешения коллизий
🟠Метод цепочек (chaining): В каждой ячейке массива хранится список значений, которые хешируются в один и тот же индекс.
🟠Открытая адресация (open addressing): При коллизии ищется другая свободная ячейка по определённому алгоритму (например, линейное пробирование, квадратичное пробирование или двойное хеширование).
Ставь 👍 и забирай 📚 Базу знаний