Метод цепочек предполагает, что каждая ячейка массива содержит не одно значение, а связный список (или динамический массив) пар «ключ–значение». При возникновении коллизии новая пара просто добавляется в список соответствующей ячейки. Таким образом, ячейка с индексом 3 будет содержать список вида [("apple", 50), ("grape", 60)]. Поиск значения по ключу в таком случае требует вычисления индекса и последующего линейного поиска по цепочке, чтобы найти нужную пару.

Пример 3

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

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

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

Пример 4

В языке Python хеш-таблицы реализованы в виде встроенного типа данных dict, который предоставляет богатый интерфейс для работы.

student_scores = {
    "Анна": 95,
    "Борис": 87,
    "Вера": 92
}

# Получение значения с указанием значения по умолчанию
print(student_scores.get("Анна", 0))      # 95
print(student_scores.get("Георгий", 0))   # 0 (ключа нет)

# Получение всех ключей и значений
print(student_scores.keys())    # dict_keys(['Анна', 'Борис', 'Вера'])
print(student_scores.values())  # dict_values([95, 87, 92])

# Перебор пар ключ-значение
for name, score in student_scores.items():
    print(f"{name}: {score} баллов")

# Обновление словаря
new_scores = {"Георгий": 88, "Анна": 98}
student_scores.update(new_scores)
print(student_scores)
# Вывод: {'Анна': 98, 'Борис': 87, 'Вера': 92, 'Георгий': 88}

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

# Пример плохой хеш-функции, зависящей только от длины строки
def bad_hash(key, size):
    return len(str(key)) % size

bad_hash("cat", 10)   # → 3
bad_hash("dog", 10)   # → 3 (коллизия!)
bad_hash("rat", 10)   # → 3 (коллизия!)

# Пример более качественной хеш-функции
def good_hash(key, size):
    return sum(ord(c) for c in str(key)) % size

good_hash("cat", 10)  # → 4
good_hash("dog", 10)  # → 4 (возможна коллизия, но реже)
good_hash("rat", 10)  # → 7 (разные индексы!)