Поняття хеш-функції

5.1 Визначення хеш-функції і її застосування

Хеш-функція — це функція, яка приймає вхідні дані (або ключ) і повертає фіксований розмір бітів, зазвичай званий хешем або хеш-значенням. Основне призначення хеш-функції — ефективний розподіл даних по хеш-таблиці для забезпечення швидкого доступу до елементів.

Застосування:

• Хеш-таблиці: Використовуються для реалізації асоціативних масивів (словники в Python), забезпечуючи швидкий доступ до даних за ключем.
• Контроль цілісності даних: Хеш-функції застосовуються для перевірки цілісності файлів і даних (наприклад, алгоритми MD5, SHA-1, SHA-256).
• Криптографія: Хеш-функції використовуються в криптографічних алгоритмах для шифрування та створення цифрових підписів.
• Пошукові системи: Застосовуються для індексації даних і швидкого пошуку інформації.
• Управління кешем: Використовуються для організації кешей, щоб швидко знаходити дані.

Приклад застосування хеш-функції в Python:

# Приклад використання хеш-функції в Python для хеш-таблиці (словника)
data = {"apple": 1, "banana": 2, "cherry": 3}

# Отримання хеш-значення ключа
key = "banana"
hash_value = hash(key)

print(f"Хеш-значення для ключа '{key}': {hash_value}")

5.2 Аналогії з реального життя

За допомогою хеш-функції можна розбити велику групу об'єктів на приблизно рівні групи. Більше того, якщо продовжити додавати нові об'єкти, то вони продовжать рівномірно розподілятися по групах.

Припустимо, у вас є 1000 людей, і вам потрібно розподілити їх по 30 групах. Ось як це можна зробити.

Спосіб 1. За першою буквою імені.

Перша група — це всі, у кого ім'я на «А», друга група — це всі, у кого ім'я на «Б», і так далі. Правило «Твоя група — це перша буква твого імені» — це і є хеш-функція. Але з такою хеш-функцією ми ризикуємо отримати багато людей у групі «А» і мало в «Е».

Спосіб 2. За датою народження.

Народився першого числа будь-якого місяця — перша група, другого — друга, і так далі. Буде 31 група. В 31-й групі людей буде десь у 2 рази менше, ніж в інших, але люди в таких групах набагато рівномірніше розподілені, ніж у першому випадку.

Спосіб 3. Номер телефону

Ідеальний варіант — це отримати таке число, яке було б, з одного боку, максимально випадковим (тоді такі числа будуть рівномірно розподілені), з іншого боку — воно повинно завжди швидко обчислюватися і бути одним і тим же.

Давайте візьмемо 4 останні цифри номера телефону — це буде 10 000 варіантів. А потім поділимо це число націло на 30. Тоді у нас буде 30 можливих остач від ділення: 0, 1, 2, ..., 29. Це і будуть номери наших груп.

Корисно! До речі, майже будь-яка хеш-функція використовує остачу від ділення націло — це дуже просто і дозволяє регулювати кількість груп, на які потрібно розбити елементи.

5.3 Основні властивості хеш-функції

Основні властивості хорошої хеш-функції:

Детермінованість: Одна і та ж хеш-функція завжди повинна повертати одне і те ж хеш-значення для одного і того ж вхідного значення.

Приклад:

key = "example"
assert hash(key) == hash(key)

Важливо! Оператор assert перевіряє, що справа від нього знаходиться істинне True вираз. Якщо вираз не істинний False, то буде викинуто виняток.

Рівномірність: Хороша хеш-функція повинна рівномірно розподіляти значення по всьому діапазону можливих хеш-значень, щоб уникнути колізій.

Приклад із життя Python-розробника: В словнику (клас dict) Python хеш-функція hash() розподіляє ключі рівномірно.

Ефективність обчислення: Хеш-функція повинна бути швидкою і ефективною, щоб не уповільнювати операції вставки і пошуку.

Приклад із життя Python-розробника: Стандартні хеш-функції в Python реалізовані для роботи з ключами різних типів, таких як рядки і числа.

Мінімізація колізій: Колізія відбувається, коли два різних ключі мають однакове хеш-значення. Хороша хеш-функція повинна мінімізувати ймовірність колізій.

