Agrupamiento primario

En programación informática , el agrupamiento primario es un fenómeno que causa degradación del rendimiento en tablas hash de sondeo lineal . El fenómeno establece que, a medida que se agregan elementos a una tabla hash de sondeo lineal, estos tienden a agruparse en secuencias largas (es decir, regiones largas y contiguas de la tabla hash que no contienen espacios libres). Si la tabla hash tiene un factor de carga de${\displaystyle 1-1/x}$para algún parámetro${\displaystyle x\geq 2}$, entonces la longitud esperada de la secuencia que contiene un elemento dado${\displaystyle u}$es${\displaystyle \Theta (x^{2})}$Esto provoca que las inserciones y las consultas negativas tarden el tiempo esperado.${\displaystyle \Theta (x^{2})}$en una tabla hash de sondeo lineal.

La agrupación primaria tiene dos causas:

• El ganador sigue ganando: cuanto más larga sea una racha, mayor será la probabilidad de que acumule elementos adicionales. Esto genera un ciclo de retroalimentación positiva que contribuye al efecto de agrupamiento. Sin embargo, esto por sí solo no causaría la explosión cuadrática. ^{[ 1 ] [ 2 ]}
• Unión de secuencias: Una sola inserción no solo puede aumentar la longitud de la secuencia en la que se encuentra en una unidad, sino que también puede conectar dos secuencias que ya eran relativamente largas. Esto es lo que provoca el crecimiento cuadrático en la longitud esperada de la secuencia. ^{[ 1 ]}

Otra forma de entender la agrupación primaria es examinando la desviación estándar del número de elementos que se asignan a una región determinada dentro de la tabla hash. ^{[ 2 ]} Consideremos una subregión de la tabla hash de tamaño${\displaystyle x^{2}}$. El número esperado de elementos que se codifican en la región es${\displaystyle (1-1/x)x^{2}=x^{2}-x}$Por otro lado, la desviación estándar del número de dichos elementos es${\displaystyle \Theta (x)}$De ello se deduce que, con probabilidad${\displaystyle \Omega (1)}$, el número de elementos que se asignan a la región excederá el tamaño${\displaystyle x^{2}}$de la región. Intuitivamente, esto significa que regiones de tamaño${\displaystyle \Theta (x^{2})}$A menudo se producirá un desbordamiento, mientras que las regiones más grandes generalmente no lo harán. Esta intuición se utiliza a menudo como punto de partida para análisis formales de agrupamiento primario. ^{[ 2 ] [ 3 ] [ 4 ]}

La agrupación primaria provoca una degradación del rendimiento tanto para las inserciones como para las consultas en una tabla hash de sondeo lineal. Las inserciones deben llegar hasta el final de una ejecución y, por lo tanto, tardan el tiempo esperado.${\displaystyle \Theta (x^{2})}$. ^{[ 1 ]} Las consultas negativas (es decir, las consultas que buscan un elemento que resulta no estar presente) también deben llegar al final de una ejecución y, por lo tanto, también toman el tiempo esperado.${\displaystyle \Theta (x^{2})}$. ^{[ 1 ]} Las consultas positivas pueden terminar tan pronto como encuentren el elemento que están buscando. Como resultado, el tiempo esperado para consultar un elemento aleatorio en la tabla hash es${\displaystyle \Theta (x)}$. ^{[ 1 ]} Sin embargo, las consultas positivas a elementos insertados recientemente (por ejemplo, un elemento que acaba de ser insertado) tardan el tiempo esperado.${\displaystyle \Theta (x^{2})}$. ^{[ 1 ]}

Estos límites también se cumplen para el sondeo lineal con eliminaciones perezosas (es decir, usando marcadores de eliminación para las eliminaciones), siempre que la tabla hash se reconstruya (y los marcadores de eliminación se vacíen) con cierta frecuencia. Basta con realizar dicha reconstrucción al menos una vez cada${\displaystyle n/(2x)}$inserciones. ^{[ 2 ]}

Muchos libros de texto describen el efecto de que el ganador sigue ganando (en el que cuanto más larga es una racha, más probable es que acumule elementos adicionales) como la única causa de la agrupación primaria. ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]} Sin embargo, como señaló Knuth, ^{[ 1 ]} esta no es la causa principal de la agrupación primaria.

Algunos libros de texto afirman que el tiempo esperado para una consulta positiva es${\displaystyle \Theta (x)}$, ^{[ 11 ] [ 12 ]} citando típicamente a Knuth. ^{[ 1 ]} Esto es cierto para una consulta a un elemento aleatorio . Sin embargo, algunas consultas positivas pueden tener tiempos de ejecución esperados mucho mayores. Por ejemplo, si se inserta un elemento y luego se consulta inmediatamente ese elemento, la consulta tomará la misma cantidad de tiempo que la inserción, que es${\displaystyle \Theta (x^{2})}$con expectativa.

El sondeo lineal ordenado ^{[ 13 ]} (a menudo denominado hash Robin Hood ^{[ 14 ]} ) es una técnica para reducir los efectos del agrupamiento primario en las consultas. El sondeo lineal ordenado clasifica los elementos dentro de cada ejecución por su hash. Por lo tanto, una consulta puede terminar tan pronto como encuentre cualquier elemento cuyo hash sea mayor que el del elemento consultado. Esto hace que tanto las consultas positivas como las negativas tomen el tiempo esperado.${\displaystyle O(x)}$.

El hash de cementerio es una variante del sondeo lineal ordenado que elimina los efectos asintóticos del agrupamiento primario para todas las operaciones. ^{[ 2 ]} El hash de cementerio deja estratégicamente huecos dentro de las ejecuciones que las inserciones futuras pueden aprovechar. Estos huecos, que pueden considerarse como lápidas (como las creadas por las eliminaciones perezosas ), se insertan en la tabla durante las reconstrucciones semirregulares. Los huecos aceleran las inserciones que tienen lugar hasta que se produce la siguiente reconstrucción semirregular. Cada operación en una tabla hash de cementerio toma el tiempo esperado.${\displaystyle O(x)}$.

Numerosas fuentes recomiendan el uso del sondeo cuadrático como alternativa al sondeo lineal, ya que evita empíricamente los efectos de la agrupación primaria.