Pythoner
Фотография
✈️Хэш-функции играют важную роль в компьютерных науках, особенно в структурах данных и криптографии. В этой статье мы рассмотрим различные типы хэш-функций, реализованные на Python, и проанализируем их характеристики.
🔎 Типы хэш-функций
➡️1. Простая хэш-функция (simple_hash)
Эта функция суммирует ASCII-значения символов входной строки и применяет операцию модуля. Она проста в реализации, но может привести к неравномерному распределению.
def simple_hash(input_str, table_size):
hash_value = 0
for char in input_str:
hash_value += ord(char)
return hash_value % table_size
➡️2. Полиномиальный хэш (polynomial_hash)
Использует полиномиальное накопление ASCII-значений с простым числом, что позволяет придать больший вес символам в начале строки.
def polynomial_hash(input_str, table_size, prime=31):
hash_value = 0
for i, char in enumerate(input_str):
hash_value += ord(char) * (prime ** i)
return hash_value % table_size
➡️3. FNV-1a хэш (fnv1a_hash)
32-битная версия FNV-1a хэша, известная своими хорошими характеристиками распределения.
def fnv1a_hash(key, table_size):
FNV_prime = 16777619
FNV_offset_basis = 2166136261
hash_value = FNV_offset_basis
for char in key:
hash_value ^= ord(char)
hash_value *= FNV_prime
hash_value &= 0xffffffff # Обеспечивает 32-битный хэш
return hash_value % table_size
➡️4. XXХэш (xx_hash)
Использует библиотеку xxhash для быстрого некриптографического хэширования, эффективного для больших объемов данных.
def xx_hash(input_str, table_size):
return xxhash.xxh32(input_str).intdigest() % table_size
➡️5. SipHash (sip_hash)
Применяет HMAC с SHA-256 для повышенной безопасности, но может быть медленнее некриптографических хэшей.
def sip_hash(input_str, table_size, key=b'secretkey'):
hash_value = hmac.new(key, input_str.encode(), digestmod='sha256').hexdigest()
return int(hash_value, 16) % table_size
➡️6. MurmurHash (murmur_hash)
Быстрая некриптографическая хэш-функция, часто используемая в хэш-таблицах и фильтрах Блума.
def murmur_hash(input_str, table_size):
hash_value = mmh3.hash(input_str) % table_size
return hash_value
🐍Pythoner
31 · 2.1K ·