Хеш-таблица

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

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

Действие Массив/связный список Хеш-таблица
Поиск O(n) O(1)
Вставка O(n) O(1)
Delete O(n) O(1)
Эффективность использования памяти Высокая Средняя

Хеш-таблицаПрямо как умная система шкафчиков:

  • Традиционный шкафчик: Нужно помнить, в каком шкафчике находится каждый предмет (линейный поиск)
  • Умный шкафчик: вы сообщаете администратору название предмета, и он сразу говорит вам номер шкафчика (поиск по хешу)

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

Пример из реальной жизни:

  • Поиск по словарю: быстро находите страницу по первой букве слова
  • Телефонная книга: сортировка по пиньиню фамилии для быстрого поиска контактов
  • Библиотечный шифр: сразу находите место на полке по классификационному номеру

Представьте, что у вас огромная библиотека с тысячами книг.

Если вы хотите найти конкретную книгу, например «Гарри Поттера», что бы вы сделали? Самый глупый способ — начать с первой книги на первой полке и просматривать одну за другой, пока не найдёте её, — это может занять часы или даже дни!

Что бы сделал умный библиотекарь? Он использовал бысистему индексации: основываясь на некотором правиле названия книги или имени автора (например, первой букве), быстро определить примерную область, где находится книга, и затем искать только в этой небольшой области. Идея этой системы индексации —Хеш-таблица— ядро этого.


Основные концепции

Что такое хеш-таблица?

Хеш-таблица — это структура данных, которая напрямую обращается к значениям по ключам., в ней используется нечто под названиемхеш-функция— волшебная формула, преобразующая ключ произвольного размера (например, строку, число или объект) в число фиксированного размера, называемое хеш-значением.Значение хешаилиХеш-кодЗатем используйте это значение хеша какИндексиндекс массива, и сохраните значение в позиции массива, соответствующей этому индексу.

Этот процесс похож на то, как если бы каждому ключу присвоили уникальный номер места (значение хеша), а затем сказали ему: ваши данные находятся в месте с этим номером. Когда вы захотите найти эти данные, вы просто пересчитываете номер места по тому же правилу и идёте прямо к нему — не нужно проверять место за местом.

Основные компоненты

Хеш-таблица в основном состоит из следующих трёх ключевых частей:

  1. Ключ: идентификатор, который вы используете при сохранении и поиске данных. Например, в телефонной книге имя человека — это ключ.
  2. Значение: фактические данные, связанные с ключом. В телефонной книге номер телефона — это значение.
  3. Хеш-функция (Hash Function): математическая функция, которая сопоставляет ключи с индексами массива. Это сердце хеш-таблицы.

Схема работы

Давайте рассмотрим простой пример. Предположим, мы хотим создать телефонную книгу, которая сопоставляет имена с номерами телефонов.

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

Проектирование хеш-функции

Характеристики хорошей хеш-функции

Особенности Описание Важность
Детерминированность Одинаковый вход всегда даёт одинаковый выход ⭐⭐⭐⭐⭐
Равномерное распределение Выход равномерно распределён в пределах диапазона хеш-таблицы ⭐⭐⭐⭐⭐
Эффективные вычисления Процесс вычисления прост и быстр ⭐⭐⭐⭐
Лавинный эффект Крошечное изменение входных данных вызывает огромное изменение выходных данных ⭐⭐⭐

Распространённые хеш-функции

Type Пример Применимые сценарии
Метод деления с остатком hash = key % table_size Целочисленный ключ
Метод умножения hash = floor(key * A % 1 * table_size) Ключ с плавающей запятой
Метод анализа цифр Анализ закономерностей распределения чисел Данные с определёнными закономерностями
Метод середины квадрата hash = (key * key) // 10^(n/2) % table_size Числовой ключ
Хеширование строк Посимвольная обработка Строковый ключ

Методы разрешения коллизий

Метод цепочек

Особенности Описание Временная сложность
Принцип Каждая корзина хеш-таблицы хранит связный список
Вставка Добавить в начало соответствующего связанного списка O(1)
Поиск Поиск в соответствующем связанном списке O(k), где k — длина связанного списка
Delete Удалить из соответствующего связанного списка O(k)
Накладные расходы памяти Требует дополнительной памяти для указателей Относительно большие

