Descargo de responsabilidad: Sé que hay preguntas similares que suenan aquí y en Stackoverflow. Pero se trata de colisiones, que no es lo que estoy pidiendo.
Mi pregunta es: ¿por qué la búsqueda sin colisiones O(1)
en primer lugar?
Supongamos que tengo esta tabla hash:
Hash Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6
Ahora estoy buscando la clave k
donde h(k)
da la función hash h(k) = mkwer
. Pero, ¿cómo "sabe" la búsqueda que el hash mkwer
está en la posición 5? ¿Por qué no tiene que desplazarse por todas las teclas O(n)
para encontrarlo? Los hashes no pueden ser algún tipo de dirección de hardware real porque perdería la capacidad de mover los datos. Y hasta donde yo sé, la tabla hash no está ordenada en los hashes (incluso si lo fuera, la búsqueda también tomaría O(log n)
).
¿De qué manera conocer un hash ayuda a encontrar el lugar correcto en la tabla?
La función hash calcula la posición de la matriz a partir de una cadena dada . Si este es el hash perfecto, significa que seguramente no hay colisiones, lo más probable es que la matriz sea al menos dos veces mayor que el número de elementos.
Por ejemplo, daré un hash muy pobre para las letras, solo para ilustrar el mecanismo:x=0;
x=xmod52
0) 1) para cada carácter de la cadena tome el valor ascii, reste 'a' si está en minúscula, reste 'A' si está en mayúscula, agregue valor a x. 2) el número resultante, por ejemplo, 15 es el índice de la matriz. x = x m o d 52
Este hash muy simple (limitado y propenso a colisiones) difiere de otros hashes en el mecanismo de hash, no considera la entrada dada. En un esquema más avanzado, el hash es un número mayor, ajustado al número de elementos. Se genera un hash perfecto para todas las entradas para garantizar que no haya colisiones.
Esto es porque calcular el hash a partir de una cadena depende de cuán sofisticada se calcule la función, pero no depende del número de elementos.O(1)
En caso de hash perfecto, cuando se agregan elementos se recalcula, el caso más simple con colisiones cuando la carga de la matriz es grande, el tamaño de la matriz aumenta, la función toma un módulo de salida más grande y los elementos se desplazan a los nuevos lugares.h(k)
La matriz es un fragmento de memoria continuo, para obtener elemento, toma la dirección del primer elemento (inicio de la matriz) y luego agrega a esta dirección para que tenga una celda de memoria explícita.n ∗ ( s i z e o f e l e m e n t )n−th n∗(sizeofelement)
fuente
Para ampliar la respuesta de David Richerby, el término " función hash " está un poco sobrecargado. A menudo, cuando hablamos de una función hash, pensamos en MD5, SHA-1 o algo así como el
.hashCode()
método de Java , que convierte alguna entrada en un solo número. Sin embargo, es muy poco probable que el dominio de este número (es decir, el valor máximo) tenga el mismo tamaño que la tabla hash en la que está tratando de almacenar datos. (MD5 tiene 16 bytes, SHA-1 tiene 20 bytes y.hashCode()
es unint
- 4 bytes).Entonces, su pregunta es sobre el siguiente paso: una vez que tenemos una función hash que puede asignar entradas arbitrarias a números, ¿cómo los colocamos en una estructura de datos de un tamaño particular? ¡Con otra función, también llamada "función hash"!
Un ejemplo trivial de tal función es el módulo ; puede asignar fácilmente un número de tamaño arbitrario a un índice específico en una matriz con módulo. Esto se introduce en CLRS como "el método de división":
Por lo tanto, el módulo no es una gran función hash, ya que restringe los tamaños que podemos usar de manera segura para nuestra estructura de datos subyacente. La siguiente sección presenta un "método de multiplicación" un poco más complejo, que también utiliza módulo pero es ventajoso porque "el valor de no es crítico". Sin embargo, funciona mejor con algunos conocimientos previos de "características de los datos que se están procesando", algo que a menudo no conocemos.m
Java
HashMap
utiliza una versión modificada del método de división que realiza un paso de preprocesamiento para tener en cuenta las.hashCode()
implementaciones débiles para que pueda utilizar matrices de dos tamaños. Puedes ver exactamente lo que está sucediendo en el.getEntry()
método (los comentarios son míos):Java 8 trajo consigo una reescritura de la
HashMap
cual es aún más rápida, pero un poco más difícil de leer. Sin embargo, utiliza el mismo principio general para la búsqueda de índice.fuente