¿Para qué se utiliza el código hash? ¿Es único?

129

Noto que hay un getHashCode()método en todos los controles, elementos, en WP7, que devuelve una secuencia de números. ¿Puedo usar este código hash para identificar un artículo? Por ejemplo, quiero identificar una imagen o una canción en el dispositivo y verificar su paradero. Esto podría hacerse si el código hash proporcionado para elementos específicos es único.

¿Pueden ayudarme a explicarme para qué sirve el hashCode getHashCode()?

Nghia Nguyen
fuente
Sé lo que significa hashCode, trato de ejecutar mi código muchas veces para obtener el hashcode y devuelve el mismo hashcode para los mismos elementos cada vez y no parece estar duplicado, pero no estoy muy seguro. Bueno, está bien si quieres hacer un voto negativo, es tu opinión. Gracias por la edición de todos modos!
Nghia Nguyen
77
Recomiendo leer las Pautas y reglas de Eric Lippert para GetHashCode , aunque se centra en las reglas para implementar HashCodes en lugar de las reglas para usarlas ... ya que son " por diseño útiles para una sola cosa: poner un objeto en una tabla hash"
Brian

Respuestas:

108

MSDN dice :

Un código hash es un valor numérico que se utiliza para identificar un objeto durante las pruebas de igualdad. También puede servir como índice para un objeto en una colección.

El método GetHashCode es adecuado para su uso en algoritmos hash y estructuras de datos como una tabla hash.

La implementación predeterminada del método GetHashCode no garantiza valores de retorno únicos para diferentes objetos. Además, .NET Framework no garantiza la implementación predeterminada del método GetHashCode, y el valor que devuelve será el mismo entre diferentes versiones de .NET Framework. En consecuencia, la implementación predeterminada de este método no debe utilizarse como un identificador de objeto único para propósitos de hash.

El método GetHashCode puede ser anulado por un tipo derivado. Los tipos de valor deben anular este método para proporcionar una función hash que sea apropiada para ese tipo y para proporcionar una distribución útil en una tabla hash. Para ser únicos, el código hash debe basarse en el valor de un campo o propiedad de instancia en lugar de un campo o propiedad estático.

Los objetos utilizados como clave en un objeto Hashtable también deben anular el método GetHashCode porque esos objetos deben generar su propio código hash. Si un objeto utilizado como clave no proporciona una implementación útil de GetHashCode, puede especificar un proveedor de código hash cuando se construye el objeto Hashtable. Antes de .NET Framework versión 2.0, el proveedor de código hash se basaba en la interfaz System.Collections.IHashCodeProvider. A partir de la versión 2.0, el proveedor de código hash se basa en la interfaz System.Collections.IEqualityComparer.

Básicamente, existen códigos hash para hacer posibles las tablas hash.
Se garantiza que dos objetos iguales tienen códigos hash iguales. No se garantiza que
dos objetos desiguales tengan códigos hash desiguales (eso se llama colisión).

SLaks
fuente
3
La cita del MSDN ahora está desactualizada. El MSDN ahora no es tan explícito acerca de que el código hash no es único.
user34660
248

Después de aprender de qué se trata, pensé en escribir una explicación con suerte más simple por analogía:

Resumen: ¿Qué es un código hash?

  • Es una huella digital. Podemos usar esta huella digital para identificar personas de interés.

Lea abajo para más detalles:

Piense en un Hashcode como nosotros tratando de identificar a alguien de manera única

Soy un detective, en busca de un criminal. Vamos a llamarlo señor cruel. (Era un asesino notorio cuando yo era un niño; irrumpió en una casa secuestrado y asesinó a una niña pobre, arrojó su cuerpo y todavía está suelto, pero eso es un asunto aparte). El Sr. Cruel tiene ciertas características peculiares que puedo usar para identificarlo de manera única entre un mar de personas. Tenemos 25 millones de personas en Australia. Uno de ellos es el señor Cruel. ¿Cómo podemos encontrarlo?

Malas formas de identificar al señor cruel

Al parecer, el señor Cruel tiene los ojos azules. Eso no es de mucha ayuda porque casi la mitad de la población en Australia también tiene ojos azules.

Buenas formas de identificar a Mr Cruel

¿Que más puedo usar? Lo sé: ¡usaré una huella digital!

Ventajas :

  • Es realmente muy difícil para dos personas tener la misma huella digital (no imposible, pero extremadamente improbable).
  • La huella digital del señor Cruel nunca cambiará.
  • Cada parte de todo el ser del señor Cruel: su aspecto, color de cabello, personalidad, hábitos alimenticios, etc. deben (idealmente) reflejarse en su huella digital, de modo que si tiene un hermano (que es muy similar pero no el mismo), entonces ambos debería tener diferentes huellas digitales. Digo "debería" porque no podemos garantizar al 100% que dos personas en este mundo tengan huellas digitales diferentes.
  • Pero siempre podemos garantizar que el Sr. Cruel siempre tendrá la misma huella digital, y que su huella digital NUNCA cambiará.

Las características anteriores generalmente hacen buenas funciones hash.

Entonces, ¿cuál es el problema con 'Collisions'?

Así que imagínense si consigo una pista y encuentro a alguien que coincida con las huellas digitales del señor Cruel. ¿Significa esto que he encontrado al señor Cruel?

