Las Tablas Hash o Tablas de Dispersión permiten insertar, remover y buscar un elemento por medio de un key (llave).
Estas operaciones presentan una complejidad constante O(1). De todas maneras, las tablas Hash requieren el doble de espacio del que es necesario para guardar los elementos dentro de esta.
Los
elementos o Nodos se almacenan en ARREGLOS. El arreglo indice donde el elemento se guarda se decide usando una Funcion de Hash.
Si una key (llave) de un elemnto y m son el tamaño total de la tabla de Hash,
entonces la función h(k) regresa un integro entre 0 y -1
Un arreglo simple puede ser visto como una función de hash y esta función regresaun entero.
Las unicas keys que soporta son enteros. El arreglo debe ser
lo suficientemente grande para soportar todos los enteros. En Java se requieren 232 elemnetos dde arreglos (4 mil millones).
La primera opción para una tabla HASH (dispersión) seria usar la función que convierte
otro tipo de key (llave) en un entero. por ejemplo una cadena (string) a un entero.
Como segunda opción esta el sobreponerse usando un arreglo más pequeño. ya que el número de elementos en un arreglo
es más pequeño que el rango de posibles llaves.Estas llaves se dispersan hacia el mismo indice del arreglo. A esto se le conoce como COLISIÓN ya que previenen que las tablas tengan una complejidad de 0(1) en el peor
de los casos.
Una función de Hash consiste de DOS partes:
1) Convertir la llave en un integro
2)Convertir ese integro en el indice del arreglo
Para que una función de hash sea más rapida, debe de
reducirse el numero de COLISIONES.
Para referencia y ejemplos ver la seccion de
