Проблемы коллизий и методы их решения

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} секунд")