........¡quizás! Debo echar un vistazo más de cerca. Si estoy usando SHA256 (una función de hashing) y estoy buscando en una ciudad pequeña con solo 5 personas, ¡entonces hay muchas posibilidades de que lo encuentre! Pero si estoy usando MD5 (otra función de hashing famosa) y estoy buscando huellas digitales en una ciudad con + 2 ^ 1000 personas, entonces es una posibilidad bastante buena de que dos personas completamente diferentes tengan la misma huella digital.

Entonces, ¿cuál es el beneficio de todo esto de todos modos?

El único beneficio real de los códigos hash es si quieres poner algo en una tabla hash, y con las tablas hash te gustaría encontrar objetos rápidamente, y ahí es donde entra el código hash. Te permiten encontrar cosas realmente en las tablas hash con rapidez. Es un truco que mejora enormemente el rendimiento, pero a un pequeño costo de precisión.

Así que imaginemos que tenemos una tabla hash llena de personas: 25 millones de sospechosos en Australia. El Sr. Cruel está en algún lugar allí ... ¿Cómo podemos encontrarlo realmente rápido ? Necesitamos clasificarlos a todos: para encontrar una posible coincidencia, o para absolver a posibles sospechosos. No debes considerar las características únicas de cada persona porque eso tomaría demasiado tiempo. ¿Qué usarías en su lugar? ¡Usarías un hashcode! Un código hash puede decirle si dos personas son diferentes. Si Joe Bloggs NO es el señor cruel. Si las impresiones no coinciden, entonces sabes que definitivamente NO es el Sr. Cruel. Pero, si las huellas digitales coincidenentonces, dependiendo de la función hash que usaste, es muy probable que hayas encontrado a tu hombre. Pero no es 100%. La única forma en que puede estar seguro es investigar más a fondo: (i) si tuvo una oportunidad / motivo, (ii) testigos, etc., etc.

Cuando usa computadoras si dos objetos tienen el mismo valor de código hash, entonces nuevamente necesita investigar más si son realmente iguales. por ejemplo, tendría que verificar si los objetos tienen, por ejemplo, la misma altura, el mismo peso, etc., si los enteros son iguales o si customer_id es una coincidencia, y luego llegar a la conclusión de si son iguales. esto normalmente se hace implementando un IComparer o interfaces de calidad IE.

Resumen clave

Entonces, básicamente, un código hash es una huella digital.

Huella digital - Atributo de imagen para Pixabay - Disponible gratuitamente para su uso en: https://pixabay.com/en/finger-fingerprint-security-digital-2081169/

  1. En teoría, dos personas / objetos diferentes pueden tener la misma huella digital. O en otras palabras. Si tiene dos huellas digitales que son iguales ... entonces no es necesario que ambas provengan de la misma persona / objeto.
  2. Buuuuuut, la misma persona / objeto siempre devolverá la misma huella digital .
  3. Lo que significa que si dos objetos devuelven códigos hash diferentes , entonces usted sabe con 100% de certeza que esos objetos son diferentes.

Tarda unos buenos 3 minutos en entender lo anterior. Quizás lo leas algunas veces hasta que tenga sentido. ¡Espero que esto ayude a alguien porque me costó mucho aprenderlo todo!

BKSpurgeon
fuente
1
Re: La documentación de MSDN mató algunas de mis células cerebrales ... llevó a algunas de las mías al borde del suicidio. salvo solo porque me quedé dormido;)
Shwrk
Destruiste toda tu agradable explicación con ese comentario de asterisco al final.
Waldemar Gałęzinowski
¡Me encantó! principalmente el nombre "Mr.Cruel!"
João Pedro Andrade Marques
Como un verdadero fanático del crimen, esta es posiblemente mi respuesta SO favorita ... alguna vez.
IfElse TryCatch
11

GetHashCode()se utiliza para ayudar a utilizar el objeto como clave para las tablas hash. (Algo similar existe en Java, etc.). El objetivo es que cada objeto devuelva un código hash distinto, pero esto a menudo no se puede garantizar absolutamente. Sin embargo, se requiere que dos objetos lógicamente iguales devuelvan el mismo código hash.

Una implementación típica de la tabla hash comienza con el valor hashCode, toma un módulo (restringiendo así el valor dentro de un rango) y lo usa como índice de una matriz de "cubos".

Seand
fuente
8

No es exclusivo de WP7, está presente en todos los objetos .Net. De alguna manera hace lo que usted describe, pero no lo recomendaría como un identificador único en sus aplicaciones, ya que no se garantiza que sea único.

Método Object.GetHashCode

Phil Sandler
fuente
4

Esto es del artículo de msdn aquí:

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

"Si bien escuchará a las personas decir que los códigos hash generan un valor único para una entrada dada, el hecho es que, aunque es difícil de lograr, es técnicamente factible encontrar dos entradas de datos diferentes que tengan el mismo valor . Sin embargo, lo cierto Los factores determinantes con respecto a la efectividad de un algoritmo hash radican en la longitud del código hash generado y la complejidad de los datos que se van a hash ".

Tan solo use un algoritmo hash adecuado para su tamaño de datos y tendrá códigos hash únicos.

Shree Harsha
fuente