Los algoritmos de hash son como una pequeña máquina que toma un valor y devuelve otro valor basado en una función de hashing. Esta función de hash puede ser simple o compleja. Si tuviéramos que buscar un objeto en una lista, tendríamos que revisar cada objeto en una lista. Sin embargo, si utilizamos una función de hash para indexar una ubicación basada en la clave del objeto, podríamos recuperar su valor muy rápidamente yendo a ese índice en particular. Por lo tanto, el hash acelera la búsqueda de un objeto en una lista.
Una función hash simple podría ser una que devuelva la suma de los valores ASCII de los caracteres. Imagine que quiero colocar un objeto {‘cat’: ‘miau’} en una lista de tamaño 1000. hash (‘cat’) sería 99 + 97 + 116 = 312. Entonces, colocaría {‘cat’: ‘ miau ‘} en el índice 312 de mi lista. {‘lamb’: ‘baa’} se colocaría en 108 + 97 + 109 + 98 = 412 índice de mi lista. Si tuviera que encontrar el valor de la clave ‘cat’, lo pasaría a través de mi función hash, que devolvería 312. Luego miraría el índice 312, y su contenido sería {‘cat’: ‘miau’ }. Hasta aquí todo bien.
Sin embargo, ¿qué sucede si tuviera que colocar {‘act’: ‘good’} en mi lista? La suma de los valores ASCII de los caracteres equivaldría a 312, por lo que sobrescribiría {‘cat’: ‘miau’} en mi lista. Esto se llama colisión. Aquí tenemos dos opciones:
- ¿Por qué el número total de respuestas en mi cuenta de Quora disminuyó repentinamente en 10?
- Interacción humano-computadora: ¿Qué tan difícil sería escribir un algoritmo que pudiera identificar similitudes en las expresiones faciales entre dos imágenes tomadas en la cabeza?
- Soy un programador promedio, me encanta codificar en Java y estoy tratando de mejorar mis habilidades de codificación algorítmica. ¿Cómo puedo mejorarlos?
- ¿Puedo volverme competente en estructuras de datos y algoritmos sin leer el libro CLRS?
- ¿Qué significan términos como inicialización, evaluación, selección, cruce, mutación en el contexto de algoritmos genéticos?
- Cree una función de hash más compleja que diferenciaría entre la ubicación del personaje, dando así un valor diferente para ‘act’ y ‘cat’, y aumentaría enormemente el tamaño de nuestra lista. Todavía hay una pequeña posibilidad de colisión , pero las operaciones de búsqueda serán muy rápidas . El único inconveniente es que la lista ocupa mucho espacio.
- Emplee cubos, que pueden almacenar una lista dentro de una lista. Entonces podemos colocar tanto {‘act’: ‘good’} como {‘cat’: ‘meow’} dentro de una lista en el índice 312. Si tenemos que buscar ‘act’ en nuestra lista, pasamos ‘act’ a través de nuestra función de hashing que devuelve 312, y luego busca la clave ‘act’ dentro de nuestra mini lista en el índice 312, y devuelve ‘good’. La desventaja de esto es que las operaciones de búsqueda serán más lentas si las listas en un determinado índice se vuelven masivas en tamaño. La solución a esto es redimensionar (hacer más grande) la lista y volver a trocear cada objeto de la lista en nuevas ubicaciones de índice.
Espero que esto te haya dado un buen punto de entrada a las funciones de hash. Los algoritmos de hash pueden ser muy complejos de entender, pero la redacción anterior debería darle una buena base.
