Tabla hash

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Busca fuentes: «Tabla hash» – noticias · libros · académico · imágenes Este aviso fue puesto el 29 de noviembre de 2017.

Una tabla hash, matriz asociativa, hashing, mapa hash, tabla de dispersión o tabla fragmentada es una estructura de datos que implementa el tipo de dato abstracto llamado diccionario (tipo de dato abstracto). Esta asocia llaves o claves con valores.^[1]​ 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, un número que identifica la posición (casilla o cubeta) donde la tabla hash localiza el valor deseado.^[2]​

Las tablas hash se suelen implementar sobre vectores de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante de búsqueda promedio O(1),^[3]​ sin importar el número de elementos en la tabla. Sin embargo, en casos particularmente 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 se almacenan 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 estructuras como árboles binarios auto-balanceables tienen un tiempo promedio de búsqueda mayor (tiempo de búsqueda O(log n)), pero la información está ordenada en todo momento.

1. ↑ Todo lo que quería saber sobre las tablas hash
2. ↑ Tema: “Tablas Hash”
3. ↑ La reconstrucción de la tabla requiere la creación de un array más grande y el uso posterior de la función asignar para insertar todos los elementos del viejo array en el nuevo array más grande. Es común aumentar el tamaño del array exponencialmente, por ejemplo duplicando el tamaño del array.