El paso de la exploración lineal a cuadrática con palpador (colisiones hash)

Question

Mi implementación actual de una tabla hash está utilizando el sondeo lineal y ahora quiere moverse a cuadrática con palpador (y más tarde a encadenar y tal vez la doble dispersión también). He leído artículos pocos, tutoriales, Wikipedia, etc ... Pero todavía no sé exactamente lo que debía hacer.

sondeo lineal, básicamente, tiene un paso de 1 y que es fácil de hacer. Durante la búsqueda, insertar o quitar un elemento de la tabla hash, que necesito para calcular un hash y por eso hago esto:

index = hash_function(key) % table_size;

A continuación, durante la búsqueda, insertar o extraer bucle I a través de la mesa hasta que encuentre un cubo libre, como esto:

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + 1) % table_size;
    }
while(/* LOOP UNTIL IT'S NECESSARY */);

En cuanto a cuadrática de sondeo, creo que lo que tengo que hacer es cambiar la forma de calcular el tamaño "índice" paso, pero eso es lo que no entiendo cómo debería hacerlo. He visto varias piezas de código, y todos ellos son algo diferentes.

Además, he visto algunas implementaciones de sondaje cuadrática, donde se cambia la función hash para acomodada que (pero no todos ellos). Es que el cambio realmente necesario o puedo evitar modificar la función hash y seguir utilizando cuadrática Sondeo?

EDIT: Después de leer todo lo señalado por Eli Bendersky debajo Creo que tengo la idea general. Aquí es parte del código en http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx :

15   for ( step = 1; table->table[h] != EMPTY; step++ ) {
16     if ( compare ( key, table->table[h] ) == 0 )
17       return 1;
18 
19     /* Move forward by quadratically, wrap if necessary */
20     h = ( h + ( step * step - step ) / 2 ) % table->size;
21   }

Hay 2 cosas que no consigo ... Dicen que el sondeo cuadrática se hace generalmente usando c(i)=i^2. Sin embargo, en el código anterior, que está haciendo algo más parecido a c(i)=(i^2-i)/2

Yo estaba listo para implementar esto en mi código, pero yo simplemente hacer:

index = (index + (index^index)) % table_size;

... y no:

index = (index + (index^index - index)/2) % table_size;

En todo caso, lo haría:

index = (index + (index^index)/2) % table_size;

... porque yo he visto otros ejemplos de código de buceo por dos. Aunque no entiendo por qué ...

1) ¿Por qué es restar el paso?
2) ¿Por qué es el buceo por 2?

Answer 1

Usted no tiene que modificar la función hash para sondear cuadrática. La forma más simple de sondeo cuadrática es realmente sólo agregando consiguientes cuadrados para la posición calculada en lugar de lineal 1, 2, 3.

Hay un buen recurso aquí . La siguiente es tomado de allí. Esta es la forma más simple de sondeo cuadrática cuando se utiliza el sencillo c(i) = i^2 polinomio:

En el caso más general, la fórmula es:

Y usted puede escoger sus constantes.

Mantener, en la mente, sin embargo, que cuadrática de palpación es útil sólo en ciertos casos. Como afirma la entrada Wikipedia :

  

cuadrática de sondeo proporciona buena memoria   el almacenamiento en caché, ya que preserva cierta   localidad de referencia; sin embargo, lineal   sondeo tiene mayor localidad y,   por lo tanto, un mejor rendimiento de la caché.   Cuadrática de sondeo evita la mejor   problema de agrupamiento que puede ocurrir con   sondeo lineal, aunque no es   inmunológico.

---

EDIT: Como muchas cosas en la informática, las constantes exactas y polinomios de segundo grado de sondeo son heurístico. Sí, la forma más simple es i^2, pero puede elegir cualquier otro polinomio. Wikipedia da el ejemplo con h(k,i) = (h(k) + i + i^2)(mod m).

Por lo tanto, es difícil responder a su "por qué". La única "por qué" aquí es ¿Por qué necesita cuadrática de sondeo en absoluto? Tener problemas con otras formas de sondeo y para conseguir una mesa en clúster? O es sólo una tarea, o auto-aprendizaje?

Tenga en cuenta que, con mucho, la técnica de resolución de colisiones más común para las tablas hash es bien encadenando o sondeo lineal. Cuadrática de sondeo es una opción de heurística disponible para casos especiales, ya menos que sepas lo que estás haciendo muy bien, yo no recomendaría el uso de la misma.

Answer 2

Hay una manera particularmente simple y elegante para implementar cuadrática sondear si el tamaño de la tabla es una potencia de 2:

step = 1;

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + step) % table_size;
        step++;
    }
} while(/* LOOP UNTIL IT'S NECESSARY */);

En vez de mirar las compensaciones de 0, 1, 2, 3, 4 ... desde el índice original, esto se verá en las compensaciones de 0, 1, 3, 6, 10 ... (la i ^º sonda está en el offset (i * (i + 1)) / 2, es decir, que es cuadrática).

Esto está garantizado para golpear todas las posiciones en la tabla hash (por lo que está garantizado para encontrar un cubo vacío si lo hay) siempre el tamaño de la tabla es una potencia de 2.

---

Aquí es un boceto de una prueba:

1. Dado un tamaño de la tabla de n, queremos mostrar que vamos a obtener los valores distintos de n (i * (i + 1)) / 2 (mod n) con i = 0 ... n-1.
2. Se puede probar esto por contradicción. Supongamos que hay menos de n valores distintos: si es así, debe haber al menos dos valores enteros distintas para i en el rango [0, n-1] tal que (i * (i + 1)) / 2 (n mod ) es el mismo. Llame a estos p y q, donde p
3. es decir. (P * (p + 1)) / 2 = (q * (q + 1)) / 2 (mod n)
4. => (p ² + p) / 2 = (q ² + q) / 2 (mod n)
5. => p ² + p = q ² + q (mod 2n)
6. => q ² - p ² + q - p = 0 (2n mod)
7. factorizar => (q - p) (p + q + 1) = 0 (2n mod)
8. (q - p) = 0 es el caso trivial p = q
.
9. (p + q + 1) = 0 (2n mod) es imposible: nuestros valores de p y q están en el intervalo [0, n-1], y q> p, por lo que (p + q + 1) debe estar en el intervalo [2, 2n-2].
10. Como estamos trabajando 2N módulo, también tenemos que lidiar con el caso complicado, donde ambos factores no son cero, pero se multiplican para dar 0 (mod 2n):
    • Observe que la diferencia entre los dos factores (q - p) y (p + q + 1) es (2p + 1), que es un número impar - por lo que uno de los factores debe ser par, y el otro debe ser impar.
    • (q - p) (p + q + 1) = 0 (2n mod) => (q - p) (p + q + 1) es divisible por 2n. Si n (y por tanto 2n) es una potencia de 2 , esto requiere el factor incluso a ser un múltiplo de 2n (porque todos los factores primos de 2n son 2, mientras que ninguno de los factores primos de nuestro factor impares son).
    • Pero (q - p) tiene un valor máximo de n-1, y (p + q + 1) tiene un valor máximo de 2n-2 (como se ve en el paso 9), por lo que tampoco puede ser un múltiplo de 2n .
    • Así que este caso es imposible también.
11. Por lo tanto la hipótesis de que hay menos de n valores distintos (en el paso 2) debe ser falsa.

(Si el tamaño de la tabla es no una potencia de 2, esto se desmorona en el paso 10).