Алгоритмы. Структуры данных. Хеш-таблицы

Хеш-таблица представляет собой структуру данных, которая реализует ассоциативный массив, обеспечивая возможность хранения пар «ключ–значение». Её принцип работы можно сравнить с организацией библиотеки, где каждая книга имеет уникальный инвентарный номер. Если книги просто сложены в беспорядке, поиск нужной займет много времени. Однако если они расставлены на полках в соответствии со своими номерами, нужный экземпляр находится практически мгновенно. Именно такую «умную» систему и воплощает хеш-таблица — это своего рода шкаф с ячейками, где каждый элемент данных хранится в ячейке, определяемой своим ключом.

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

Работа хеш-таблицы происходит по следующему алгоритму. Допустим, имеется массив из десяти ячеек с индексами от 0 до 9. Когда требуется сохранить пару, например, "apple" : 5, хеш-функция обрабатывает ключ "apple" и возвращает число в диапазоне от 0 до 9. Предположим, результатом вычисления становится индекс 3. Тогда значение 5 будет помещено в ячейку с этим индексом. Визуально процесс можно представить так: изначально массив пуст, после операции hash("apple") → 3 в ячейке с индексом 3 оказывается значение, ассоциированное с ключом "apple".

# Пример создания и использования хеш-таблицы (словаря) в Python для хранения цен на фрукты
prices = {}

# Добавление элементов
prices["apple"] = 50      # hash("apple") → условно, ячейка 3
prices["banana"] = 30     # hash("banana") → условно, ячейка 7
prices["orange"] = 40     # hash("orange") → условно, ячейка 1

print(prices)
# Вывод: {'apple': 50, 'banana': 30, 'orange': 40}

Внутренне это может соответствовать следующей структуре, где некоторые ячейки остаются пустыми:

Индекс:  [0]    [1]         [2]  [3]        [4]  [5]  [6]  [7]          [8]  [9]
         пусто  orange→40  пусто apple→50  пусто пусто пусто banana→30  пусто пусто

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

Пример 1

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

# Подсчет количества слов в тексте
text = "apple banana apple orange apple banana apple"
words = text.split()

word_count = {}

for word in words:
    if word in word_count:
        word_count[word] += 1  # Увеличиваем счетчик
    else:
        word_count[word] = 1   # Первая встреча слова

print(word_count)
# Вывод: {'apple': 4, 'banana': 2, 'orange': 1}

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

Пример 2

Одной из фундаментальных проблем в работе хеш-таблиц являются коллизии — ситуации, когда разные ключи в результате работы хеш-функции получают один и тот же индекс ячейки. Это аналогично тому, как двум разным людям выдали ключи от одной и той же квартиры. Например, может оказаться, что hash("apple") → 3 и hash("grape") → 3. Для разрешения коллизий существует несколько методов, наиболее распространёнными из которых являются метод цепочек и метод открытой адресации.