Tabla hash java

HASH

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 sólo se dan funciones hash perfectas cuando las entradas están preestablecidas.

Direccionamiento Cerrado, Encadenamiento separado o 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 cuan uniformemente la función hash distribuya el conjunto de claves entre los m slots de la tabla.

Ventajas:

La técnica de encadenamiento tiene ventajas sobre direccionamiento abierto. Primero el borrado es simple y segundo 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. De hecho, muchas tablas hash encadenadas pueden no requerir crecimiento nunca, dado que la degradación de rendimiento es lineal en la medida que se va llenando la tabla. Por ejemplo, una tabla hash encadenada con dos veces el número de elementos recomendados, será dos veces más lenta en promedio que la misma tabla a su capacidad recomendada.

Desventajas:

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. También los viajes a través de las listas tienen un rendimiento de caché muy pobre.

Direccionamiento abierto o 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 no existe esa llave en la tabla.

Inserción

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. 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 numero de salto como un segundo argumento:

Búsqueda

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

La operación 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 Search subsiguientes. Una solución es utilizar otro valor para indicar una posición que conténía un elemento que fue borrado y modificar la operación de búsqueda para que continué 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 Delete, se prefiere la técnica de encadenamiento para manejo de colisiones. Las secuencias de sondeo más socorridas incluyen:

El sondeo lineal ofrece el mejor rendimiento del caché, pero es más sensible al aglomeramiento, en tanto que el doble hasheo tiene pobre rendimiento en el caché pero elimina el problema de aglomeramiento. El sondeo cuadrático se sitúa en medio. El doble hasheo también puede requerir más cálculos que las otras formas de sondeo.