Проблеми колізій та методи їх вирішення

7.1 Визначення колізій у хеш-таблиці

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

Приклад колізії:

Припустимо, у нас є проста хеш-функція, яка повертає залишок від ділення ключа на розмір таблиці. Для ключів 5 і 15 при розмірі таблиці 10 обидва ключі дадуть однаковий індекс: 5 % 10 = 5 і 15 % 10 = 5. Це колізія.

Ще приклад:

Допустимо, ви складаєте словник імен, і у вас є проста хеш-функція, яка повертає першу букву імені. Але виявляється, що 80% імен починаються на букву «А». Це не просто колізія, це проблема.

7.2 Методи вирішення колізій – ланцюжки

Існує кілька методів вирішення колізій у хеш-таблицях. Два найбільш поширених методи — це ланцюжки (chaining) і відкрита адресація (open addressing).

Ланцюжки (Chaining)

Переваги:

• Простота реалізації.
• Ефективність при невеликій кількості колізій.
• Менша залежність від щільності заповнення хеш-таблиці.

Недоліки:

• Потребує додаткової пам'яті для вказівників у зв'язному списку.
• Продуктивність може падати при великій кількості колізій через довгі ланцюжки.

Приклад реалізації методу ланцюжків:

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

class HashTableChaining:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    # Вставка пари ключ-значення
    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

    def search(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return None
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

    def delete(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return

# Приклад використання:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Вивід: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # Вивід: None

7.3 Метод номер два – відкрита адресація

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

Переваги:

• Не потребує додаткової пам'яті для зберігання вказівників.
• Більш компактне представлення даних.

Недоліки:

• Продуктивність може значно падати при високій щільності заповнення таблиці.
• Потребує більше обчислювальних ресурсів для вирішення колізій.

Приклади стратегій відкритої адресації

Лінійне пробування (Linear Probing):

• Пробування з кроком 1: index = (index + 1) % size.
• Просте, але може призвести до "кластеризації".

Квадратичне пробування (Quadratic Probing):

• Пробування з кроком, що збільшується по квадрату: index = (index + i^2) % size.
• Зменшує проблему кластеризації, але складніше у реалізації.

Подвійне хешування (Double Hashing):

• Використання другої хеш-функції для обчислення кроку: index = (index + i * hash2(key)) % size.
• Менше проблем з кластеризацією, але складніше у реалізації.

Приклад реалізації методу відкритої адресації (лінійне пробування): Я наведу повний робочий код, для простоти можете розібрати тільки роботу функції insert

class HashTableOpenAddressing:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    # Вставка пари ключ-значення
    def insert(self, key, value):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

    def delete(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None
                return
            index = (index + 1) % self.size
            if index == original_index:
                break

# Приклад використання:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Вивід: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # Вивід: None

7.4 Вплив колізій на хеш-таблицю

Вплив колізій на продуктивність.

Середній час доступу:

• В ідеальних умовах (за відсутності колізій) середній час доступу до елементів у хеш-таблиці становить O(1).
• Колізії збільшують час доступу, оскільки потрібна обробка ланцюжків або пробування клітинок, що збільшує кількість операцій.

Збільшення довжини ланцюжків:

• У методі ланцюжків збільшення довжини ланцюжків при великій кількості колізій може призвести до лінійного часу доступу O(n) для операцій пошуку, вставки та видалення.
• Довгі ланцюжки збільшують кількість порівнянь, необхідних для пошуку або вставки елемента.

Просторова складність:

• У методі ланцюжків потрібно додаткову пам'ять для зберігання вказівників у зв'язних списках.
• У методі відкритої адресації заповнення таблиці вище певного рівня (зазвичай близько 70-80%) значно збільшує кількість колізій і, отже, час доступу.

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

Приклад аналізу впливу колізій на продуктивність:

Це прямо для любителів копати глибше

import time
import random

# Лінійне пробування
class HashTableOpenAddressing:
    def __init__(self, size):
        # Ініціалізація
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    # Вставка пари ключ-значення
    def insert(self, key, value):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

# Генерація великої кількості даних для вставки
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]

# Вставка даних і вимірювання часу
start_time = time.time()
for key in keys:
    hash_table.insert(key, key)
print(f"Час вставки: {time.time() - start_time:.6f} секунд")

# Пошук даних і вимірювання часу
start_time = time.time()
for key in keys:
    hash_table.search(key)
print(f"Час пошуку: {time.time() - start_time:.6f} секунд")