ventajas tablas tabla resolucion las implementacion funcion ejemplos dispersion desventajas colisiones aplicaciones algorithm hash primes

algorithm - resolucion - tablas hash en java



¿Por qué el tamaño 127(principal) es mejor que 128 para una tabla hash? (9)

Suponiendo un hash simple y uniforme, ese ser, cualquier valor dado es igual al hash en cualquiera de las ranuras del hash. ¿Por qué es mejor usar una tabla de tamaño 127 y no de 128? Realmente no entiendo cuál es el problema con el poder de 2 números. O cómo realmente hace alguna diferencia en absoluto.

Al usar el método de división, generalmente evitamos ciertos valores de m (tamaño de la tabla). Por ejemplo, m no debería ser una potencia de 2, ya que si m = 2 ^ p, entonces h (k) es simplemente el p de bits de orden más bajo de k.

Supongamos que los posibles elementos están solo entre 1 y 10000 y escogí el tamaño de la tabla como 128. ¿Cómo puede 127 ser mejor? Entonces 128 es 2 ^ 6 (1000000) y 127 es 0111111. ¿Qué diferencia hace esto? Todos los números (cuando hash) seguirán siendo los p bits de orden más bajo de k para 127 también. ¿Obtuve algo mal?

Estoy buscando algunos ejemplos ya que realmente no puedo entender por qué es malo. ¡Muchas gracias por adelantado!

PD: estoy al tanto de: tabla Hash: ¿por qué el tamaño debe ser primordial?

Creo que solo tiene que ver con el hecho de que las computadoras funcionan en la base 2. Algo similar sucede con la base 10.

...

Escoger un número lo suficientemente grande que no sea potencia de dos asegurará que la función hash realmente sea una función de todos los bits de entrada, en lugar de un subconjunto de ellos.

De Why hash tables debería usar un tamaño de número primo .

Todos los números (cuando hash) seguirán siendo los p bits de orden más bajo de k para 127 también.

Eso está mal (o lo malentendí ...). k % 127 depende de todos los bits de k. k % 128 solo depende de los 7 bits más bajos.

EDITAR:

Si tienes una distribución perfecta entre 1 y 10,000. 10,000 % 127 y 10,000 % 128 ambos convertirán esto en una excelente distribución más pequeña. Todos los cubos contendrán 10,000 / 128 = 78 (o 79) elementos.

Si tiene una distribución entre 1 y 10,000 que está sesgada, porque {x, 2x, 3x, ..} ocurren más a menudo. Entonces, un tamaño principal dará una distribución mucho, mucho mejor, como se explica en esta answer . (A menos que x sea exactamente ese tamaño principal).

Por lo tanto, cortar los bits altos (usando un tamaño de 128) no es un problema en absoluto si la distribución en los bits inferiores es lo suficientemente buena. Pero, con datos reales y funciones hash realmente mal diseñadas, necesitarás esos bits altos.

Método de división

"Cuando usamos el método de división, usualmente evitamos ciertos valores de m (tamaño de la tabla). Por ejemplo, m no debe ser una potencia de 2 , ya que si m = 2 p , entonces h(k) es solo el orden p más bajo bits de k ".

--CLRS

Para entender por qué m = 2 p usa solo los p bits más bajos de k , primero debe comprender la función hash del módulo h(k) = k % m .

La clave se puede escribir en términos de un cociente q y el resto r .

k = nq + r

Elegir que el cociente sea q = m nos permite escribir k % m simplemente como el resto en la ecuación anterior:

k % m = r = k - nm, where r < m

Por lo tanto, k % m es equivalente a restar continuamente m un total de n veces (hasta r < m ):

k % m = k - m - m - ... - m, until r < m

Intentemos mezclar la clave k = 91 con m = 2 4 = 16 .

91 = 0101 1011 - 16 = 0001 0000 ---------------- 75 = 0100 1011 - 16 = 0001 0000 ---------------- 59 = 0011 1011 - 16 = 0001 0000 ---------------- 43 = 0010 1011 - 16 = 0001 0000 ---------------- 27 = 0001 1011 - 16 = 0001 0000 ---------------- 11 = 0000 1011

Por lo tanto, 91 % 2 4 = 11 es solo la forma binaria de 91 con solo el p=4 bits más bajos restantes.