Приклад із життя Python-розробника: Алгоритм SHA-256 мінімізує ймовірність колізій при хешуванні даних.

Розподіл хешів: Для великих обсягів даних хеш-функція повинна забезпечувати рівномірний розподіл хеш-значень по всій хеш-таблиці.

Приклад із життя Python-розробника: Стандартні хеш-функції в Python добре справляються з розподілом ключів у хеш-таблицях.

5.4 Приклади хеш-функцій та їх реалізація

Хеш-функції приймають на вхід дані довільного розміру і повертають фіксований розмір хеш-значення. Розглянемо кілька прикладів хеш-функцій і їх реалізацію.

Приклад 1: Проста хеш-функція для рядків

Одна з найпростіших хеш-функцій для рядків може бути реалізована з використанням суми кодів символів рядка:

def simple_hash(key):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % 1000  # Припустимо, що наша таблиця має розмір 1000

# Приклад використання:
key = "example"
print(f"Хеш-значення для ключа '{key}': {simple_hash(key)}")

Приклад 2: Хеш-функція для рядків з використанням поліноміального хешування

Поліноміальне хешування є більш складною, але ефективною технікою:

def polynomial_hash(key, a=33, m=1000):
    hash_value = 0
    for char in key:
        hash_value = (hash_value * a + ord(char)) % m
    return hash_value

# Приклад використання:
key = "example"
print(f"Хеш-значення для ключа '{key}': {polynomial_hash(key)}")

Приклад 3: Вбудована хеш-функція в Python

Python надає вбудовану функцію hash() для отримання хеш-значення для різних типів даних:

key = "example"
print(f"Хеш-значення для ключа '{key}': {hash(key)}")

Приклад 4: Криптографічна хеш-функція (SHA-256)

Криптографічні хеш-функції, такі як SHA-256, використовуються для забезпечення безпеки даних:

import hashlib

def sha256_hash(key):
    return hashlib.sha256(key.encode()).hexdigest()

# Приклад використання:
key = "example"
print(f"Хеш-значення для ключа '{key}': {sha256_hash(key)}")

5.5 Вступ до хешування і його застосування

Хешування — це процес перетворення вхідних даних довільного розміру у фіксований розмір хеш-значення з використанням хеш-функції. Хешування широко використовується в комп'ютерних науках і програмуванні для оптимізації і забезпечення безпеки.

Основні застосування хешування:

1. Хеш-таблиці (словники): Хеш-таблиці використовують хеш-функції для організації і швидкого доступу до даних.

data = {"apple": 1, "banana": 2, "cherry": 3}
key = "banana"
hash_value = hash(key)
print(f"Хеш-значення для ключа '{key}': {hash_value}")

2. Контроль цілісності даних: Хеш-функції використовуються для перевірки цілісності файлів і даних.

Приклад: Перевірка цілісності файлу з використанням SHA-256:

import hashlib

def get_file_hash(file_path):
    hasher = hashlib.sha256()
    with open(file_path, 'rb') as file:
        buf = file.read()
        hasher.update(buf)
    return hasher.hexdigest()

file_hash = get_file_hash('example.txt')
print(f"SHA-256 хеш файлу: {file_hash}")

3. Криптографія і безпека: Хеш-функції використовуються для створення криптографічних примітивів, таких як цифрові підписи і хеші паролів.

Приклад: Хешування пароля з використанням SHA-256:

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

password = "securepassword"
hashed_password = hash_password(password)
print(f"Хеш пароля: {hashed_password}")

4. Пошукові системи і індексація: Хешування застосовується для створення індексів і швидкого пошуку даних.

Приклад: Створення індексу для текстового пошуку:

def create_index(text):
    index = {}
    for word in text.split():
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

text = "This is an example text for indexing"
index = create_index(text)
print(f"Індекс: {index}")

5. Управління кешем: Хешування використовується для організації кешей, щоб швидко знаходити дані.

Приклад: Простий кеш з використанням хеш-функції:

cache = {}

def get_from_cache(key):
    hash_key = hash(key)
    return cache.get(hash_key, None)

def add_to_cache(key, value):
    hash_key = hash(key)
    cache[hash_key] = value

# Додавання і отримання даних з кешу
add_to_cache("test_key", "test_value")
print(get_from_cache("test_key"))  # Вивід: test_value