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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

Крис

Ответ 3

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

f(abc) = 6

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

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

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

Hashmaps похожи на hashtables, но в нем хранится только один пример каждого объекта (поэтому ключ не должен предоставляться, сам объект является ключом).

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

Ответ 4

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