Что такое хеш-функция в Java?

Question

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

Answer 1

В статье Википедии будет много технической информации, но упрощенное представление о хешировании выглядит примерно так:

Представьте, что есть магическая функция, которая может давать число любому объекту.Учитывая один и тот же объект, он всегда возвращает одно и то же число.

Сразу же у вас есть быстрый способ проверить, совпадают ли два объекта: спросите у этой функции их номера и сравните.Если они разные, значит, они не одинаковые.

Но что, если у них одинаковое число?Могут ли два разных объекта иметь одинаковое число?

Да, это возможно в большинстве сценариев.Допустим, что функция может давать только числа от 1..10, например, и есть 100 различных объектов.Тогда, конечно, некоторые разные объекты должны иметь одинаковые номера.Это то, что называется «столкновение».«Столкновение» делает наш быстрый тест на равенство не таким полезным, поэтому мы стараемся свести его к минимуму.Хорошей магической функцией является та, которая пытается минимизировать количество «столкновений».

Так что еще вы можете сделать с этим числом?Ну, вы можете использовать его для индексации массива.Для данного объекта вы можете поместить его в индекс, указанный числом из этой магической функции.Этот массив по сути является хеш-таблицей;эта магическая функция является хеш-функцией.

Answer 2

Хеш-функция - это способ создать компактное представление произвольно большого объема данных. В java с методом hashcode это означает, что как-то описывается состояние вашего объекта (независимо от его размера) в int (4 байта). И обычно пишется достаточно быстро, как объясняется ниже.

Чтобы упростить хеш-таблицы / хеш-карты, хеш-код служит своего рода дешевым равным. Возьмем два объекта a и b типа Foo, который позволяет say говорит, что a.equals (b) занимает 500 мс, а для вычисления (эффективного) хеш-кода требуется всего 10 мс. Поэтому, если мы хотим знать, если a.equals (b) вместо того, чтобы делать это непосредственно, мы сначала посмотрим на хеш-коды и спросим, ​​выполняет ли a.hashCode () == b.hashCode (). Обратите внимание, что в нашем примере это займет всего 20 мс.

Из-за определения API хеш-кода мы знаем, что если хеш-код a не равен b, то a.equals (b) никогда не должно быть истинным. Так что в нашем тесте выше, если мы увидим хеш-коды неравны, тогда нам больше не нужно выполнять более длинный тест .equals (), поэтому вы всегда должны переопределять hashCode и равны вместе .

Вы также можете увидеть ссылки на написание "хороших" или "хорошо распределенных" хеш-кодов. Это связано с тем, что обратное предыдущее утверждение о хэш-коде и равно не соответствует действительности. В частности, a.hashCode () == b.hashCode () не обязательно подразумевает a.equals (b) Так что идея хорошего хеш-кода состоит в том, что вы уменьшаете вероятность a.hashCode () == b.hashCode (), когда a.equals (b) имеет значение false. Возможно, вы видели это как столкновение хэш-функции.

Вернуться к хэш-картам / таблицам. Они основаны на парах ключ / значение. Поэтому, когда вы добавляете или извлекаете значение, вы предоставляете ключ. Поэтому первое, что нужно сделать карте, - это найти ключ, что означает поиск чего-то, что .equals () дает ключ, который вы предоставляете. Но, как мы уже говорили выше, .equals () может быть невероятно медленным, что означает, что сравнение может быть значительно ускорено, если сначала проверять хеш-коды Поскольку, когда хеш-коды хорошо распределены, вы должны быстро знать, когда x определенно! = Y.

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

Answer 3

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

Кормен http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/chp_6046textcove.jpg

Кроме того, только FYI, hashCode(), вызванный для экземпляра класса Object, возвращает адрес этого конкретного экземпляра в памяти. Не совсем верно, как указано полигеномасляными веществами в комментариях.

Answer 4

HashCode() Функция, которая возвращает целочисленное значение, используется HashMap для поиска правильного сегмента.

Answer 5

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

HASH MAP: - HashMap - это класс коллекции, предназначенный для хранения элементов в виде пар ключ-значение.Карты предоставляют способ поиска одной вещи в зависимости от ценности другой.

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

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

Answer 6

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

Выше функциональность вызывает хеширование.

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

Почему почти O (1): он использует массив в качестве своей базовой структуры для хранения объектов, и, поскольку массивы имеют постоянное время доступа, следовательно, таблица Hash делает то же самое.

[Основной внутренний]: Таким образом, он использует массив фиксированного размера внутри, а когда вы вставляете пару (Key, Value), он вычисляет хэш ключа и использует это значение в качестве индекса для хранения пары (Key, Value) в массиве. Затем, когда вы ищете объект, используя тот же ключ, он снова использует хеш ключа в качестве индекса для поиска ключа в массиве. Теперь два объекта могут иметь одинаковое хеш-значение и, следовательно, при вставке этих объектов в хеш-таблицу произойдет столкновение. Есть два способа разрешения столкновений. Вы можете обратиться по этой ссылке для достаточно подробного обсуждения этой темы.

Answer 7

Отображение ключей на индексы хеш-таблицы называется хеш-функцией. Хеш-функция состоит из двух частей

Карта хэш-кода : преобразует ключи в целое число любого диапазона.

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

Взято из http://coder2design.com/hashing/

Answer 8

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

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