Что такое хеш-функция в Java?
Я имею, проверяют эту страницу Wikipedia на него, но я все еще не понимаю это. Кто-то может помочь моему недалекому уму понять понятие хеширования, hashtable/hashmap, и хеш-функции? Некоторые примеры действительно помогли бы.
4 ответа
В статье в Википедии будет много технической информации, но упрощенный взгляд на хеширование выглядит примерно так.
Представьте, что существует магическая функция, которая может дать число любому объекту. Для одного и того же объекта он всегда возвращает одно и то же число.
Теперь у вас есть быстрый способ проверить, являются ли два объекта одинаковыми: запросите у этой функции их номера и сравните. Если они разные, значит, они не такие.
Но что, если у них одинаковые номера? Может ли два разных объекта иметь одинаковый номер?
Да, это возможно в большинстве сценариев. Предположим, что функция может выдавать только числа от 1 до 10, например, и существует 100 различных объектов. Тогда, конечно, некоторые разные объекты должны иметь одинаковые номера. Это то, что называется «столкновением». «Столкновение» делает наш быстрый тест на равенство не таким полезным, поэтому мы хотим максимально свести его к минимуму. Хорошая магическая функция - это попытка минимизировать количество «столкновений».
Так что еще можно сделать с этим номером? Ну, вы можете использовать его для индексации массива. Получив объект, вы можете поместить его по индексу, заданному числом из этой магической функции. По сути, этот массив и есть хеш-таблица; эта волшебная функция - хеш-функция.
Хэш-функция - это способ создания компактного представления произвольно большого объема данных. В java с помощью метода hashcode это означает каким-то образом описать состояние вашего объекта (неважно какого размера) в виде int (4 байта). И обычно это записывается довольно быстро, как объясняется ниже.
Для упрощения в хэш-таблицах/хэшмапах хэшкод служит своего рода дешевым эквивалентом. Возьмем два объекта a и b типа Foo, скажем, чтобы узнать, равно ли a.equals(b), потребуется 500 мс, тогда как вычисление (эффективного) хэш-кода займет всего 10 мс. Поэтому, если мы хотим узнать, равно ли a.equals(b), вместо того чтобы делать это напрямую, мы сначала посмотрим на хэш-коды и спросим, равно ли a.hashCode() == b.hashCode(). Обратите внимание, что в нашем примере это займет всего 20 мс.
Из определения хэшкода в API мы знаем, что если хэшкод a не равен b, то a.equals(b) никогда не должен быть истинным. Поэтому в нашем вышеприведенном тесте, если мы видим, что хэш-коды не равны, нам никогда не нужно выполнять более длинный тест .equals(), вот почему вы всегда должны переопределять hashCode и equals вместе.
Вы также можете встретить упоминания о написании "хороших" или "хорошо распределенных" хэш-кодов. Это связано с тем, что обратное предыдущим утверждениям о hashcode и equals не верно. Более конкретно a.hashCode() == b.hashCode() не обязательно подразумевает a.equals(b) Таким образом, идея хорошего хэш-кода заключается в том, что вы уменьшаете вероятность того, что a.hashCode() == b.hashCode(), когда a.equals(b) ложно. Возможно, вы видели, что это называется коллизией хэш-функции.
Вернемся к хэшмапам/таблицам. Они основаны на парах ключ/значение. Поэтому, когда вы добавляете или извлекаете значение, вы предоставляете ключ. Поэтому первое, что должна сделать карта, это найти ключ, что означает найти что-то, что .equals() предоставленного вами ключа. Но, как мы обсуждали выше, .equals() может быть невероятно медленным, поэтому сравнение можно значительно ускорить, если сначала проверить хэш-коды. Поскольку, когда хэш-коды хорошо распределены, вы должны быстро понять, когда x определенно != y.
Теперь в дополнение к сравнению хэш-карты/таблицы фактически используют хэш-коды для организации внутреннего хранения данных, однако я думаю, что это выходит за рамки того, что вы хотите понять на данном этапе.
Эта книга (и вспомогательные видеолекции ) предоставляют отличное объяснение алгоритмов и структур данных. Есть несколько лекций о хэш-функциях ( 1 , 2 ). Я бы рекомендовал это.
(источник: mit.edu )
Кроме того, просто FYI, Не совсем так, как указано в комментариях polygenelubricants . hashCode () , вызванный экземпляром класса Object , возвращает адрес этого конкретного экземпляра в памяти.
Хеш-таблица - это, по сути, способ сохранить что-либо в массиве и получить это почти так же быстро, как поиск чего-либо в массиве через индекс, не тратя слишком много места.
Задача хэш-функции (в данном контексте) - вычислить индекс массива, в котором будет храниться объект, на основе содержимого объекта. Это означает, что он всегда должен возвращать один и тот же результат для одного и того же объекта и должен возвращать разные результаты для разных объектов, насколько это возможно. Когда два разных объекта имеют один и тот же хэш, это называется «столкновением», и вы должны обрабатывать эти случаи специально, что замедляет все это.