Sondeo cuadrático

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}}$

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}}}$

donde c ₂ ≠ 0 (Si c ₂ = 0, entonces h ( k , i ) se degrada a una sonda lineal ). Para una tabla hash dada , los valores de c ₁ y c ₂ permanecen constantes.

Ejemplos:

• Si , entonces la secuencia de la sonda será ${\displaystyle h(k,i)=(h(k)+i+i^{2}){\pmod {m}}}$ ${\displaystyle h(k),h(k)+2,h(k)+6,...}$
• Para m = 2 ⁿ , una buena elección para las constantes es c ₁ = c ₂ = 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,...}$
• Para el primo m > 2, la mayoría de las opciones de c ₁ y c ₂ harán que h ( k , i ) sea distinto para i en [0, ( m −1)/2]. Dichas opciones incluyen c ₁ = c ₂ = 1/2, c ₁ = c ₂ = 1 y c ₁ = 0, c ₂ = 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}}$ ${\displaystyle h(k,i)=(h(k)+i+ni^{2}){\pmod {m}}}$ ${\displaystyle h(k,0)=h(k)}$ ${\displaystyle h(k,i+1)=(h(k,i)+2in+n+1){\pmod {m}}}$
• 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)}}}$ ${\displaystyle h(k,i)>=m}$ ${\displaystyle roundUp2(m)-m<m/2}$

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. ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p-1}$

Referencias

1. 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.
2. 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.
3. 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.
4. 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