El sondeo cuadrático es un esquema de direccionamiento abierto en programación informática para resolver colisiones de hash en tablas hash . El sondeo cuadrático funciona tomando el índice hash original y sumando valores sucesivos de un polinomio cuadrático arbitrario hasta que se encuentra una ranura abierta.
Un ejemplo de secuencia que utiliza sondeo cuadrático es:
![{\displaystyle H+1^{2},H+2^{2},H+3^{2},H+4^{2},...,H+k^{2}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
El sondeo cuadrático se recomienda a menudo como una alternativa al sondeo lineal porque implica menos agrupamiento . [1] El sondeo cuadrático muestra una mejor localidad de referencia que muchas otras tablas hash como el encadenamiento ; sin embargo, para las consultas, el sondeo cuadrático no tiene una localidad tan buena como el sondeo lineal , lo que hace que este último sea más rápido en algunas configuraciones. [2]
El sondeo cuadrático fue introducido por primera vez por Ward Douglas Maurer en 1968. [3]
Función cuadrática
Sea h ( k ) una función hash que asigna un elemento k a un 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 dada por la función
![{\displaystyle h(k,i)=h(k)+c_{1}i+c_{2}i^{2}{\pmod {m}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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á
![{\displaystyle h(k,i)=(h(k)+i+i^{2}){\pmod {m}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle h(k),h(k)+2,h(k)+6,...}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Para m = 2 n , una buena elección para las constantes es c 1 = c 2 = 1/2, ya que los valores de h ( k , i ) para i en [0, m −1] son todos distintos (de hecho, es una permutación en [0, m −1] [4] ). Esto conduce a una secuencia de prueba de (los números triangulares ) donde los valores aumentan en 1, 2, 3, ...
![{\displaystyle h(k),h(k)+1,h(k)+3,h(k)+6,...}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Para el primo m > 2, la mayoría de las opciones de c 1 y c 2 harán que h ( k , i ) sea distinto para i en [0, ( m −1)/2]. Dichas 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 tengan éxito cuando el factor de carga exceda 1/2.
- Para , donde m , n y p son enteros mayores o iguales a 2 (se degrada a sonda lineal cuando p = 1), entonces da un ciclo de todas las sondas distintas. Se puede calcular en bucle como: , y
![{\displaystyle m=n^{p}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle h(k,i)=(h(k)+i+ni^{2}){\pmod {m}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle h(k,0)=h(k)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle h(k,i+1)=(h(k,i)+2in+n+1){\pmod {m}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Para cualquier m , se puede lograr un ciclo completo con sondeo cuadrático redondeando m a la potencia de 2 más cercana, calculando el índice de sondeo: y salteando la iteración cuando . Hay un máximo de iteraciones salteadas, y estas iteraciones no hacen referencia 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:
![{\displaystyle h(k,i)=h(k)+((i^{2}+i)/2){\pmod {roundUp2(m)}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle h(k,i)>=m}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle redondear2(m)-m<m/2}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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 ++ ; volver v ; }
Limitaciones
Signos alternados
Si el signo del desplazamiento se alterna (p. ej. +1, −4, +9, −16, etc.), y si el número de cubos es un número primo congruente con 3 módulo 4 (p. ej. 3, 7, 11, 19, 23, 31, etc.), entonces los primeros desplazamientos serán únicos (módulo ). [ se necesita más explicación ] En otras palabras, se obtiene una permutación de 0 a , y, en consecuencia, siempre se encontrará un cubo libre mientras exista al menos uno.![{\estilo de visualización p}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización p}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización p}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\estilo de visualización p-1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Referencias
- ^ Cormen, Thomas H.; Leiserson, Charles Eric; Rivest, Ronald Linn; Stein, Clifford (2009). Introducción a los algoritmos (3.ª ed.). Cambridge, Massachusetts Londres, Inglaterra: MIT Press. ISBN 978-0-262-53305-8.
- ^ Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015). "Un análisis de siete dimensiones de los métodos de hash y sus implicaciones en el procesamiento de consultas". Actas de la Fundación VLDB . 9 (3): 96–107. doi :10.14778/2850583.2850585. ISSN 2150-8097.
- ^ Maurer, WD (1968). "Técnica de programación: un código hash mejorado para almacenamiento disperso". Comunicaciones de la ACM . 11 (1): 35–38. doi : 10.1145/362851.362880 . ISSN 0001-0782.
- ^ El arte de la informática Volumen 3 Ordenación y búsqueda, Capítulo 6.4, ejercicio 20, Donald Knuth
Enlaces externos
- Tutorial/sonda cuadrática