Tabla hash
Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el acceso ordenado a su contenido es bastante lento.
Es deseable utilizar la misma función hash para arrays de cualquier tamaño concebible.
En estos casos, cuando una casilla ya está ocupada, debemos encontrar otra ubicación donde almacenar el nuevo registro, y hacerlo de tal manera que podamos encontrarlo cuando se requiera.
La inserción consiste en encontrar la casilla correcta y agregar al final de la lista correspondiente.
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.
También se pueden utilizar vectores dinámicos para disminuir el espacio extra requerido y mejorar el rendimiento del caché cuando los registros son pequeños.
Las tablas hash de direccionamiento abierto pueden almacenar los registros directamente en el array.
Una vez que se llena la tabla, los algoritmos de sondeo pueden incluso caer en un círculo sin fin.
Incluso utilizando buenas funciones hash, el límite aceptable de capacidad es normalmente 80%.
Con funciones hash pobremente diseñadas el rendimiento puede degradarse incluso con poca información, al provocar aglomeramiento significativo.
Estos algoritmos hash no requieren que los elementos estén ordenados.
Esta función se emplea con claves numéricas entre las que existen huecos de tamaño conocido, obteniéndose direcciones consecutivas.
Consiste en elevar al cuadrado la clave y coger las cifras centrales.
Consiste en ignorar parte del número y utilizar los elementos restantes como índice.
El tiempo de búsqueda se reduce considerablemente, y no hace falta poner restricciones al tamaño del arreglo, ya que se pueden añadir nodos dinámicamente a la lista.
El proceso de búsqueda concluye cuando el elemento es hallado, o bien cuando se encuentra una posición vacía.
Se trata al arreglo como a una estructura circular: el siguiente elemento después del último es el primero.
La función de rehashing es, por tanto, de la forma: R(H(X)) = (H(X) + 1) % m (siendo m el tamaño del arreglo) Ejemplo: Si la posición 397 ya estaba ocupada, el registro con clave 0596397 es colocado en la posición 398, la cual se encuentra disponible.
Las tablas hash se presentaron como una alternativa hacia las estructuras tipo árbol ya que permitían el almacenamiento de grandes volúmenes de información y algoritmos eficientes para la administración sobre estas estructuras (inserción, eliminación y búsqueda).
El método de las expansiones totales consiste en realizar una duplicación del tamaño del arreglo establecido para realizar la tabla hash, esta expansión se ejecuta cuando se supera la densidad de ocupación.
Para realizar una reducción la densidad de ocupación se debe disminuir a un valor menor al rango establecido y los registros se deben eliminar de tal manera que los registros resultantes se puedan ingresar en una tabla hash que posea la mitad del tamaño de la tabla original.
Cada vez que se implementa una reducción es necesario volver a utilizar la función hash con cada uno de los registros almacenados.
El método de las expansiones parciales consiste en incrementar en un 50% el tamaño del arreglo establecido para realizar la tabla hash, esta expansión se ejecuta cuando se supera la densidad de ocupación.
Para realizar una reducción la densidad de ocupación debe disminuir a un valor menor al rango establecido y los registros se deben eliminar de tal manera que los registros resultantes se puedan ingresar en una tabla hash que posea la mitad del tamaño de la tabla original.
Cada vez que se implementa una reducción es necesario volver a utilizar la función hash con cada uno de los registros almacenados.
