Tablas Hash

Tablas Hash
Definición
* Las tablas hash aparecen para conseguir una búsqueda e inserción muy rápidas; para ello se hace uso de un array, con lo que volvemos a la estructura básica de almacenamiento. Sin embargo, hay una diferencia importante que es lo que hace que sea mejor que el array en cuanto a rapidez: a cada dato se le asigna, mediante una fórmula matemática denominada función hash,una posición única en la tabla, con lo que la búsqueda, la inserción y el borrado son inmediatos.
* Una tabla Hash es un contenedor asociativo (tipo Diccionario) que permite un almacenamiento y posterior recuperación eficientes de elementos (denominados valores) a partir de otros objetos, llamados claves. Una tabla hash se puede ver como un conjunto de entradas. Cada una de estas entradastiene asociada una clave única, y por lo tanto, diferentes entradas de una misma tabla tendrán diferentes claves. Esto implica, que una clave identifica unívocamente a una entrada en una tabla hash. Por otro lado, las entradas de las tablas hash están compuestas por dos componentes, la propia clave y la información que se almacena en dicha entrada.
Operaciones que se realizan en las tablas Hash* Inserción de datos: El proceso de inserción en una tabla hash es muy simple y sencillo. Sobre el elemento que se desea insertar se aplica la función de dispersión. El valor obtenido tras la aplicación de esta función será el índice de la tabla en el que se insertará el nuevo elemento.
* Búsqueda de datos: Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a lacual se le aplica la función resumen. El valor obtenido se mapea al espacio de direcciones de la tabla. Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.* Borrado de información: Una vez indicada la clave del objeto a borrar, se procederá a eliminar el valor asociado a dicha clave de la tabla. Esta operación se realiza en tiempo constante, sin importar el tamaño de la tabla o el número de elementos que almacene en ese momento la estructura de datos. Esto es así ya que al ser la tabla una estructura a la que se puede acceder directamente a travésde las claves, no es necesario recorrer toda la estructura para localizar un elemento determinado.
* Redispersión: Consiste en pasar todos los elementos de la tabla original a una nueva tabla de un tamaño mayor. De esta forma, se reduce el factor de carga de la tabla.
Ventajas
* El acceso a los datos suele ser muy rápido si se cumplen las siguientes condiciones:
* Una razón deocupación no muy elevada (a partir del 75% de ocupación se producen demasiadas colisiones y la tabla se vuelve ineficiente).
* Una función resumen que distribuya uniformemente las claves. Si la función está mal diseñada, se producirán muchas colisiones.
* Almacenamiento asociativo
* Recuperación eficiente de la información

Desventajas
* Al tratarse de un array, el tamaño de latabla está limitado y debe fijarse desde el principio.
* Como las posiciones ocupadas no tienen por qué ser consecutivas, no se puede recorrer el contenido de una tabla hash.
* Como la posición de una palabra se calcula de forma matemática, los datos no pueden almacenarse ordenados.
* Si permitimos datos duplicados se produce lo que se denomina “colisión”, que consiste en que a dospalabras se les asigna la misma posición en el array.
Pseudocódigo de tablas Hash
class nodo{
private:
int dato;
bool estado;
public:
nodo()
{
dato=0;
estado=false;/*true=hay , false=no hay*/
}
friend class TablaHash;
};

class TablaHash{
private:
int m;
int tablesize;
nodo *t;
public:
TablaHash(int n)
{
tablesize=n;
m=n-2;
t=new nodo[n];

}
void ingresar(int);...