Tablas HASH

Permiten únicamente un subconjunto de las operaciones permitidas por los árboles binarios de búsqueda. Las inserciones, eliminaciones y búsqueda tienen coste medio constante, basado en propiedades estadísticas. Esta mejora se consigue perdiendo gran cantidad de información sobre el orden de los elementos. Este método proporciona acceso muy rápido cuando la condición de búsqueda es de igualdad sobre un solo campo. Se aplica una función sobre el valor del campo y produce la dirección del bloque de disco. Ésta no produce direcciones distintas a todo distinto valor, porque el espacio de direccionamiento calculado suele ser mucho más grande que el espacio de direcciones. Cuando la función devuelve una dirección ocupada, se dice que ocurre una colisión. Si s es una cadena, se puede convertir s a un número entero grande x y después aplicar el operador % para obtener un índice adecuado. La cadena "hola" se puede representar como: "h". $128^{3}$ + "o". $128^{2}$ + "l" . $128^{1}$ + "a" . $128^{0}$ = 224.229.227 Luego, si el tamaño de la tabla es 10000, “hola” se indexaría por 9.227

public final static int hash (String clave, int tamTabla)
{
  int valorHash = 0;
  for(int index = 0; index < clave.length (); index ++)
      valorHash = (valorHash * 128 + clave.charAt(index)  
                                    % tamTabla;
  return valorHash;
}

Métodos para resolver colisiones

Direccionamiento abierto

Partiendo de la posición que especifica la dirección, se examinan las posiciones subsecuentes en orden hasta encontrar una no utilizada. El algoritmo buscar sigue el mismo camino que el insertar: si llega a una casilla vacía, el elemento no está, caso contrario lo busca secuencialmente hasta encontrarlo o hasta que haya una casilla vacía. La eliminación estándar no puede aplicarse, porque podrían fallar operaciones de buscar posteriores. Como consecuencia se implementa la eliminación perezosa, marcando los elementos como borrados. Para estimar la eficiencia de la E. Lineal se supone cada intento en la tabla independiente de los anteriores. Si la fracción de la tabla ocupada es k, entonces cada vez que examinamos una celda, la probabilidad de que esté ocupada es k independientemente de los intentos anteriores. Si se supone independencia entre intentos, el número medio de celdas que se examinan en una inserción es ${\frac {1}{1-k}}$ . Siendo (1-k) la probabilidad de encontrar una celda vacía y considerando que si la probabilidad de que un suceso se produzca es p, se necesitan en media ${\frac {1}{p}}$ intentos para que dicho suceso se produzca. Pero la independencia lineal no se cumple: existe un efecto denominado agrupación primaria: la formación de grandes grupos de celdas ocupadas, haciendo que las inserciones dentro de las agrupaciones sean más costosa. Teorema: El número medio de celdas examinadas en una inserción con exploración lineal es cercano a ${\frac {1}{2}}(1+{\frac {1}{(1-k)^{2}}})$ . Teorema: Si se emplea exploración cuadrática, el tamaño de la tabla es un número primo, y el factor de carga no excede el 0.5, siempre podemos insertar un nuevo elemento en la tabla, y durante una operación de inserción no se examina ninguna celda dos veces.

Exploración cuadrática

Para reducir el número de intentos se necesita un esquema de resolución de conflictos que evite la agrupación primaria. Si la función da como resultado la celda H y está ocupada, se consultan: $H+1^{2};H+2^{2};H+3^{2};.....;H+i^{2}$ El tamaño de la tabla debe ser un número primo para evitar que se formen ciclos en la función que excluyan celdas potencialmente vacías.

Encadenamiento

Se mantienen áreas de desbordamiento y se agrega un campo puntero a cada posición de registro.

Direccionamiento calculado múltiple

Cuando ocurre una colisión se recurre a más funciones, hasta que una de una dirección libre, o se acaben, en cuyo caso se aplica el direccionamiento abierto.

La función de direccionamiento

El objetivo de una función de direccionamiento calculado es distribuir los registros uniformemente en el espacio de direcciones. Lo mejor suele ser mantener la tabla de direccionamiento ocupada entre el 70% y el 90%, y elegir un número primo para el tamaño del espacio de direcciones si la función utilizada para direccionar es basada en módulo. Otras funciones requerirán que sea una potencia de dos.

Direccionamiento calculado externo para ficheros de disco

Direccionamiento calculado estático

El espacio de direcciones se divide en cubetas (uno o varios bloques contiguos) que contienen varios registros. Este esquema ofrece el acceso más rápido para recuperar un registro arbitrario. Se puede mantener un puntero a una lista enlazada de registros de desbordamiento en cada cubeta para cuando una se llena. La mayoría de las funciones no mantienen el orden de los registros, pero algunas sí lo hacen. El esquema descrito se le llama estático, porque asigna un número M fijo de cubetas. Siendo m el máximo de registros en una cubeta, si (M*m) resulta mucho menor que el número de registros, se estará desperdiciando espacio, si es al revés, habrán muchas colisiones y la recuperación resultará lenta.

Direccionamiento extensible

Si el factor de carga es superior a 0.5, aumenta el tamaño de la tabla al primo siguiente al doble del tamaño.

Si el factor de carga es inferior a 0.5, disminuye el tamaño de la tabla al primo siguiente a la mitad del tamaño.

Un nuevo vector implica una nueva función Hash: se debe buscar cada elemento en la tabla vieja, calcular su nuevo valor hash e insertarlo en la tabla nueva : REHASHING.

Direccionamiento extensible parcial

Si el factor de carga es superior a 0.5, aumenta el tamaño de la tabla al primo siguiente al 50% del tamaño original, luego de hacer dos incrementos sucesivos el tamaño obtenido será el nuevo tamaño original.

Si el factor de carga es inferior a 0.5, disminuye el tamaño de la tabla al primo siguiente a un 50% del tamaño original, luego de hacer dos decrementos sucesivos el tamaño obtenido será el nuevo tamaño original.

Un nuevo vector implica una nueva función Hash: se debe buscar cada elemento en la tabla vieja, calcular su nuevo valor hash e insertarlo en la tabla nueva : REHASHING.

Direccionamiento calculado extensible

Se mantiene un arreglo de 2d direcciones de cubeta (d es la profundidad global). Varias posiciones del directorio que tengan los primeros d’ (profundidad de la cubeta) bits en sus valores de direccionamiento calculado pueden contener la misma dirección de cubeta. El valor de d se puede aumentar o reducir en uno cada vez, duplicando o reduciendo a la mitad el número de entradas del array. Será necesario aumentarlo si una cubeta de profundidad d se desborda. Se podrá reducir si d > d’ para todas las cubetas. El espacio extra para la tabla del directorio es insignificante, y la reorganización es menor, ya que la mayor parte de las veces sólo los registros de una cubeta se distribuyen en dos, siendo costosa solamente cuando cambia d. Una desventaja es que deben realizarse dos accesos a bloque en lugar de uno, pero esta falta de rendimiento se considera leve.

Direccionamiento calculado lineal

Utiliza una función (k mod M). Cuando ocurre una colisión, a la cubeta 0 se le aplica la función (k mod 2M) y así parte de su contenido se depositará en una nueva cubeta M, y así sucesivamente se le irá aplicando a las cubetas 1, 2, 3, …, en orden secuencial, y agregando cubetas al final hasta llegar a (M-1), momento en el cual todas las cubetas se calcularán con la función (k mod 2M). Se debe mantener el número n de divisiones en una variable, y, al momento de recuperar un registro, si la función retorna un número menor a n, se aplicará la segunda función, ya que la cubeta ya estará dividida. La división se puede controlar monitoreando la carga del fichero, pudiendo recombinarse las c cubetas si la carga cae debajo de cierto umbral.