¿Cómo funcionan los hashes en la programación?

Question

¿Cómo funcionan los hash en la programación? La forma en que pienso en un hash es algo que me permite usar un valor único para recuperar algunos datos. Al igual que si tenemos una matriz y empiezo a poner cosas en la matriz, si tengo otra variable que realiza un seguimiento de qué elemento está en la ranura 0,1,2 ... entonces tengo esa capacidad instantánea para encontrar un elemento. ¿Eso es hash?

¿Cuál es el propósito de un hash?

¿Cuándo se debe implementar un hash? ¿Qué es un hash similar en términos de estructura de datos?

Lo que creo que sé sobre hashes es que nos permite recuperar el elemento dentro de O (1). ¿Es eso correcto?

Answer 1

Un hash map/dictionary es una estructura de datos clave/valor que almacena objetos en cubos según el valor de una función hash. Estas claves deben ser únicas, pero los valores de la función hash (a veces llamados hashcodes) no son necesariamente únicos.

Me gusta si tenemos una matriz y empiezo a poner htings en la matriz, si tengo otra varible que realiza un seguimiento de qué elemento está en la ranura 0,1,2 ... entonces tengo esa capacidad instantánea para encontrar un artículo ¿Eso es hash?

No. Una función hash es una función determinística que siempre da el mismo valor para un objeto. El código hash no cambia dependiendo de dónde se almacena el objeto.

Lo que creo que sé sobre hashes es que nos permite recuperar el objeto dentro de O (1). ¿Es eso correcto?

Casi. Un diccionario tiene O (1) complejidad para búsquedas si no hay demasiadas colisiones de código hash. Sin embargo, si la función hash es pobre y cada objeto tiene el mismo valor hash, entonces un diccionario podría tener un rendimiento O (n).

Answer 2

Un hash es como el primer nombre de una persona; es una forma breve de recordar a una persona, aunque no tiene que ser única. Si necesita encontrar información sobre alguien, puede ponerlos por su nombre, y solo necesita realizar otros controles si dos o más personas tienen el mismo nombre. Ese es el poder de hash, y así como recordar personas es mucho más fácil por nombre que por Número de Seguridad Social, encontrar un objeto por su código es mucho más fácil que comparar el objeto con todo lo que ya está en su colección.

Ahora, en este ejemplo, si busca a alguien en una guía telefónica por nombre, probablemente los encuentre en el tiempo O (log n), porque los nombres están ordenados alfabéticamente y porque necesita hacer una búsqueda binaria Sin embargo, si en lugar de eso has "pirateado" a 100 personas nacidas en los años 1900 por sus años de nacimiento, solo necesitarías como máximo 4 comparaciones en la tabla/libro telefónico (una por dígito) para encontrar un año por medio de hash, que es tiempo constante. Entonces, si dos personas nacen de la misma manera, puede usar otra información para encontrar a la persona que necesita y, en promedio, si su tabla no está demasiado llena (por ejemplo, si tiene como máximo 50 personas durante 100 años diferentes de nacimiento), sus búsquedas serán constantes.

(Si la tabla se vuelve más que, por ejemplo, el 50% de su capacidad, siempre se puede duplicar su tamaño, para mantener el número de colisiones de baja y por lo tanto para mantener sus operaciones de búsqueda rápida.)

---

Más información :

Si alguna vez ha oído hablar de MD5 o SHA-1 SHA-2 hashes para archivos, son como las "huellas dactilares" del archivo. Si bien es posible tener dos archivos con el mismo hash, esto es tan improbable que, para fines prácticos, es imposible; por lo tanto, si tiene el hash de dos archivos, puede comparar los archivos por sus huellas digitales en lugar de por sus datos, que es inmensamente más rápido.

Answer 3

A hash lo hace rápido para buscar en lugar de iterar sobre una matriz o árbol. Hace posible el tiempo de búsqueda O(1) con poco uso de la memoria.