Принципы работы хеш-таблиц

6.1 Определение хеш-таблицы и её структура

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

Важные аспекты хеш-таблицы

Массив – это основной компонент хеш-таблицы, он хранит указатели на элементы или списки элементов.

Хеш-функция: Функция, которая преобразует ключи словаря в индексы массива.

Коллизии: Ситуация, когда два разных ключа имеют одинаковое хеш-значение. Для разрешения коллизий используются различные методы, такие как цепочки (chaining) или открытая адресация (open addressing).

Пример словаря:

{
   "apple": 101,
   "banana": 102,
   "cherry": 103
}

Пример структуры хеш-таблицы:

6.2 Основные операции в хеш-таблице

Основные операции в хеш-таблице: вставка, поиск, удаление

1. Вставка (Insertion): Процесс добавления нового элемента (пары ключ-значение) в хеш-таблицу.

Шаги вставки:

1. Вычислить хеш-значение ключа с помощью хеш-функции.
2. Найти индекс в массиве на основе хеш-значения.
3. Если в массиве по этому индексу уже есть элемент (коллизия), добавить элемент в список (в случае цепочек) или найти следующий доступный индекс (в случае открытой адресации).

Пример вставки в хеш-таблицу с использованием цепочек:

class HashTable:
    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))

# Пример использования:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. Поиск (Search): Процесс нахождения значения по заданному ключу в хеш-таблице.

Шаги поиска:

1. Вычислить хеш-значение ключа с помощью хеш-функции.
2. Найти индекс в массиве на основе хеш-значения.
3. Проверить наличие ключа в списке элементов (в случае цепочек) или по индексу (в случае открытой адресации).

Пример поиска в хеш-таблице с использованием цепочек:

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

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

    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

# Пример использования:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Вывод: 2
print(hash_table.search("grape"))   # Вывод: None

3. Удаление (Deletion): Процесс удаления элемента (пары ключ-значение) из хеш-таблицы.

Шаги удаления:

1. Вычислить хеш-значение ключа с помощью хеш-функции.
2. Найти индекс в массиве на основе хеш-значения.
3. Удалить элемент из списка (в случае цепочек) или установить значение по индексу в None (в случае открытой адресации).

Пример удаления из хеш-таблицы с использованием цепочек:

class HashTable:
    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 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 = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # Вывод: None

6.3 Временная сложность хеш-таблицы

Временная сложность операций в хеш-таблице

Вставка (Insertion):

• Средний случай: O(1)
• Худший случай: O(n) (в случае большого количества коллизий или если все элементы попадают в одно и то же место)

Поиск (Search):

• Средний случай: O(1)
• Худший случай: O(n) (в случае большого количества коллизий или если все элементы попадают в одно и то же место)

Удаление (Deletion):

• Средний случай: O(1)
• Худший случай: O(n) (в случае большого количества коллизий или если все элементы попадают в одно и то же место)

Пояснение:

Средний случай: В среднем случае хеш-функция равномерно распределяет элементы по таблице, и каждый элемент находится в своей уникальной ячейке, что обеспечивает постоянное время доступа O(1).

Худший случай: В худшем случае все элементы попадают в одну ячейку из-за плохой хеш-функции или большого количества коллизий. Тогда хеш-таблица превращается в связный список, и временная сложность операций становится O(n).

6.4 Примеры использования хеш-таблиц

1. Реализация словаря (ассоциативного массива)

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

Пример:

# Создание словаря
dictionary = {}

# Вставка элементов
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# Поиск элемента
print(dictionary["banana"])  # Вывод: 2

# Удаление элемента
del dictionary["cherry"]

# Проверка существования ключа
if "apple" in dictionary:
    print("Ключ 'apple' существует в словаре")  # Вывод: Ключ 'apple' существует в словаре

Теперь вы немного больше знаете о словаре в Python и о том, как он устроен.

2. Кэширование результатов вычислений

Хеш-таблицы используются для кэширования результатов дорогостоящих вычислений для ускорения последующих запросов.

Пример:

# Кэш для хранения результатов
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # Пример дорогостоящего вычисления
    cache[x] = result
    return result

# Использование кэша
print(expensive_computation(10))  # Вывод: 100 (вычисление и кэширование)
print(expensive_computation(10))  # Вывод: 100 (из кэша)

3. Подсчёт частоты слов в тексте

Хеш-таблицы используются для подсчёта количества вхождений каждого слова в тексте.

Пример:

from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# Вывод результатов
for word, count in word_count.items():
    print(f"Слово '{word}' встречается {count} раз(а)")

4. Поиск дубликатов в списке

Хеш-таблицы используются для эффективного поиска дубликатов в списке.

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]