Что является картой хеша в программировании и где может это использоваться
Я часто слышал, что люди говорят о хешировании, и хеширую карты и хеш-таблицы. Я хотел знать то, что они и где можно лучше всего использовать их для.
3 ответа
Сначала вы, возможно, должны прочитать эту статью .
Когда вы используете списки и ищете особый элемент, вам обычно приходится перебирать весь список. Это очень дорого, когда у вас большие списки.
Хеш-таблица может быть намного быстрее. В лучшем случае вы получите искомый элемент только с одним доступом.
Как это работает? Как словарь ... когда вы ищете слово «хеш-таблица» в словаре, вы не начинаете с первого слова под «а». Но лучше сразу перейти к букве «h». Затем на «ха», «имеет» и так далее, пока не найдешь свое слово. Вы используете индекс в своем словаре, чтобы ускорить поиск.
Хеш-таблица в основном делает то же самое. Каждому элементу присваивается уникальный индекс (так называемый хэш ). Вы используете этот хеш для поиска. Хеш может быть индексом в обычном связном списке. Например, ваш хэш может быть числом вроде 2130, что означает, что вы должны смотреть на позицию 2130 в вашем списке. Поиск по известному индексу в обычном списке очень простой и быстрый.
Проблемой всего подхода является так называемая хэш-функция , которая присваивает этот индекс каждому элементу. Когда вы ищете товар, у вас должна быть возможность заранее рассчитать индекс. Как и в реальном словаре, где вы видите, что слово «хеш-таблица» начинается с буквы «h», и, следовательно, вы знаете приблизительную позицию.
Хорошая хэш-функция предоставляет хэш-коды, которые равномерно распределяются по пространству всех возможных хэш-кодов.И, конечно же, он пытается избежать коллизий . Конфликт происходит, когда два разных элемента получают один и тот же хэш-код.
Например, в C # у каждого объекта есть метод GetHashcode () , который предоставляет ему хэш (не обязательно уникальный). Это можно использовать для поиска и сортировки в вашем словаре.
Когда вы начинаете использовать хэш-таблицы, вы всегда должны помнить, что вы правильно обрабатываете коллизии. В больших хэш-таблицах может довольно легко случиться, что два объекта имеют одинаковый хэш (возможно, ваша перегрузка GetHashcode () неисправна, может быть, что-то еще произошло).
Хеширование (в некриптографическом смысле) - это общий термин для принятия входных данных и последующего создания выходных данных для их идентификации. Тривиальный пример хеширования - это сложение суммы букв строки, например:
f(abc) = 6
Обратите внимание, что эта тривиальная хеш-схема создаст конфликт между строками abc, bca, ae и т. Д. Эффективная схема хеширования, естественно, будет выдавать разные значения для каждой строки.
Хэш-карты и хэш-таблицы - это структуры данных (например, массивы и списки), которые используют хеширование для хранения данных. В хэш-таблице создается хэш (либо из предоставленного ключа, либо из самого объекта), который определяет, где в таблице хранится объект. Это означает, что до тех пор, пока пользователь хеш-таблицы знает ключ, получение объекта происходит очень быстро.
В списке, для сравнения, вам нужно каким-то образом выполнить поиск по списку, чтобы найти искомый объект. Это также представляет собой обратную сторону хэш-таблиц, заключающуюся в том, что очень сложно найти в ней объект, не зная ключа, потому что место, где объект хранится в таблице, не имеет отношения ни к его значению, ни к тому, когда он был введен.
Хэш-карты похожи на хэш-таблицы, но в них хранится только один пример каждого объекта (следовательно, ключ не требуется, ключ является самим объектом).
Это, конечно, очень простое объяснение, поэтому я предлагаю вам прочитать его подробно с этого момента. Надеюсь, я не совершил глупых ошибок. =)
По сути, HashMap позволяет хранить элементы с идентификаторами. Они хранятся в формате таблицы с идентификатором, хешируемым с использованием алгоритма хеширования.
Обычно они более эффективны для поиска элементов, чем деревья поиска и т. Д.
Вы можете найти это полезным: http://www.relisoft.com/book/lang/pointer/8hash.html
Надеюсь, это поможет,
Крис