Хеш-функції та їх застосування

10.1 Вступ до хеш-функцій та хеш-таблиць

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

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

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

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

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

Хеш-таблиці забезпечують швидкий доступ до даних, зазвичай зі складністю O(1) у середньому випадку.

Застосування хеш-функцій у реальному житті

Приклад: Блокчейн-технології

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

import hashlib
import time

class Block:
    def __init__(self, data, previous_hash):
        self.timestamp = time.time()
        self.data = data
        self.previous_hash = previous_hash
        self.hash = self.calculate_hash()

    def calculate_hash(self):
        hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
        return hashlib.sha256(hash_string.encode()).hexdigest()

# Приклад використання
block1 = Block("Транзакція 1", "0")
block2 = Block("Транзакція 2", block1.hash)
print(f"Хеш блока 1: {block1.hash}")
print(f"Хеш блока 2: {block2.hash}")

Порівняння продуктивності

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

import time

def find_duplicates_with_hash(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

def find_duplicates_without_hash(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

# Тест продуктивності
arr = list(range(10000)) + list(range(5000))  # Масив з дублікатами

start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"Час виконання з хеш-таблицею: {end - start} секунд")

start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"Час виконання без хеш-таблиці: {end - start} секунд")

Запустіть програму і переконайтесь, наскільки використання хеш-таблиці прискорює пошук дублікатів. Особливо на великих масивах даних.

10.2 Приклади застосування хеш-функцій у реальних задачах

1. Хешування паролів

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

Приклад реалізації:

import hashlib

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

# Приклад використання:
password = "securepassword"
hashed_password = hash_password(password)
print(f"Хеш пароля: {hashed_password}")

2. Контроль цілісності даних

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

Приклад реалізації:

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. Пошукові системи та індексація

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

Приклад реалізації:

def create_index(text):
    index = {}
    words = text.split()
    for word in words:
        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}")

10.3 Оптимізація пошуку з використанням хеш-функцій

1. Використання хеш-таблиць для пошуку дублікатів

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

Приклад реалізації:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Приклад використання:
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Вивід: [2, 4]

2. Оптимізація пошуку пар із заданою сумою

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

Приклад реалізації:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# Приклад використання:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Вивід: [(4, 2), (3, 3), (8, -2)]

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

1. Підрахунок кількості слів у тексті

Використовуйте хеш-таблицю для підрахунку кількості входжень кожного слова в тексті.

Приклад реалізації:

def count_words(text):
    word_count = {}
    words = text.split()

    for word in words:
        if word in word_count:
            word_count[word] += 1
        else:
            word_count[word] = 1

    return word_count

# Приклад використання:
text = "this is a test this is only a test"
print(count_words(text))  # Вивід: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}

2. Перевірка перетину двох масивів

Перевірте, чи перетинаються два масиви (мають хоча б один спільний елемент).

Приклад реалізації:

def has_intersection(arr1, arr2):
    set1 = set(arr1)
    for item in arr2:
        if item in set1:
            return True
    return False

# Приклад використання:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2))  # Вивід: True
print(has_intersection(arr1, arr3))  # Вивід: False

3. Перевірка унікальності елементів у масиві

Перевірте, чи містить масив лише унікальні елементи.

Приклад реалізації:

def all_unique(arr):
    seen = set()
    for item in arr:
        if item in seen:
            return False
        seen.add(item)
    return True

# Приклад використання:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1))  # Вивід: True
print(all_unique(arr2))  # Вивід: False