En programación de computadoras , la agrupación primaria es uno de los dos modos de falla principales de las tablas hash basadas en direccionamiento abierto , especialmente aquellas que usan sondeo lineal . Ocurre después de que una colisión hash hace que dos de los registros de la tabla hash se muevan a la misma posición y hace que uno de los registros se mueva a la siguiente ubicación en su secuencia de sondeo. Una vez que esto sucede, es más probable que el clúster formado por este par de registros crezca mediante la adición de aún más registros en colisión, independientemente de si los nuevos registros tienen la misma ubicación que los dos primeros. Este fenómeno hace que las búsquedas de claves dentro del clúster sean más largas. [1]
Por ejemplo, en el sondeo lineal , un registro involucrado en una colisión siempre se mueve a la siguiente celda disponible de la tabla hash posterior a la posición dada por su función hash, creando un grupo contiguo de celdas ocupadas de la tabla hash. Siempre que se aplica un hash a otro registro en cualquier lugar dentro del clúster, su tamaño aumenta en una celda. Debido a este fenómeno, es probable que una tabla hash de sondeo lineal con un factor de carga constante (es decir, con el tamaño de la tabla proporcional al número de elementos que almacena) tenga algunos grupos de longitud logarítmica y tomará tiempo logarítmico para buscar las claves dentro de ese grupo. [2]
Un fenómeno relacionado, la agrupación secundaria , ocurre de manera más general con los modos de direccionamiento abiertos que incluyen el sondeo lineal y el sondeo cuadrático en los que la secuencia de la sonda es independiente de la clave, así como en el encadenamiento hash. En este fenómeno, una función de hash de baja calidad puede hacer que muchas claves se transfieran a la misma ubicación, después de lo cual todas siguen la misma secuencia de sondeo o se colocan en la misma cadena de hash, lo que hace que tengan tiempos de acceso lentos. [1]
Ambos tipos de agrupación en clústeres se pueden reducir mediante el uso de una función hash de mayor calidad o mediante un método de hash, como el doble hash, que es menos susceptible a la agrupación. [1]