Метод открытой адресации (Open Addressing)

Type Последовательность проб Преимущества Недостатки
Линейное пробирование h, h+1, h+2, ... Простой и лёгкий в реализации Склонность к кластеризации
Квадратичное пробирование h, h+1², h+2², ... Снижает кластеризацию Возможно, не удастся проверить все позиции
Двойное хеширование h, h+hash2(key), h+2*hash2(key), ... Равномерное распределение Вычислительно сложный

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

Сравнение методов разрешения конфликтов


Углублённое понимание хеш-функций

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

  • Детерминированность: Один и тот же ключ всегда должен давать одно и то же хеш-значение.
  • Эффективность: Скорость вычислений должна быть высокой.
  • Равномерное распределение: Позволяет отображать разные ключи как можно более равномерно по всему пространству массива, уменьшая количество коллизий.

Пример простой хеш-функции

Предположим, наши ключи — строки, а длина массива равна 10. Простой хеш-функцией могла бы быть сумма ASCII-кодов каждого символа строки, затем взятие остатка по модулю длины массива.

Пример

def simple_hash(key, array_size):
    """
Простая хеш-функция для строк.
:param key: Входной ключ (строка)
:param array_size: Размер массива хеш-таблицы
:return: Вычисленный индекс массива
    """

    total = 0
    for char in key:
        # Преобразовать символ в его ASCII-код и накопить значение
        total += ord(char)
    # Взять остаток от деления на размер массива, чтобы индекс не выходил за пределы массива
    return total % array_size

# Протестировать нашу хеш-функцию
keys_to_test = ["Alice", "Bob", "Charlie", "David"]
array_size = 10

print("Результаты теста простой хеш-функции:")
for key in keys_to_test:
    hash_index = simple_hash(key, array_size)
    print(fКлюч '{key}' -> индекс хеша: {hash_index})

Результат вывода:

简单哈希函数测试结果:
  键 'Alice' -> 哈希索引: 0
  键 'Bob' -> 哈希索引: 8
  键 'Charlie' -> 哈希索引: 5
  键 'David' -> 哈希索引: 3

Эта функция проста, но может быть не лучшей, потому что разные строки могут давать одинаковую сумму (например, ab и ba), что приводит кхеш-коллизии。


Хеш-конфликты и методы их разрешения

Хеш-коллизияколлизии. Коллизия — это когда два или более разных ключа после обработки хеш-функцией дают один и тот же индекс массива. Это как двум зрителям кинотеатра назначают одно и то же место, что явно проблема. Коллизии неизбежны, потому что диапазон хеш-значений (размер массива) обычно конечен, а возможные ключи бесконечны.

Существует два основных классических метода разрешения конфликтов:

Метод 1: метод цепочек

Это самый распространённый метод. Он не размещает данные непосредственно в каждой позиции массива; вместо этого он хранит вСвязный списоксвязный список (или другую структуру данных, например красно-чёрное дерево) в каждой позиции массива. Когда возникает коллизия, новая пара ключ-значение добавляется в связный список в этой позиции.

Описание процесса:

