¿Por qué una búsqueda de tabla hash (sin colisión) es realmente O (1)?

10

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 kdonde h(k)da la función hash h(k) = mkwer. Pero, ¿cómo "sabe" la búsqueda que el hash mkwerestá 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?

Foo Bar
fuente

Respuestas:

24

La función hash no devuelve alguna cadena como mkwer. Devuelve directamente la posición del elemento en la matriz. Si, por ejemplo, su tabla hash tiene diez entradas, la función hash devolverá un número entero en el rango 0–9.

David Richerby
fuente
1
Gracias. :) Mi error fue pensar en una función hash de tabla hash como MD5 o SHA. Pero un hash, por supuesto, puede ser una posición entera, en la que no pensé. Ahora que sé qué buscar, incluso encontré rápidamente un buen ejemplo: la función hash de PHP: github.com/php/php-src/blob/PHP-5.6.10/Zend/zend_hash.h#L237
Foo Bar
13
@FooBar: MD5 y SHA también calculan números individuales a partir de la entrada, es muy común hablar de los hashes en forma hexadecimal. Al igual que las direcciones de memoria, rara vez se consideran en decimal.
nperson325681
44
Además, MD5, etc., son demasiado largos para usarse directamente como índice de matriz. Sería posible usar alguna parte del hash, como los n bits más bajos .
chirlu
6

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:
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 52x=0;
x=xmod52

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 )nthn(sizeofelement)

Mal
fuente
1
¿Y cómo saben las operaciones de búsqueda en la tabla es el hash? No es ni ordenado ni direcciones de hardware.
Foo Bar
Le da una cadena, por ejemplo, "xcnvb", por lo que el hash calculado da el índice de la matriz, "xcnvb" es su elemento para buscar, 8 es el índice en la tabla. Se ordena con la cabeza, el hash devuelve el lugar al elemento retreive. Este elemento fue puesto allí por la misma función. El hardware no tiene nada que hacer aquí. Proporciona matriz, función hash y calcula hash para obtener el índice en la matriz, lo mismo en retreival. La matriz no está ordenada, tampoco está llena. h("xcnvb")=8
Mal
Pero no se completarán todos los índices. Si tengo los hash 1, 4, 8, 90 y 223 llenos de datos, ¿cómo encuentra una búsqueda el lugar correcto? En este caso, el índice "90" está en la posición 4 porque la mayoría de los otros índices no existen. ¿Y una tabla hash vacía no es de tamaño infinito con todas las posiciones posibles?
Foo Bar
Sí, la matriz nos permite asumir 512 elementos de largo, 9 bits utilizados para la función hash, y solo tiene 4 elementos. El índice 90 tiene la posición 90 en la matriz, como en el ejemplo: casi todas las celdas están vacías. Si su matriz es , la indexa = sus datos para "xcnvb"HaHa(h("xcnvb"))=Ha[90]
Mal
La función hash no devuelve un índice en la matriz. En cambio, devuelve un número predecible que se puede asignar a la matriz. Esto generalmente se hace usando el operador de módulo con el número de cubos de la tabla hash como el otro operando.
Christopher Schultz
3

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 un int- 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":

En el método de división para crear funciones hash, asignamos una clave en una de las ranuras al tomar el resto de dividido por . Es decir, la función hash eskmkm

h(k)=k mod .m

...

Cuando usamos el método de división, generalmente evitamos ciertos valores de . Por ejemplo, no debería ser una potencia de 2, ya que si entonces es solo los bits de orden más bajo de .mmm=2ph(k)pk

~ Introducción a los algoritmos, §11.3.1 - CLRS

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 HashMaputiliza 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):

 // hash() transforms key.hashCode() to protect against bad hash functions
 int hash = (key == null) ? 0 : hash(key.hashCode());
 // indexOf() converts the resulting hash to a value between 0 and table.length-1
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
     ...

Java 8 trajo consigo una reescritura de la HashMapcual 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.

dimo414
fuente