Для чего используется хэш-код? Это уникально?

129

Я заметил, что getHashCode()в каждом элементе управления и элементах WP7 есть метод, который возвращает последовательность чисел. Могу ли я использовать этот хэш-код для идентификации предмета? Например, я хочу определить изображение или песню на устройстве и проверить, где они находятся. Это можно сделать, если хэш-код, присвоенный конкретным элементам, уникален.

Не могли бы вы объяснить мне, что такое hashCode и getHashCode()для чего он нужен ?

Нгиа Нгуен
источник
Я знаю, что означает hashCode, я пытаюсь запустить свой код много раз, чтобы получить хэш-код, и он каждый раз возвращает один и тот же хэш-код для одних и тех же элементов и, похоже, не дублируется, но я просто не очень уверен. Что ж, ничего страшного, если вы хотите проголосовать против, это ваше мнение. В любом случае спасибо за редактирование!
Нгиа Нгуен
7
Я рекомендую прочитать Руководство и правила Эрика Липперта для GetHashCode , хотя он фокусируется на правилах для реализации HashCodes, а не на правилах их использования ... поскольку они « по дизайну полезны только для одного: помещения объекта в хеш-таблицу»
Брайан

Ответы:

108

MSDN говорит :

Хэш-код - это числовое значение, которое используется для идентификации объекта во время проверки на равенство. Он также может служить индексом для объекта в коллекции.

Метод GetHashCode подходит для использования в алгоритмах хеширования и структурах данных, таких как хеш-таблица.

Реализация по умолчанию метода GetHashCode не гарантирует уникальных возвращаемых значений для разных объектов. Кроме того, .NET Framework не гарантирует реализацию метода GetHashCode по умолчанию, и значение, которое он возвращает, будет одинаковым для разных версий .NET Framework. Следовательно, реализация этого метода по умолчанию не должна использоваться в качестве уникального идентификатора объекта для целей хеширования.

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

Объекты, используемые в качестве ключа в объекте Hashtable, также должны переопределять метод GetHashCode, потому что эти объекты должны генерировать свой собственный хэш-код. Если объект, используемый в качестве ключа, не обеспечивает полезную реализацию GetHashCode, вы можете указать поставщика хэш-кода при создании объекта Hashtable. До .NET Framework версии 2.0 поставщик хэш-кода был основан на интерфейсе System.Collections.IHashCodeProvider. Начиная с версии 2.0 поставщик хэш-кода основан на интерфейсе System.Collections.IEqualityComparer.

По сути, хеш-коды существуют, чтобы сделать хэш-таблицы возможными.
Два одинаковых объекта гарантированно будут иметь одинаковые хэш-коды. Не гарантируется, что
два неравных объекта будут иметь разные хэш-коды (это называется коллизией).

SLaks
источник
3
Цитата из MSDN теперь устарела. В MSDN теперь не так явно говорится о том, что хэш-код не является уникальным.
user34660
249

Узнав, что это такое, я решил написать, надеюсь, более простое объяснение по аналогии:

Резюме: что такое хэш-код?

  • Это отпечаток пальца. Мы можем использовать этот отпечаток пальца, чтобы идентифицировать интересующих вас людей.

Подробнее читайте ниже:

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

Я детектив, ищу преступника. Назовем его мистером Жестоким. (Он был известным убийцей, когда я был ребенком - он ворвался в дом, похитил и убил бедную девушку, бросил ее тело, а он все еще на свободе - но это отдельный вопрос). У мистера Крула есть определенные особенности, которые я могу использовать, чтобы однозначно идентифицировать его среди множества людей. У нас в Австралии 25 миллионов человек. Один из них - мистер Круэл. Как его найти?

Плохие способы идентифицировать мистера Крула

Судя по всему, у мистера Крула голубые глаза. Это не очень помогает, потому что почти половина населения Австралии также имеет голубые глаза.

Хорошие способы идентифицировать мистера Крула

Что еще я могу использовать? Я знаю: я воспользуюсь отпечатком пальца!

Преимущества :

  • Двум людям действительно очень сложно иметь один и тот же отпечаток пальца (что не невозможно, но крайне маловероятно).
  • Отпечаток пальца мистера Крула никогда не изменится.
  • Каждая часть всего существа мистера Крула: его внешний вид, цвет волос, личность, пищевые привычки и т. Д. Должны (в идеале) отражаться в его отпечатке пальца, так что если у него есть брат (очень похожий, но не такой же), то оба должны быть разные отпечатки пальцев. Я говорю «должен», потому что мы не можем на 100% гарантировать, что у двух людей в этом мире будут разные отпечатки пальцев.
  • Но мы всегда можем гарантировать, что у мистера Крула всегда будет один и тот же отпечаток пальца - и что его отпечаток НИКОГДА не изменится.

