Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos(teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona transformando la clave con una función hash en un hash, unnúmero que la tabla hash utiliza para localizar el valor deseado.
Las tablas hash se suelen implementar sobre arrays de una dimensión, aunque se pueden hacer implementaciones multi-dimensionalesbasadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante de búsqueda promedio O(1),[1] sin importar el número de elementos en la tabla. Sin embargo, en casosparticularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, en función del número de elementos.
Comparada con otras estructuras de arrays asociadas, las tablas hash son más útiles cuando sealmacenan grandes cantidades de información.
Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el acceso ordenado a su contenido es bastante lento. Otras estructurascomo árboles binarios auto-balanceables son más rápidos en promedio (tiempo de búsqueda O(log n)) pero la información está ordenada en todo momento.
Clasificación
Hashing Perfecto: Existeuna Función de Enumeración que asigna a cada valor del dominio una única posición de memoria. No posee colisiones.Hashing Puro: La función de Hash puede asignar a dos valores distintos el mismo lugar enmemoria. [pic] y h(x1) = h(x2). Estos dos valores reciben el nombre de sinónimos. Las estructuras de hashing puros poseen colisiones y en consecuencia se deberán establecer mecanismos para tratar los mismos.Podemos clasificarlos en estructuras cerradas y abiertas y dentro de las abiertas en estáticas y dinámicas:
Cerradas: No utilizan un nuevo espacio en memoria.
Abiertas: Utilizan espacio…
