Что такое хэш-карта в программировании и где ее можно использовать

Question

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

Answer 1

Сначала вы должны прочитать эту статью .

Когда вы используете списки и ищете специальный элемент, вам обычно приходится перебирать весь список.Это очень дорого, если у вас большие списки.
Хеш-таблица может быть намного быстрее, при лучших обстоятельствах вы получите искомый элемент только с одним доступом.
Как это работает?Как словарь ... когда вы ищете слово "хеш-таблица" в словаре, вы не начинаете с первого слова под "а".Но скорее вы идете прямо к букве «ч».Затем к «ха», «имеет» и так далее, пока вы не нашли свое слово.Вы используете индекс в своем словаре для ускорения поиска.
Хеш-таблица в основном делает то же самое.Каждый элемент получает уникальный индекс (так называемый hash).Вы используете этот хэш для поиска.Хеш может быть индексом в обычном связанном списке.Например, ваш хэш может быть числом, подобным 2130, что означает, что вы должны посмотреть на позицию 2130 в вашем списке.Поиск известного индекса в обычном списке очень прост и быстр.
Проблема всего подхода заключается в так называемом hash function, который присваивает этот индекс каждому элементу.Когда вы ищете предмет, вы должны заранее рассчитать индекс.Как в реальном словаре, где вы видите, что слово «хеш-таблица» начинается с буквы «h», и, следовательно, вы знаете приблизительную позицию.
Хорошая хеш-функция предоставляет хеш-коды, которые равномерно распределены по пространству всех возможныхhashcodes.И, конечно, он пытается избежать collisions.Столкновение происходит, когда два разных элемента получают один и тот же хэш-код.
Например, в C # каждый объект имеет метод GetHashcode(), который предоставляет для него хэш (не обязательно уникальный).Это можно использовать для поиска и сортировки в вашем словаре.

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

Answer 2

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

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

Вы можете найти это полезным: http://www.relisoft.com/book/lang/pointer/8hash.html

Надеюсь, это поможет,

Chris

Answer 3

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

f(abc) = 6

Обратите внимание, что эта тривиальная схема хеширования создаст коллизию между строками abc, bca, ae и т. Д. Эффективная схема хеширования, естественно, выдаст разные значения для каждой строки.

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

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

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

Это, конечно, очень простое объяснение, поэтому я предлагаю вам прочитать подробно с этого момента. Надеюсь, я не допустил глупых ошибок. =)

Answer 4

Hashmap используется для хранения данных в парах ключ-значение.Мы можем использовать хэш-карту для хранения объектов в приложении и использовать его в том же приложении для хранения, обновления, удаления значений.Ключ и значения Hashmap хранятся в корзине для конкретной записи, это местоположение записи определяется с помощью функции Hashcode.Эта функция хеширования определяет хеш, где хранится значение.Подробное объяснение того, как работает hashmap, описано в этом видео: https://youtu.be/iqYC1odZSNo