El sondeo cuadrático es un esquema de direccionamiento abierto en programación informática para resolver colisiones hash en tablas hash . El sondeo cuadrático opera tomando el índice hash original y agregando valores sucesivos de un polinomio cuadrático arbitrario hasta que se encuentra una ranura abierta.
Una secuencia de ejemplo que utiliza el sondeo cuadrático es:
El sondeo cuadrático puede ser un algoritmo más eficiente en una tabla de direccionamiento abierta , ya que evita mejor el problema de agrupamiento que puede ocurrir con el sondeo lineal , aunque no es inmune. También proporciona un buen almacenamiento en caché de memoria porque conserva alguna localidad de referencia ; sin embargo, el sondeo lineal tiene una mayor localidad y, por tanto, un mejor rendimiento de la caché. [ dudoso ] [ cita requerida ]
Función cuadrática
Sea h ( k ) una función hash que mapea un elemento k a un número entero en [0, m −1], donde m es el tamaño de la tabla. Sea la i- ésima posición de la sonda para un valor k sea dada por la función
donde c 2 ≠ 0 (Si c 2 = 0, entonces h ( k , i ) se degrada a una sonda lineal ). Para una tabla hash dada , los valores de c 1 y c 2 permanecen constantes.
Ejemplos:
- Si , entonces la secuencia de la sonda será
- Para m = 2 n , una buena elección para las constantes son c 1 = c 2 = 1/2, ya que los valores de h ( k , i ) para i en [0, m −1] son todos distintos. Esto conduce a una secuencia de sonda de(los números triangulares ) donde los valores aumentan en 1, 2, 3, ...
- Para primos m > 2, la mayoría de las opciones de c 1 y c 2 harán que h ( k , i ) sea distinta para i en [0, ( m −1) / 2]. Estas opciones incluyen c 1 = c 2 = 1/2, c 1 = c 2 = 1 y c 1 = 0, c 2 = 1. Sin embargo, solo hay m / 2 sondas distintas para un elemento dado, lo que requiere otras técnicas. para garantizar que las inserciones se realizarán correctamente cuando el factor de carga sea superior a 1/2.
- Para , Donde m , n , y p son mayores número entero o igual a 2 (degrada a sonda lineal cuando p = 1), entoncesda el ciclo de todas las sondas distintas. Se puede calcular en bucle como:, y
- Para cualquier m , se puede lograr un ciclo completo con sondeo cuadrático redondeando hacia arriba m a la potencia más cercana de 2, calcular el índice de la sonda:y omitir la iteración cuando . Hay maximoiteraciones omitidas, y estas iteraciones no se refieren a la memoria, por lo que es una operación rápida en la mayoría de los procesadores modernos. El redondeo de m se puede calcular mediante:
uint64_t roundUp2 ( uint64_t v ) { v - ; v | = v >> 1 ; v | = v >> 2 ; v | = v >> 4 ; v | = v >> 8 ; v | = v >> 16 ; v | = v >> 32 ; v ++ ; return v ; }
Limitaciones
Sin embargo, cuando se usa el sondeo cuadrático (con la excepción de los casos de números triangulares para una tabla hash de tamaño), [1] no hay garantía de encontrar una celda vacía una vez que la tabla se llena más de la mitad, o incluso antes si el tamaño de la tabla es compuesto , [2] porque las colisiones deben resolverse usando la mitad de la tabla como máximo.
Lo inverso de esto se puede probar como tal: supongamos que una tabla hash tiene un tamaño (un primo mayor que 3), con una ubicación inicial y dos ubicaciones alternativas y (dónde y ). Si estas dos ubicaciones apuntan al mismo espacio clave, pero, luego
- .
Como es un número primo, ya sea o debe ser divisible por . Desde y son diferentes (modulo ), , y dado que ambas variables son mayores que cero, . Así, por contradicción, la primera ubicaciones alternativas después debe ser único y, posteriormente, siempre se puede encontrar un espacio vacío siempre que como máximo las ubicaciones están llenas (es decir, la tabla hash no está llena a más de la mitad).
Signos alternos
Si se alterna el signo del desplazamiento (por ejemplo, +1, -4, +9, -16, etc.), y si el número de cubos es un número primo congruente con 3 módulo 4 (por ejemplo, 3, 7, 11, 19, 23, 31, etc.), entonces el primer las compensaciones serán únicas (módulo ). [ se necesita más explicación ] En otras palabras, una permutación de 0 a se obtiene y, en consecuencia, siempre se encontrará un balde libre mientras exista al menos uno.
Referencias
- ^ Hopgood, F. Robert A .; Davenport, James H. (noviembre de 1972). "El método hash cuadrático cuando el tamaño de la tabla es una potencia de 2" . Revista informática . 15 (4): 314–5. doi : 10.1093 / comjnl / 15.4.314 . Consultado el 7 de febrero de 2020 .
- ^ Weiss, Mark Allen (2009). "§5.4.2 Sondeo cuadrático". Estructuras de datos y análisis de algoritmos en C ++ . Educación Pearson. ISBN 978-81-317-1474-4.