Distinción importante:

Esto se refiere específicamente al método de división de hash. De hecho, lo contrario es cierto para el método de multiplicación como se establece en CLRS:

"Una ventaja del método de multiplicación es que el valor de m no es crítico ... Por lo general, elegimos [m] como una potencia de 2 ya que podemos implementar fácilmente la función en la mayoría de las computadoras".

En primer lugar, no se trata de elegir un número primo. Para su ejemplo, si sabe que su conjunto de datos estará en el rango de 1 a 10,000, escoger 127 o 128 no hará la diferencia porque es una opción de diseño pobre.

Por el contrario, es mejor elegir un primo REALMENTE grande como 3967 para su ejemplo, de modo que cada dato tenga su propio par clave / valor único. Solo quieres minimizar las colisiones. Elegir 127 o 128 para su ejemplo no hará una diferencia porque todos los 127/128 depósitos se llenarán de manera uniforme (esto es malo y degradará la inserción y el tiempo de búsqueda de búsqueda O (1) a O (n)) en comparación con 3967 (que conservará los tiempos de ejecución O (1))

EDIT # 4

El diseño de la "función hash" es algo así como un arte negro. Puede estar muy influenciado por los datos que están destinados a almacenarse en la estructura de datos basada en hashes, por lo que la discusión sobre una función de hash sensible a menudo puede desviarse hacia una discusión sobre entradas específicas.

Como por qué los números primos son "preferidos", uno tiene que considerar un análisis de "adversario", es decir, si diseñé una estructura de datos basada en hash general, ¿cómo funcionaría dado el peor aporte de un adversario? Dado que la ejecución está dictada por colisiones hash, la pregunta es qué hash usar para minimizar la colisión en las peores condiciones. Una de esas condiciones es cuando la entrada es siempre divisible por un número entero, digamos 4. Si usa N = 128, cualquier número divisible por 4 mod 128 aún es divisible por 4, lo que significa solo cubos 4, 8, 12, ... . siempre se usan, lo que resulta en una utilización del 25% de la estructura de datos. Primes efectivamente reduce la probabilidad de que ocurra tal escenario, con números> N.

Nick tiene razón en que, en general, el tamaño de la tabla hash no importa. Sin embargo, en el caso especial donde se utiliza el direccionamiento abierto con doble hash (en el que el intervalo entre sondeos se calcula mediante otra función hash), una tabla hash de tamaño principal es la mejor para asegurar que todas las entradas de tabla hash estén disponibles para un nuevo elemento (como Corkscreewe mencionado)

No puedo demostrarlo más, aunque recuerdo haber tenido que hacerlo en un examen en la universidad hace un millón de años, pero los tamaños de hash óptimos no son simplemente primos. Desea elegir un número primo N tal que N = 4*M − 1 (donde M también es un número entero).

Eso hace que 31 sea un número de cubos mayor que 29. M es 8 cuando N es 31, pero no hay M integral cuando N es 29.

Como dije, ya no recuerdo las matemáticas para probar esto. Fue en un curso teórico impartido por Rachel Manber, la esposa de Udi, hace unos 25 años más o menos.

Si tienes una función hash perfecta que tiene una distribución pareja, entonces no importa.

aquí hay una manera de entender "k% 127 depende de todos los bits de k. k% 128 solo depende de los 7 bits más bajos". .
k% 128 es igual a k & (2 ^ 7-1). Por ejemplo: 129% 128 = 1, en Binario: 1000 0001 y 0111 1111 = 0000 0001, cualquier punto alto de (2 ^ 7-1) será 0, lo que significa que la dosis no importa cuál es la posición más alta. pero este traductor no es válido para números que no son iguales a 2 ^ n.
ahora echemos un vistazo a cómo hacemos la división en Decimal 129% 127, primero observemos la posición más alta 1, menos de 127, luego obtenemos el siguiente ítem 2 combinándolo con el puño obtenemos 12, 12 es menos de 127, luego combinamos con 9, lo que significa 129, dividido por 127, el resto es 2, podríamos escribir esto en matemáticas: 129 = 1 * 127 +2, así que tenemos 2 [todo esto se llama Long_division] , y es lo mismo en la división binaria, ahora, sabemos que k% 127 depende de todos los bits de k