Para simplificar la visualización de las funciones hash, piénselo de esta manera:
(Muchas ideas en informática también pueden pensarse en términos de cosas más simples que hacemos en la vida cotidiana)
Dado un registro de todas las palabras en el idioma inglés, ¿cómo buscaría palabras o insertaría nuevas palabras en el registro rápidamente? Bueno, hay cientos de miles de palabras, por lo que para un acceso rápido necesitamos alguna forma de organizarlas.
Orden ordenado: esto es lo que hacen en los diccionarios. Organice todas las palabras en orden lexicográfico. Esto hace que la búsqueda sea muy fácil. Sin embargo hay un problema. No puede agregar palabras nuevas fácilmente, ya que necesita exprimirlas entre otras 2 palabras ya existentes, por lo tanto, desplazar hacia abajo todas las palabras después de 1 entrada.
- ¿Cuál es la diferencia entre la barra diagonal (/) y la barra diagonal inversa (\)?
- ¿Cuándo la regresión logística funciona mal y se debe preferir la máquina de vectores de soporte (SVM)?
- Si tengo un año para ser realmente bueno en programación algorítmica y todavía no he probado suerte en programación competitiva, ¿cuál debería ser mi enfoque?
- Informática: ¿Por qué la memoria contenida en los registros es tan costosa?
- ¿Cómo puede contribuir la informática a la producción de energía renovable?
Hashing: la otra opción es abandonar por completo la idea de un arreglo total de cualquier cosa. Nos conformaremos con esto: sería más fácil buscar cosas si sabes en general dónde están. Por ejemplo, al buscar una ropa de un determinado color, sería mucho más fácil si hubiera tirado toda la ropa amarilla en una canasta amarilla, las verdes en una canasta verde, azul a azul, etc.
En un diccionario, esto se puede hacer simplemente renunciando a la idea de un orden perfecto de las palabras. En cambio, simplemente dividimos todo el diccionario en, digamos, 26 secciones, y agrupamos las palabras en una sección basada en el primer carácter de la palabra. Claro, cuando agrega cosas a la sección, todos los pedidos se complican. (Por ejemplo, puede agregar las palabras en este orden, “Jungle”, “Japan”, “Jitters”, “Jet”, …) Sin embargo, al realizar la búsqueda, sabe que solo necesita mirar a través de las palabras en Sección “J” para encontrar la respuesta.
Esta idea de tratar de asignar elementos a “cubos” específicos se llama hashing. Obviamente, el mismo objeto DEBE terminar siempre en el mismo cubo, o nunca podrá encontrarlo. (Piense que la ropa amarilla se coloca en el fondo de una canasta roja) Esta asignación de un elemento a su “cubo” se llama función hash.
Buenas funciones hash
Otra cosa a tener en cuenta sobre las funciones hash. Desearía una buena función hash al realizar el hash. Toma un diccionario. Pocas palabras comienzan con “Z”, por lo que es muy fácil encontrar una palabra en su diccionario “hash” que comience con una “Z”. Sin embargo, ¿qué pasa con algo que comienza con “A”, recuerde que el hash no ordena las palabras en orden lexicográfico. Esto significa que necesitaría buscar en toda la sección “A” solo para encontrar la palabra que está buscando.
Una buena función hash intenta asignar diferentes elementos a diferentes cubos con la misma probabilidad. Para que el tiempo de búsqueda promedio de cualquier elemento sea más o menos el mismo. Por ejemplo, si tiene 18 prendas amarillas, 1 azul y 1 verde, entonces no tiene mucho sentido tirar todas las prendas amarillas en 1 cubo. Sin embargo, si hay, por ejemplo, 7 piezas de ropa formal, 7 piezas de ropa casual y 6 piezas de ropa deportiva. Entonces eso haría una distribución mucho más equitativa de los elementos para acelerar la búsqueda.
(Cuantos más cubos use la función hash, más rápido será el tiempo de búsqueda)