Вышеупомянутые характеристики обычно обеспечивают хорошие хеш-функции.

Так в чем же дело с «столкновениями»?

Так что представьте, если я получу зацепку и найду кого-нибудь, кто совпадет с отпечатками пальцев мистера Крула. Означает ли это, что я нашел мистера Крула?

........ возможно! Я должен присмотреться. Если я использую SHA256 (функция хеширования) и ищу в небольшом городке, где проживает всего 5 человек, то есть очень хорошие шансы, что я его нашел! Но если я использую MD5 (еще одну известную функцию хеширования) и проверяю отпечатки пальцев в городе с + 2 ^ 1000 человек, то вполне вероятно, что два совершенно разных человека могут иметь один и тот же отпечаток пальца.

Так в чем же польза от всего этого?

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

Итак, давайте представим, что у нас есть хеш-таблица, заполненная людьми - 25 миллионов подозреваемых в Австралии. Мистер Круэл где-то там ... Как мы можем найти его действительно быстро ? Нам нужно их все разобрать: найти потенциального совпадения или иным образом оправдать потенциальных подозреваемых. Вы не хотите учитывать уникальные характеристики каждого человека, потому что это займет слишком много времени. Что бы вы использовали вместо этого? Вы бы использовали хэш-код! Хэш-код может сказать вам, если два человека разные. Является ли Джо Блоггс Мистером Жестоким. Если отпечатки не совпадают, значит, это точно НЕ Мистер Круэл. Но если отпечатки пальцев совпадаюттогда, в зависимости от хэш-функции, которую вы использовали, скорее всего, вы уже нашли своего мужчину. Но это не 100%. Единственный способ быть уверенным - это продолжить расследование: (i) имел ли он / она возможность / мотив, (ii) свидетели и т. Д. И т. Д.

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

Ключевое резюме

По сути, хэш-код - это отпечаток пальца.

Цифровой отпечаток пальца - атрибут изображения для Pixabay - бесплатно доступен для использования по адресу: https://pixabay.com/en/finger-fingerprint-security-digital-2081169/

  1. Теоретически у двух разных людей / объектов может быть один и тот же отпечаток пальца. Или другими словами. Если у вас есть два одинаковых отпечатка пальца ......... тогда они не обязательно должны быть получены от одного и того же человека / объекта.
  2. Буууууут, один и тот же человек / объект всегда будет возвращать один и тот же отпечаток пальца .
  3. Это означает, что если два объекта возвращают разные хэш-коды, то вы со 100% уверенностью знаете, что эти объекты разные.

На то, чтобы осмыслить вышесказанное, потребуется добрых 3 минуты. Возможно, прочтите его несколько раз, пока он не станет понятен. Я надеюсь, что это кому-то поможет, потому что мне пришлось очень горевать, чтобы все это выучить!

BKSpurgeon
источник
1
Re: Документация MSDN убила несколько клеток моего мозга .... довела довольно много моих до самоубийства. спасли только потому, что я заснул;)
Shwrk
Вы уничтожили все свое красивое объяснение этим комментарием звездочкой в ​​конце.
Вальдемар Галензиновски
Я люблю это! в основном имя «Мистер Круэл!»
Жуан Педро Андраде Маркес
Как настоящий фанат преступности, это, возможно, мой самый любимый ответ ТАК ... когда-либо.
IfElseTryCatch
11

GetHashCode()используется для поддержки использования объекта в качестве ключа для хеш-таблиц. (Аналогичная вещь существует в Java и т. Д.). Цель состоит в том, чтобы каждый объект возвращал отдельный хэш-код, но это часто не может быть абсолютно гарантировано. Однако требуется, чтобы два логически равных объекта возвращали один и тот же хэш-код.

Типичная реализация хеш-таблицы начинается со значения hashCode, принимает модуль (тем самым ограничивая значение в пределах диапазона) и использует его в качестве индекса для массива «сегментов».

seand
источник
8

Это не уникально для WP7 - оно присутствует во всех объектах .Net. Он вроде как делает то, что вы описываете, но я бы не рекомендовал его в качестве уникального идентификатора в ваших приложениях, поскольку его уникальность не гарантируется.

Object.GetHashCode - метод

Фил Сэндлер
источник
4

Это из статьи msdn здесь:

https://blogs.msdn.microsoft.com/tomarcher/2006/05/10/are-hash-codes-unique/

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

Поэтому просто используйте алгоритм хеширования, подходящий для вашего размера данных, и он будет иметь уникальные хэш-коды.

Шри Харша
источник