El hash coalescido , también llamado encadenamiento coalescido , es una estrategia de resolución de colisiones en una tabla hash que forma un híbrido de encadenamiento separado y direccionamiento abierto .
En una tabla hash de encadenamiento independiente, los elementos que se codifican en la misma dirección se colocan en una lista (o "cadena") en esa dirección. Esta técnica puede generar una gran cantidad de memoria desperdiciada porque la tabla en sí debe ser lo suficientemente grande como para mantener un factor de carga que funcione bien (normalmente el doble de la cantidad esperada de elementos) y se debe utilizar memoria adicional para todos los elementos de una cadena, excepto el primero (a menos que se utilicen encabezados de lista, en cuyo caso se debe utilizar memoria adicional para todos los elementos de una cadena).
Dada una secuencia "qrj", "aty", "qur", "dim", "ofu", "gcl", "rhv", "clq", "ecd", "qsu" de cadenas de tres caracteres de longitud generadas aleatoriamente, se generaría la siguiente tabla (utilizando el algoritmo hash One-at-a-Time de Bob Jenkins ) con una tabla de tamaño 10:
Esta estrategia es eficaz, eficiente y muy fácil de implementar. Sin embargo, a veces el uso de memoria adicional puede resultar prohibitivo y la alternativa más común, el direccionamiento abierto, tiene desventajas incómodas que reducen el rendimiento. La principal desventaja del direccionamiento abierto es la agrupación primaria y secundaria, en la que las búsquedas pueden acceder a secuencias largas de contenedores usados que contienen elementos con diferentes direcciones hash; los elementos con una dirección hash pueden, por lo tanto, alargar las búsquedas de elementos con otras direcciones hash.
Una solución a estos problemas es el hash fusionado. El hash fusionado utiliza una técnica similar al encadenamiento independiente, pero en lugar de asignar nuevos nodos para la lista enlazada, se utilizan contenedores en la tabla real. El primer contenedor vacío en la tabla en el momento de una colisión se considera el contenedor de colisión. Cuando se produce una colisión en cualquier parte de la tabla, el elemento se coloca en el contenedor de colisión y se crea un enlace entre la cadena y el contenedor de colisión. Es posible que un elemento recién insertado colisione con elementos con una dirección hash diferente, como el caso del ejemplo de la imagen cuando se inserta el elemento "clq". Se dice que la cadena para "clq" se "fusiona" con la cadena de "qrj", de ahí el nombre del algoritmo. Sin embargo, el grado de fusión es menor en comparación con la agrupación que exhibe el direccionamiento abierto. Por ejemplo, cuando se produce la fusión, la longitud de la cadena crece solo en 1, mientras que en el direccionamiento abierto, las secuencias de búsqueda de longitud arbitraria pueden combinarse.
Una optimización importante, para reducir el efecto de la coalescencia, es restringir el espacio de direcciones de la función hash a solo un subconjunto de la tabla. Por ejemplo, si la tabla tiene un tamaño M con contenedores numerados de 0 a M − 1 , podemos restringir el espacio de direcciones de modo que la función hash solo asigne direcciones a las primeras N ubicaciones en la tabla. Los M − N contenedores restantes , llamados bodega , se utilizan exclusivamente para almacenar elementos que colisionan durante la inserción. No puede ocurrir ninguna coalescencia hasta que se agote la bodega.
La elección óptima de N en relación con M depende del factor de carga (o de la plenitud) de la mesa. Un análisis cuidadoso muestra que el valor N = 0,86 × M produce un rendimiento casi óptimo para la mayoría de los factores de carga. [1] [2]
También son posibles otras variantes de inserción que han mejorado el tiempo de búsqueda. Se han desarrollado algoritmos de eliminación que preservan la aleatoriedad y, por lo tanto, el análisis del tiempo de búsqueda promedio aún se mantiene después de las eliminaciones. [1]
Inserción en C :
/* htab es la tabla hash, N es el tamaño del espacio de direcciones de la función hash y M es el tamaño de toda la tabla, incluida la bodega. Los contenedores de colisión se asignan en orden decreciente, comenzando con el contenedor M-1. */int insert ( char clave [] ) { unsigned h = hash ( clave , strlen ( clave ) ) % N ; if ( htab [ h ] == NULL ) { /* Crear una nueva cadena */ htab [ h ] = make_node ( key , NULL ); } else { struct node * it ; int cursor = M -1 ; /* Encuentra el primer cubo vacío */ while ( cursor >= 0 && htab [ cursor ] != NULL ) -- cursor ; /* La tabla está llena, finaliza sin éxito */ if ( cursor == -1 ) return -1 ; htab [ cursor ] = make_node ( key , NULL ); /* Encuentra el último nodo en la cadena y apúntalo */ it = htab [ h ]; mientras ( it -> siguiente != NULL ) it = it -> siguiente ; es -> siguiente = htab [ cursor ]; } devuelve 0 ; } Una ventaja de esta estrategia es que el algoritmo de búsqueda para encadenamiento separado se puede utilizar sin cambios en una tabla hash fusionada.
Búsqueda en C:
char * find ( char clave [] ) { unsigned h = hash ( clave , strlen ( clave ) ) % N ; si ( htab [ h ] != NULL ) { struct nodo * it ; /* Busca la cadena en el índice h */ for ( it = htab [ h ]; it != NULL ; it = it -> next ) { if ( strcmp ( key , it -> data ) == 0 ) return it -> data ; } } devuelve NULL ; } La eliminación puede ser difícil. [3] [4]
El encadenamiento fusionado evita los efectos de la agrupación primaria y secundaria y, como resultado, puede aprovechar el algoritmo de búsqueda eficiente para el encadenamiento por separado. Si las cadenas son cortas, esta estrategia es muy eficiente y puede condensarse en gran medida en términos de memoria. Al igual que en el direccionamiento abierto, la eliminación de una tabla hash fusionada es complicada y potencialmente costosa, y el cambio de tamaño de la tabla es terriblemente costoso y debería hacerse rara vez, si es que se hace alguna vez. [ cita requerida ]