Что такое хеш-функция в Java?
Я проверил эту страницу в Википедии, но до сих пор не понимаю. Может ли кто-нибудь помочь моему тупому разуму понять концепции хеширования, хэш-таблицы / хэш-карты и хэш-функций? Некоторые примеры действительно помогут.
7 ответов
В статье Википедии будет много технической информации, но упрощенное представление о хешировании выглядит примерно так.
Представьте, что есть магическая функция, которая может дать число любому объекту. Учитывая один и тот же объект, он всегда возвращает один и тот же номер.
Теперь у вас есть быстрый способ проверить, совпадают ли два объекта: спросите у этой функции их номера и сравните. Если они разные, значит, они не одинаковые.
Но что, если у них одинаковый номер? Могут ли два разных объекта иметь одинаковый номер?
Да, это возможно в большинстве сценариев. Допустим, что функция может давать только числа от 1..10, например, и есть 100 различных объектов. Тогда, конечно, некоторые разные объекты должны иметь одинаковые номера. Это то, что называется "столкновением". "Столкновение" делает наш быстрый тест на равенство не таким полезным, поэтому мы стараемся свести его к минимуму. Хорошей магической функцией является та, которая пытается минимизировать количество "столкновений".
Так что еще можно сделать с этим номером? Ну, вы можете использовать его для индексации массива. Для данного объекта вы можете поместить его в индекс, указанный числом из этой магической функции. Этот массив по сути является хеш-таблицей; эта магическая функция является хэш-функцией.
Хеш-функция - это способ создать компактное представление произвольно большого объема данных. В 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) ложно. Возможно, вы видели, что это называется столкновением хэш-функции.
Вернуться к хэш-картам / таблицам. Они основаны на парах ключ / значение. Поэтому, когда вы добавляете или извлекаете значение, вы предоставляете ключ. Поэтому первое, что нужно сделать карте, - это найти ключ, что означает поиск чего-то, что.equals() дает ключ, который вы предоставляете. Но, как мы уже говорили выше,.equals() может быть невероятно медленным, что означает, что сравнение может быть значительно ускорено, если сначала проверять хеш-коды Поскольку, когда хеш-коды хорошо распределены, вы должны быстро знать, когда x определенно!= Y.
Теперь в дополнение к хеш-таблицам / таблицам сравнения фактически используют хеш-коды для организации своего внутреннего хранения данных, однако я думаю, что это выходит за рамки того, что вы хотите понять на данном этапе.
HASH FUNCTION:- Хеш-функция берет группу символов (называемую ключом) и отображает ее на значение определенной длины (называемое хеш-значением или хешем). Значение хеша является представителем исходной строки символов, но обычно меньше, чем оригинал. Хеширование выполняется для индексации и размещения элементов в базах данных, поскольку легче найти более короткое значение хеш-функции, чем более длинную строку. Хеширование также используется в шифровании. Этот термин также известен как алгоритм хеширования или функция дайджеста сообщения.
HASH MAP: - HashMap - это класс коллекции, предназначенный для хранения элементов в виде пар ключ-значение. Карты предоставляют способ поиска одной вещи в зависимости от ценности другой.
Таблица поиска, предназначенная для эффективного хранения несмежных ключей (номеров счетов, номеров деталей и т. Д.), Которые могут иметь большие пробелы в их алфавитной или числовой последовательности.
Хеш-таблица: - Хеш-таблицы создаются с помощью алгоритма, который хранит ключи в хеш-памяти, которые содержат пары ключ-значение. Поскольку разные ключи могут хешироваться в одном и том же сегменте, цель разработки хэш-таблицы состоит в том, чтобы равномерно распределить пары ключ-значение, причем каждый набор содержит как можно меньше пар ключ-значение. Когда предмет ищется, его ключ хэшируется, чтобы найти соответствующий сегмент, а затем сравнивается, чтобы найти правильную пару ключ-значение.
Эта книга (и вспомогательные видео лекции) дают отличное объяснение алгоритмов и структур данных. Есть несколько лекций о хэш-функциях ( 1, 2). Я бы порекомендовал это.
Кроме того, просто к вашему сведению, hashCode() , вызванный по случаю Object Класс возвращает адрес этого конкретного экземпляра в памяти. Не совсем верно, как указано в комментариях polygenelubricants.
Хеш-таблица - это в основном способ хранения чего-либо в массиве и извлечения его почти так же быстро, как поиск чего-либо в массиве по индексу, не тратя слишком много места.
Задача хэш-функции (в этом контексте) состоит в том, чтобы вычислить индекс массива, в котором будет храниться объект, на основе содержимого объекта. Это означает, что он должен всегда возвращать один и тот же результат для одного и того же объекта и должен возвращать разные результаты для разных объектов в максимально возможной степени. Когда два разных объекта имеют один и тот же хэш, это называется "столкновением", и вы должны обрабатывать эти случаи специально, что замедляет процесс.
Хэш-функция: если вы передаете один и тот же объект этой функции любое количество раз, будь то текст, двоичный код или число, вы всегда получаете один и тот же вывод. Для целей хеш-таблицы используется целочисленная возвращающая хеш-функция.
Выше функциональность вызывает хеширование.
Хеш-таблица: Чудесная структура данных компьютерной науки, которая возвращает результат поиска в постоянном времени или O(1). Он основан на вышеупомянутой концепции хеширования. Таким образом, он имеет лучшее время доступа, чем связанный список, деревья двоичного поиска и т. Д.
Почему почти O(1): он использует массив в качестве своей базовой структуры для хранения объектов, и, поскольку массивы имеют постоянное время доступа, следовательно, таблица Hash делает то же самое.
[Базовое внутреннее]: Итак, он использует массив фиксированного размера внутри, и когда вы вставляете пару (Key, Value), он вычисляет хэш ключа и использует это значение хеш-функции в качестве индекса для хранения пары (Key, Value) в массиве., Затем, когда вы ищете объект, используя тот же ключ, он снова использует хеш ключа в качестве индекса для поиска ключа в массиве. Теперь два объекта могут иметь одинаковое хеш-значение и, следовательно, при вставке этих объектов в хеш-таблицу произойдет столкновение. Есть два способа разрешения столкновений. Вы можете обратиться по этой ссылке для достаточно подробного обсуждения этой темы.
Отображение ключей на индексы хеш-таблицы называется хеш-функцией. Хеш-функция состоит из двух частей
Карта хэш-кода: конвертирует ключи в целые числа любого диапазона.
Карта сжатия: она преобразует (выводит) эти целые числа в диапазон ключей, который имеет хеш-таблица.
Взято с http://coder2design.com/hashing/
HashCode() функция, которая возвращает целочисленное значение, используется HashMap найти правильное ведро.