Что такое хеш-таблицы и хэш-карты и их типичные варианты использования?

Question

Недавно я несколько раз сталкивался с этими терминами, но совершенно не понимаю, как они работают и когда они обычно применяются?

Answer 1

Ну, подумайте об этом так.

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

Если вы хотите получить более быстрый доступ к данным, вы обычно прибегаете к сортировке массива и использованию двоичного поиска.Однако это, хотя и увеличивает скорость поиска существующего значения, замедляет вставку новых значений, поскольку вам нужно перемещать существующие элементы, когда вам нужно вставить элемент в середину.

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

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

Каждый элемент имеет два свойства: данные и ключ, идентифицирующий данные.Например, список почтовых индексов США будет иметь тип ассоциации «почтовый индекс -> имя».Функция уменьшает ключ, но не учитывает данные.

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

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

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

Типичная хеш-таблица не имеет бесконечного числа элементов, доступных для хранения, поэтому это число обычно сокращается до индекса, соответствующего размеру массива.Один из способов сделать это — просто сравнить модуль индекса с размером массива.Для массива размером 10 индекс 0–9 будет напрямую отображаться в индекс, а индекс 10–19 снова будет отображаться в 0–9 и так далее.

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

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

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

Функция, сводящая ключ к числу, не выдает линейное значение, т.е.«AAA» становится 1, затем «AAB» становится 2, поэтому хеш-таблица не сортируется по какому-либо типичному значению.

На эту тему также есть хорошая статья в Википедии: здесь.

Answer 2

Ответ Лассевка очень хорош, но может содержать слишком много деталей.Вот исполнительное резюме.Я намеренно опуская некоторые важные информацию, которую вы можете спокойно игнорировать в 99% случаев.

Есть нет существенной разницы между хеш-таблицами и хэш-картами в 99% случаев.

Хэш-таблицы — это волшебство

Серьезно.Это волшебная структура данных, которая почти гарантирует три вещи.(Есть исключения.Вы можете их игнорировать, хотя изучение их когда-нибудь может оказаться для вас полезным.)

1) Все в хеш-таблице является частью пары — есть ключ и ценить.Вы вводите и извлекаете данные, указав ключ, с которым работаете.

2) Если вы делаете что-либо с помощью одного ключа в хеш-таблице, это невероятно быстро.Это означает, что put(key,value), get(key), contains(key), и remove(key) все очень быстро.

3) Общие хэш-таблицы не получается сделать что-либо, не перечисленное в пункте 2!(Под «провалом» мы подразумеваем, что они невероятно медленны.)

Когда мы используем хеш-таблицы?

Используем хеш-таблицы когда их магия соответствует нашей проблеме.

Например, кэширование часто в конечном итоге используется хеш-таблица — например, предположим, что у нас в университете 45 000 студентов, и какой-то процесс должен хранить записи для всех них.Если вы регулярно обращаетесь к студенту по идентификационному номеру, то ID => student кэш имеет отличный смысл.Операция, которую вы оптимизируете для этого кеша, быстрый поиск.

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

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

Когда не следует использовать хеш-таблицы

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

Сортировка. Если вы не можете выполнять итерации, сортировка тоже станет настоящей болью.

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

Answer 3

если вы говорите с точки зрения Java, обе коллекции являются коллекциями, которые позволяют добавлять, удалять и обновлять объекты и использовать алгоритмы Хасинга внутри.

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

Помимо синхронизации, в обоих случаях внутренним механизмом хранения и извлечения объектов является хеширование.

Если вам нужно увидеть, как работает хеширование, я бы порекомендовал немного погуглить о структураторах данных и методах хеширования.

Answer 4

Хэш-таблицы/хэш-карты связывают значение (называемое «ключом» в целях устранения неоднозначности) с другим значением.Вы можете рассматривать их как своего рода словарь (слово:определение) или запись базы данных (ключ:данные).