Как работают хеш -карты
7 августа 2025 г.Аdictв Python.mapв Go,ObjectилиMapв JavaScript. Ассоциативные массивы в PHP,Dictionary<TKey, TValue>в C ++. Хеш-карты реализованы практически на каждом языке программирования высокого уровня. И они потрясающие! Кто не хочет хранить, а затем получать доступ к данным в постоянное время? Независимо от того, работаете ли вы с большими наборами данных или измельчающими проблемами LeetCode, очень часто эта структура данных приходит на помощь. Но что они точно, и как они работают под капюшоном? В этой статье мы постараемся ответить на эти вопросы.
Что такое хэш -карта?
На высоком уровне хэш -карта или хэш -таблица представляет собой структуру данных, которая реализует ассоциативный тип данных, структуру, которая может отображать ключи от значений. Ключ используется для однозначного идентификации значения на карте, а значение - это данные, которые хранятся. Хеш-карты предназначены для обеспечения быстрого вставки, удаления и поиска пар ключей.
Фактически, средняя сложности времени для этих операций - O (1), что означает, что они могут быть выполнены в постоянное время! Эта функция делает хэш -карты, вероятно, наиболее используемая структура данных в программировании, однако в этом есть некоторые предостережения, как мы увидим позже.
Сложность в худшем случае для этих операций-O (n), что может произойти в определенных сценариях, и чем больше мы знаем о внутренних органах, тем больше вероятность того, что мы должны избежать этих сценариев.
СогласноВикипедия статья:
Хэш -таблица - это структура данных, которая реализует ассоциативный массив, также называемый словарем или просто карту; Ассоциативный массив - это абстрактный тип данных, который отображает ключи от значений. Хэш -таблица использует хэш -функцию для вычисления индекса, также называемого хэш -кодом, в массив ведра или слотов, из которого можно найти желаемое значение.
Итак, давайте сделаем шаг назад и посмотрим на компоненты хэш -карты.
Что такое хэш -функция?
Хэш -функция - это функция, которая принимает вход (или «ключ») и обычно возвращает целое число, которое используется для индексации данных на карте хэш. Ключ преобразуется в целое число, которое затем используется для определения индекса в базовом массиве, где хранится значение.
Хорошая хэш -функция имеет следующие свойства:
- Детерминированный: Тот же вход всегда будет производить один и тот же выход.
- Равномерное распределение: Функция хеш должна равномерно распределять ключи по хеш -таблице, чтобы минимизировать столкновения.
- Быстрое вычисление: Функция хеш должна быть быстро вычислять, даже для больших входов.
- Минимизировать столкновения: Пространство возможных клавиш, как правило, намного больше (часто бесконечно), чем пространство хэш -кодов. Это означает, что разные клавиши могут создавать один и тот же хэш -код. Хотя эти столкновения неизбежны, хорошая хэш -функция сводит к минимуму шансы на два разных ключа, производящих один и тот же хэш -код.
Простым примером хэш -функции является операция модуля, которая берет ключ и возвращает остаток при разделении на размер хэш -таблицы. Например, если у нас есть хэш -таблица размера 10 и ключ из 23, хэш -код будет23 % 10 = 3, то есть значение, связанное с ключом 23, будет сохранено в индексе 3 в базовом массиве. И если ключ составляет 33 года, хэш -код будет33 % 10 = 3Кроме того, это означает, что у нас столкновение. В этом случае оба ключа будут отображать с одним и тем же индексом в массиве.
Что такое ведро?
Ведро-это слот в хэш-столе, где хранится пара ключей. В случае столкновения, когда два разных клавиша производят один и тот же хэш-код, ведро может хранить несколько пар клавишных значений. Это часто делается с использованием связанного списка или другой структуры данных для обработки столкновений.
Эта диаграмма иллюстрирует, как все это работает:
Здесь мы видим, как хэш -функция отображает ключи от индексов в базовом массиве. Ключи 23 и 33 производят один и тот же хэш -код 3, что означает, что они хранятся в одном и том же ведре. Ведро может затем хранить обе пары ключевых значений, но когда мы получаем значение, нам нужно проверить клавиши в ведре, чтобы найти правильный. Именно здесь сложность времени может увеличиться до O (n) в худшем случае, если многие (или даже все) ключи сталкиваются и хранятся в одном ведре.
Коэффициент нагрузки
Коэффициент нагрузки является мерой того, насколько полна хэш -таблица. Он рассчитывается как количество элементов в хэш -таблице, деленных на количество ведер (или слотов) в базовом массиве. Более высокий коэффициент нагрузки означает, что в хэш -таблице больше элементов относительно количества ведер, что может привести к большему количеству столкновений и более медленной производительности.
Разрешение столкновения
Когда два ключа производят один и тот же хэш -код, у нас столкнутся столкновение. Есть несколько стратегий для обработки столкновений на хэш -картах:
- Цепочка: В этом методе каждое ведро содержит связанный список (или другую структуру данных) всех пар клавиш, которые хешируют с одним и тем же индексом. Когда происходит столкновение, новая пара клавишных значений просто добавляется в список в соответствующем ведре. Это самый распространенный метод для обработки столкновений.
Сложность: Средний O (1) для всех операций, в худшем случае O (n), если все ключи хеша к одному и тому же ведро
Плюс: Простой в реализации, хорошо обрабатывает коэффициенты высокой нагрузки, удаление является простым
Минусы: Дополнительные накладные расходы на память для указателей, плохая производительность кэша из -за рассеянного доступа к памяти
- Открытая адресация: В этом методе, когда происходит столкновение, хэш-таблица ищет следующий доступный слот в массиве для хранения новой пары ключевых значений. Есть несколько методов поиска следующего доступного слота:
Линейное зондирование: Если происходит столкновение, алгоритм проверяет следующий слот в массиве, пока не найдет пустой.
- Сложность: Средний O (1), худший случай O (n) из-за первичной кластеризации
- Плюс: Простая реализация, хорошая производительность кеша для близлежащих доступа
- Минусы: Первичная кластеризация (последовательная занятых слотов), производительность ухудшается с кластеризацией
Квадратичное зондирование: Вместо того, чтобы проверять следующий слот, он проверяет слоты на увеличивающихся расстояниях (1, 4, 9 и т. Д.) Из исходного индекса.
- Сложность: Средний O (1), лучше, чем линейное зондирование из -за снижения кластеризации
- Плюс: Уменьшает первичную кластеризацию по сравнению с линейным зондированием, все еще благоприятным для кеша
- Минусы: Вторичная кластеризация (клавиши с одинаковой хэшем следуйте за той же последовательности зондов), может не посещать все слоты
Двойной хешинг: Использует вторую хэш -функцию для определения размера шага для зондирования. В отличие от линейного зондирования, которое всегда перемещается к следующему слоту, или квадратичному зондированию, которое использует фиксированную последовательность, двойное хэширование вычисляет уникальный размер шага для каждого ключа. Формула обычно:index = (hash1(key) + i * hash2(key)) % table_size, гдеiэто номер попытки зонда. Вторая хэш -функция должна вернуть значение, которое относительно основное для размера таблицы, чтобы гарантировать, что все слоты можно посетить. Например, еслиhash1(key) = 7иhash2(key) = 3, тогда мы исследуем индексы 7, 10, 13, 16 и т. Д.
Сложность: Средний O (1), лучшая производительность среди методов открытой адресации
Плюс: Минимизирует кластеризацию, равномерное распределение последовательностей зондов, посещает все слоты при правильном реализации
Минусы: Более сложная реализация, требует вычисления двух хэш -функций и немного больше накладных расходов на операцию
Перефразируя: Если коэффициент нагрузки становится слишком высоким, хэш-таблица может быть изменен, и все существующие пары ключевых значений могут быть перефразированы в новую таблицу. Это помогает поддерживать эффективную производительность по мере роста количества элементов.
- Сложность: O (n) для самой операции перефразировки, но амортизируется до (1) за вставку с течением времени
- Плюс: Поддерживает оптимальную производительность, сохраняя низкую коэффициент нагрузки, предотвращает снижение производительности
- Минусы: Временный всплеск производительности во время перефразирования, требует дополнительной памяти во время операции изменения размера
Каждый из этих методов имеет свои собственные компромиссы с точки зрения сложности, производительности и использования памяти. Выбор стратегии разрешения столкновений может оказать существенное влияние на общую производительность хеш -карты.
Вот краткое изложение плюсов и минусов каждого метода разрешения столкновения:
Особенность | Цепочка | Линейное зондирование | Квадратичное зондирование | Двойной хешинг |
|---|---|---|---|---|
Средняя сложность времени | O (1) | O (1) | O (1) | O (1) |
Сложность худшего времени | На) | На) | На) | На) |
Память над головой | Высокий (указатели) | Низкий | Низкий | Низкий |
Кэш производительность | Бедный | Хороший | Хороший | Умеренный |
Сложность реализации | Простой | Простой | Умеренный | Сложный |
Проблемы кластеризации | Никто | Первичная кластеризация | Вторичная кластеризация | Минимальный |
Допуск коэффициента нагрузки | Высокий (> 1,0) | Низкий (<0,7) | Низкий средний (<0,7) | Средний (<0,8) |
Сложность удаления | Простой | Комплекс (надгробия) | Комплекс (надгробия) | Комплекс (надгробия) |
Космическая эффективность | Ниже | Выше | Выше | Выше |
Деградация производительности | Постепенно | Быстро при высокой нагрузке | Умеренный при высокой нагрузке | Медленно при высокой нагрузке |
Требования к функции хэш | Один | Один | Один | Два |
Лучшие варианты использования | Неизвестные коэффициенты нагрузки, частые удаления | Приложения для кэша, низкая нагрузка | Лучше, чем линейная, умеренная нагрузка | Высокая производительность, предсказуемая нагрузка |
Некоторые реальные примеры
Реализации языка программирования
Многие языки программирования имеют встроенные хэш-карты. Эти реализации часто используют комбинацию методов, описанных выше, для эффективной эффективности и обработки столкновений.
- ПитонS.
dictИспользует открытую адресацию с рандомизированным зондированием, перефразируя, когда коэффициент нагрузки превышает около 0,66. - ЯваS.
HashMapИспользует цепочку со связанными списками (преобразование в сбалансированные деревья для больших ведер в Java 8+), перефразируется при 0,75 коэффициенте нагрузки. - C ++S.
unordered_mapОбычно использует цепочку, но реализации могут варьироваться.
Системы баз данных
Хеш -карты также широко используются в индексации базы данных. Многие системы баз данных используют хэш -индексы для ускорения поиска данных. Эти индексы допускают быстрый поиск путем хранения индексированных столбцов и сохраняя полученные пары ключей в хэш-таблице. Когда запрос выполняется, база данных может быстро найти соответствующие строки, вычислив хэш ключа запроса и просмотрев его в хэш -индексе.
Некоторые популярные системы баз данных, которые используют хэш -индексацию, включают:
- Postgresql: Поддерживает хэш-индексы, но они не так часто используются, как индексы B-Tree.
- Mongodb: Использует хэш -индексы для шардинга и для поддержки запросов равенства на хешированных полях.
- Редис: Реализует хеш-карты как основную структуру данных, позволяющая эффективно хранение и поиск пар ключевых значений.
Эти реализации часто используют те же основные принципы хеширования и разрешения столкновений, обсуждаемых ранее, но они также могут включать дополнительные оптимизации, специфичные для контекста базы данных.
Управление версией
Системы управления версиями, такие как GIT, используют хеш -карты для эффективного управления изменениями файлов и отслеживания версий. Каждый коммит в GIT определяется хэшем SHA-1 его содержания, который служит уникальным ключом для объекта Commit. Это позволяет GIT быстро искать коммиты, филиалы и другие объекты в репозитории. GIT не использует традиционное разрешение на столкновение с хеш -таблицей, оно разработано вокруг предположения, что криптографические хэш -столкновения не будут происходить на практике.
Собрать все это вместе: как важно знания о реализации
И это не только теория! Понимание того, как реализуются хеш -карты на вашем языке программирования по выбору, может привести к значительному улучшению производительности в вашем коде.
Например, начиная с PythondictИспользует открытую адресацию с оптимизированной обработкой строк, понимание этого может привести к гораздо лучшей производительности. Вот как написать эффективный и неэффективный код:
Плохая реализация (борьба с диктом Python)
def count_words_bad(text):
word_counts = {}
words = text.split()
for word in words:
# This is inefficient with open addressing!
if word in word_counts: # First lookup
word_counts[word] += 1 # Second lookup + assignment
else:
word_counts[word] = 1 # Third lookup + assignment
return word_counts
Введите полноэкранную режим выхода из полноэкранного режима
Проблемы:
- Многочисленные хэш -поиски на слово (до 3!)
- Открытая адресация делает пропускные чеки дорогими
- Не использует оптимизации DICT Python
Хорошая реализация (работает с DICT Python)
from collections import defaultdict, Counter
def count_words_good_v1(text):
# defaultdict eliminates key existence checks
word_counts = defaultdict(int)
words = text.split()
for word in words:
word_counts[word] += 1 # Single operation!
return dict(word_counts)
def count_words_good_v2(text):
# Counter is optimized specifically for Python's dict implementation
words = text.split()
return Counter(words)
def count_words_good_v3(text):
# dict.get() with default avoids the membership test
word_counts = {}
words = text.split()
for word in words:
word_counts[word] = word_counts.get(word, 0) + 1 # Single lookup
return word_counts
Введите полноэкранную режим выхода из полноэкранного режима
Почему они лучше:
- Одиночная хэш -операцияза слово вместо нескольких
- Использует оптимизацию струн Python- Клавики струны обрабатываются очень эффективно
- Работает с открытой адресацией- Меньше необходимого зондирования
- Использует встроенные оптимизациинравиться
Counterкоторый настроен на реализацию Python
Разница в производительности
Типичные результаты:Хорошая реализация часто в 2-3 раза быстрее, просто понимая и работая с реализацией DICT Python, а не против этого!
Заключение
Хэш-карты являются одними из самых фундаментальных и мощных структур данных в информатике, обеспечивая почти постоянный доступ к данным, которые делают их незаменимыми в современном программировании. На протяжении всего этого глубокого погружения мы исследовали, как они достигают своей замечательной средней производительности O (1) за счет умного использования хэш -функций, разрешения стратегического столкновения и тщательного управления коэффициентами нагрузки.
Ключевым пониманием является то, что «магия» хэш-карт совсем не волшебство-это результат хорошо разработанных алгоритмов и структур данных, работающих вместе. Понимание этих внутренних органов помогает нам избежать наихудших сценариев O (n) и писать более эффективный код.
Ключевые выводы:
- Хэш -функцииЯвляются ли фундамент - они определяют, как равномерно распределяются данные и напрямую влияют на ставки столкновений
- Стратегии разрешения столкновенийУ каждого есть отдельные компромиссы: цепочка для простоты и надежности, открытая адресация для эффективности памяти и производительности кэша
- Управление коэффициентом нагрузкиЧерез перефразирование предотвращает снижение производительности по мере роста карт хэш -карт
- Знание реализациипереводится на реальную прибыль производительности-понимание того, использует ли ваш язык цепочку или открытую адресацию, может сделать ваш код 2-3 раза быстрее
Независимо от того, оптимизируете ли вы сценарий Python, отладку проблем с производительностью в Java или принимаете архитектурные решения для системы базы данных, это понимание внутренних групп HashMap дает вам инструменты для принятия обоснованных вариантов. В следующий раз, когда вы используетеdictВHashMap, илиunordered_mapВы точно знаете, что происходит под капотом и как максимально использовать эти невероятные структуры данных.
Хэш -карты действительно потрясающие - и теперь вы знаете, почему!
Оригинал