Conceptos Fundamentales de Hashing
Una buena función hash debe poder calcularse en tiempo constante y satisfacer (al menos aproximadamente) la hipótesis de hashing uniforme: es equiprobable que una clave dada tenga cualquier valor hash entre 0 y m − 1.
Hashing Perfecto
Se dice que la función hash es inyectiva cuando cada dato de entrada se mapea a un valor hash diferente. En este caso, se dice que la función hash es perfecta. Para que se dé, es necesario que la cardinalidad del conjunto dominio sea inferior o igual a la cardinalidad del conjunto imagen. Normalmente, solo se dan funciones hash perfectas cuando las entradas están preestablecidas.
Métodos de Resolución de Colisiones en Tablas Hash
Encadenamiento Separado (Hashing Abierto)
En la técnica más simple de encadenamiento, cada casilla en el array referencia una lista de los registros insertados que colisionan en la misma casilla. La inserción consiste en encontrar la casilla correcta y agregar al final de la lista correspondiente. El borrado consiste en buscar y quitar de la lista.
El peor caso para una tabla hash que use la técnica de encadenamiento es que todas las claves almacenadas tengan el mismo valor hash, en cuyo caso se termina con una única lista enlazada que contiene todos los elementos almacenados, y el costo de la búsqueda y el borrado es O(n). El costo promedio depende de cuán uniformemente la función hash distribuya el conjunto de claves entre los m slots de la tabla.
Ventajas del Encadenamiento
- El borrado es simple.
- El crecimiento de la tabla puede ser pospuesto durante mucho más tiempo, dado que el rendimiento disminuye mucho más lentamente incluso cuando todas las casillas ya están ocupadas.
- Muchas tablas hash encadenadas pueden no requerir crecimiento nunca, dado que la degradación del rendimiento es lineal a medida que se va llenando la tabla. Por ejemplo, una tabla hash encadenada con el doble del número de elementos recomendados será, en promedio, dos veces más lenta que la misma tabla a su capacidad recomendada.
Desventajas del Encadenamiento
- Las tablas hash encadenadas heredan las desventajas de las listas ligadas.
- Cuando se almacenan cantidades de información pequeñas, el gasto extra de las listas ligadas puede ser significativo.
- Los viajes a través de las listas tienen un rendimiento de caché muy pobre.
Direccionamiento Abierto (Hashing Cerrado)
Las tablas hash de direccionamiento abierto pueden almacenar los registros directamente en el array. Las colisiones se resuelven mediante un sondeo del array, en el que se buscan diferentes localidades del array (secuencia de sondeo) hasta que el registro es encontrado o se llega a una casilla vacía, indicando que esa llave no existe en la tabla.
Inserción en Direccionamiento Abierto
Para realizar una inserción usando el método de direccionamiento abierto, se examinan sistemáticamente los slots de la tabla hasta que se encuentra una posición libre. En lugar de usar un orden prefijado como 0, 1, …, m − 1 (que requiere un tiempo de búsqueda Θ(n)), la secuencia de posiciones que se examinan depende de la clave que se inserta. Para determinar los slots a examinar, se extiende la función hash para incluir el número de salto como un segundo argumento.
Búsqueda en Direccionamiento Abierto
El algoritmo de búsqueda examina la misma secuencia de slots que en la inserción, con éxito al encontrar la clave buscada o sin éxito al encontrar una posición vacía, porque de haberse insertado el elemento, debería haber ocupado esa posición.
Borrado en Direccionamiento Abierto
La operación de borrado (Delete) debe implementarse con cuidado. Cuando se borra un slot i, no se puede simplemente marcar la posición como vacía porque afectaría a las operaciones de búsqueda (Search) subsiguientes. Una solución es utilizar otro valor para indicar una posición que contenía un elemento que fue borrado, y modificar la operación de búsqueda para que continúe si encuentra ese tipo de posiciones, y la operación de inserción para que considere vacías las posiciones de ese tipo. Cuando se hace esto, sin embargo, el tiempo de búsqueda deja de ser dependiente del factor de carga α. Por esta razón, cuando se requiere la operación de borrado (Delete), se prefiere la técnica de encadenamiento para el manejo de colisiones.
Tipos de Sondeo
Las secuencias de sondeo más socorridas incluyen:
- Sondeo lineal: Ofrece el mejor rendimiento del caché, pero es más sensible al aglomeramiento.
- Doble hashing: Tiene un pobre rendimiento en el caché pero elimina el problema de aglomeramiento. También puede requerir más cálculos que otras formas de sondeo.
- Sondeo cuadrático: Se sitúa en un punto intermedio entre el sondeo lineal y el doble hashing.