Вычислите хеш-значение ключа и найдите индекс массива.

  • Если связанный список в этой позиции индекса пуст, создайте новый узел для хранения пары ключ-значение.
  • Если связанный список не пуст (произошла коллизия), пройдите по связанному списку.

    • Если найден тот же ключ, обновите его значение (или обработайте его по мере необходимости).
    • Если тот же ключ не найден, добавьте новую пару ключ-значение в конец связанного списка.

    Пример

    class HashTableChaining:
        """Реализация хеш-таблицы с использованием цепочек для разрешения коллизий."""

        def __init__(self, size=10):
            """Инициализирует хеш-таблицу.
    :param size: начальный размер базового массива
            """

            self.size = size
            # Создать список размера `size`, в котором каждый элемент инициализирован пустым списком (представляющим связанный список)
            self.table = [[] for _ in range(size)]

        def _hash(self, key):
            """Внутренняя хеш-функция. Здесь мы используем встроенную функцию hash в Python и берём остаток по модулю."""
            return hash(key) % self.size

        def insert(self, key, value):
            """Вставить пару ключ-значение в хеш-таблицу."""
            index = self._hash(key)
            bucket = self.table[index] # Получить 'bucket' (связный список), соответствующий этому индексу

            # Пройти по корзине и проверить, существует ли уже ключ
            for i, (k, v) in enumerate(bucket):
                if k == key:
                    # Ключ уже существует, обновить значение
                    bucket[i] = (key, value)
                    return
            # Ключ отсутствует, добавить его в конец связного списка
            bucket.append((key, value))

        def get(self, key):
            """Получить значение по ключу. Если ключ отсутствует, вернуть None."""
            index = self._hash(key)
            bucket = self.table[index]

            for k, v in bucket:
                if k == key:
                    return v
            return None # Ключ отсутствует

        def delete(self, key):
            """Удалить пару ключ-значение по ключу."""
            index = self._hash(key)
            bucket = self.table[index]

            for i, (k, v) in enumerate(bucket):
                if k == key:
                    del bucket[i] # Удалить этот узел из связного списка
                    return True # Удаление выполнено успешно
            return False # Ключ отсутствует, удаление не удалось

        def display(self):
            """Вывести всё содержимое хеш-таблицы."""
            for i, bucket in enumerate(self.table):
                print(fИндекс {i}: {bucket})

    # Пример использования
    print("\n--- Пример хеш-таблицы с цепочками ---)
    phone_book = HashTableChaining(5)
    phone_book.insert("Alice", "123-4567")
    phone_book.insert("Bob", "987-6543")
    phone_book.insert("Charlie", "555-1234")
    # Предположим, что хеш-значение "David" вызывает коллизию с "Alice" (для демонстрации)
    phone_book.insert("David", "111-2222")

    print("Хеш-таблица после вставки данных:")
    phone_book.display()

    print(f"\nНайти телефон 'Bob': {phone_book.get('Bob')}")
    print(f"Поиск несуществующего 'Eve': {phone_book.get('Eve')}")

    phone_book.delete("Charlie")
    print("\nХеш-таблица после удаления 'Charlie':")
    phone_book.display()

    Результат вывода:

    --- 链地址法哈希表示例 ---
    插入数据后的哈希表:
    索引 0: [('David', '111-2222')]
    索引 1: []
    索引 2: [('Alice', '123-4567')]
    索引 3: [('Charlie', '555-1234')]
    索引 4: [('Bob', '987-6543')]
    
    查找 'Bob' 的电话: 987-6543
    查找不存在的 'Eve': None
    
    删除 'Charlie' 后的哈希表:
    索引 0: [('David', '111-2222')]
    索引 1: []
    索引 2: [('Alice', '123-4567')]
    索引 3: []
    索引 4: [('Bob', '987-6543')]
    

    Примечание: Чтобы наглядно продемонстрировать коллизии, в примере размер массива установлен равным 5, и мы используемhash(key), фактические конфликты могут быть неочевидны. Вsimple_hashПод функцией,"Alice"и"David"ключи, которые могут давать один и тот же индекс, тем самым показывая, как метод цепочек хранит несколько записей под одним индексом.

    Метод 2: метод открытой адресации

    Этот метод сохраняет все элементы непосредственно в самом массиве. При возникновении коллизии он ищет следующую свободную позицию в массиве в соответствии с последовательностью проб.

    Распространённые методы проб:

    • Линейное пробирование: Если позицияiзанята, то попробуйтеi+1, i+2, i+3... пока не будет найдена пустая ячейка.
    • Квадратичное пробирование: Если позицияiзанята, то попробуйтеi+1^2, i+2^2, i+3^2...。
    • Двойное хеширование: Используйте вторую хеш-функцию для вычисления размера шага пробирования.

    Здесь мы реализуем простое линейное пробирование:

    Пример

    class HashTableLinearProbing:
        """Реализация хеш-таблицы с использованием линейного пробирования (открытая адресация) для разрешения коллизий."""

        def __init__(self, size=10):
            self.size = size
            # Используйте специальный маркер `None` для обозначения пустых ячеек и маркер (например, `'DELETED'`) для обозначения удалённых позиций.
            # Для простоты для пустых ячеек используется только `None`; поиск останавливается, когда встречает `None`.
            self.keys = [None] * size
            self.values = [None] * size

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

        def insert(self, key, value):
            index = self._hash(key)
            original_index = index

            # Использовать линейное пробирование для поиска пустого слота или того же ключа
            while self.keys[index] is not Отсутствует:
                if self.keys[index] == key:
                    # Ключ уже существует, обновить значение
                    self.values[index] = value
                    return
                index = (index + 1) % self.size # Перейти к следующей позиции (циклический массив)
                if index == original_index:
                    # Прошли полный круг; таблица заполнена (на практике следует изменить размер)
                    raise Exception("Хеш-таблица заполнена")

            # Найден пустой слот, вставляем
            self.keys[index] = key
            self.values[index] = value

        def get(self, key):
            index = self._hash(key)
            original_index = index

            while self.keys[index] is not Отсутствует:
                if self.keys[index] == key:
                    return self.values[index]
                index = (index + 1) % self.size
                if index == original_index:
                    break # Прошли полный круг, так и не найдя его
            return None

        def display(self):
            for i in range(self.size):
                if self.keys[i] is not Отсутствует:
                    print(f"Индекс {i}: ключ={self.keys[i]}, значение={self.values[i]}")
                else:
                    print(fИндекс {i}: пусто)

    # Пример использования
    print("\n--- Пример хеш-таблицы с линейным пробированием ---)
    ht_linear = HashTableLinearProbing(7) # Маленький размер делает пробирование наглядным
    ht_linear.insert("Яблоко", 10)
    ht_linear.insert("Банан", 20)
    ht_linear.insert("Вишня", 30)
    # Предположим, 'Финик' и 'Яблоко' вызывают коллизию
    ht_linear.insert("Date", 40)

    print("Хеш-таблица после вставки данных:")
    ht_linear.display()

    print(f"\nПоиск 'Banana': {ht_linear.get('Banana')})
    print(fПоиск 'Date' (вставлено после коллизии): {ht_linear.get('Date')})

    Результат вывода:

    --- 线性探测哈希表示例 ---
    插入数据后的哈希表:
    索引 0: 键=Apple, 值=10
    索引 1: 键=Date, 值=40
    索引 2: 键=Banana, 值=20
    索引 3: 键=Cherry, 值=30
    索引 4: 空
    索引 5: 空
    索引 6: 空
    
    查找 'Banana': 20
    查找 'Date' (冲突后插入的): 40
    

    Примечание: При открытой адресации удаление сложно: нельзя просто установить позицию вNoneпустое значение (null); иначе это нарушит последовательность зондирования. Обычно используется специальный маркер "deleted". Для простоты в этом примере удаление не реализовано.

    Сравнение двух методов

    Особенности Метод цепочек Открытая адресация
    Сложность реализации Относительно просто Относительно сложно, особенно операции удаления
    Накладные расходы памяти Требуется дополнительное пространство для хранения указателей (связный список) Все данные находятся в массиве, поэтому использование пространства может быть выше
    Влияние коллизий Коллизии влияют только на производительность одной и той же корзины (связного списка) Коллизии влияют на позиции последующих вставок и могут приводить к "кластеризации"
    Момент изменения размера Расширять, когда средняя длина связного списка превышает порог Расширять, когда коэффициент загрузки (число элементов / размер массива) превышает порог
    Применимые сценарии Общий, более распространённый Дружественный к кэшу, подходит для сценариев с известным максимальным объёмом данных или ограниченной памятью

    Производительность хеш-таблиц и коэффициент загрузки

    Эффективность хеш-таблицы во многом зависит от ключевой метрики:Коэффициент загрузки。

    Коэффициент загрузки = количество элементов, хранящихся в хеш-таблице / общий размер массива хеш-таблицы

    • Низкий коэффициент загрузки(например, 0.5): означает, что в массиве ещё много пустых слотов, вероятность коллизий низкая, а операции выполняются быстро.
    • Высокий коэффициент загрузки(например, 0.9): означает, что массив почти заполнен, вероятность коллизий резко возрастает, связанные списки становятся длиннее или расстояния при пробировании увеличиваются, а производительность снижается.

    Чтобы поддерживать высокую производительность, когда коэффициент загрузки превышает определённый порог (например, 0.75), хеш-таблица расширяется:ResizeОперации:

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

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


    Практическое упражнение: создайте счётчик слов

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

    Мы будем использовать следующий текст в качестве тестовых данных (вы можете скопировать его в свой код):

    the quick brown fox jumps over the lazy dog the dog is not lazy at all
    

    Пример

    # Упражнение: используйте нашу реализацию HashTableChaining для подсчёта частот слов
    print("\n=== Практическое упражнение: Счётчик слов ===)

    # 1. Создайте экземпляр хеш-таблицы
    word_counter = HashTableChaining(size=10)

    # 2. Предоставленный тестовый текст
    text = "быстрая коричневая лиса прыгает через ленивую собаку собака не ленивая вообще"
    words = text.split() # Разделить текст на список слов

    print(Обработанный список слов:, words)

    # 3. Перебрать слова и вставить в хеш-таблицу
    for word in words:
        current_count = word_counter.get(word)
        if current_count is None:
            # Первое вхождение слова, количество равно 1
            word_counter.insert(word, 1)
        else:
            # Слово уже существует, увеличить количество на 1
            word_counter.insert(word, current_count + 1)

    # 4. Вывод статистических результатов
    print("\nСтатистика вхождений слов:)
    # Примечание: наш метод отображения выводит по индексу; здесь мы пишем более удобный для пользователя вывод
    all_entries = []
    for bucket in word_counter.table:
        all_entries.extend(bucket) # Объединить записи во всех корзинах

    for word, count in all_entries:
        print(f'{word}': {count} раз)

    # 5. Проверка конкретного слова
    test_word = "the"
    print(f"\nПроверка: слово '{test_word}' встречалось {word_counter.get(test_word)} раз.)
    test_word = "lazy"
    print(fПроверка: слово '{test_word}' встречалось {word_counter.get(test_word)} раз.)

    Результат вывода:

    === 实践练习:单词计数器 ===
    处理的单词列表: ['the', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog', 'the', 'dog', 'is', 'not', 'lazy', 'at', 'all']
    
    单词出现次数统计:
      'the': 3 次
      'quick': 1 次
      'brown': 1 次
      'fox': 1 次
      'jumps': 1 次
      'over': 1 次
      'lazy': 2 次
      'dog': 2 次
      'is': 1 次
      'not': 1 次
      'at': 1 次
      'all': 1 次
    
    验证:单词 'the' 出现了 3 次。
    验证:单词 'lazy' 出现了 2 次。
    

    Поздравляем! Вы успешно использовали свою собственную реализацию хеш-таблицы, чтобы выполнить практическую задачу. В реальном программировании вам редко приходится реализовывать хеш-таблицу самостоятельно, потому что современные языки программирования (такие как в PythondictJavaHashMapC++'sunordered_map) все предоставляют высокооптимизированные, мощные встроенные реализации хеш-таблиц. Понимание их принципов поможет вам использовать их более разумно и эффективно.


    Резюме и обзор ключевых моментов

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

    Основной механизм: Хеш-функцияПреобразует ключ в индекс массива.

    Ключевые проблемы: Хеш-коллизия— разные ключи отображаются на один и тот же индекс.

    Решение:

    • Метод цепочек: каждая позиция индекса хранит связанный список для хранения конфликтующих пар ключ-значение.
    • Открытая адресация: поиск следующей пустой ячейки в массиве в соответствии с последовательностью проб.

    Критично для производительности: Коэффициент заполнения. Когда коэффициент заполнения слишком высок, необходимоизменить размери выполнитьперехешированиечтобы восстановить производительность.

    Практические применения: хеш-таблицы — краеугольный камень программирования, широко используемый в бесчисленных сценариях, таких как индексирование баз данных, системы кэширования, проверка принадлежности к множеству, хранение свойств объектов и многие другие.

    Другие расширения