Tabla hash

Una tabla hash, matriz asociativa, mapa hash, tabla de dispersión o tabla fragmentada 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, un número que identifica la posición (casilla o cubeta) donde la tabla hash localiza el valor deseado.

Un ejemplo práctico para ilustrar que es una tabla hash es el siguiente: Se necesita organizar los periódicos que llegan diariamente de tal forma que se puedan ubicar de forma rápida, entonces se hace de la siguiente forma - se hace una gran caja para guardar todos los periódicos (una tabla), y se divide en 31 contenedores (ahora es una "hash table" o tabla fragmentada), y la clave para guardar los periódicos es el día de publicación (índice). Cuando se requiere buscar un periódico se busca por el día que fue publicado y así se sabe en que zócalo (bucket) está. Varios periódicos quedarán guardados en el mismo zócalo (es decir colisionan al ser almacenados), lo que implica buscar en la sub-lista que se guarda en cada zócalo. De esta forma se reduce el tamaño de las búsquedas de O(n) a O(log(n)).

Ejemplo de tabla hash.

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),[1] 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.

Funcionamiento

Las operaciones básicas implementadas en las tablas hash son:

inserción(llave, valor)
búsqueda(llave) que devuelve valor

La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer funciones como iteración en la tabla, crecimiento y vaciado. Algunas tablas hash permiten almacenar múltiples valores bajo la misma clave.

Para usar una tabla hash se necesita:

  • Una estructura de acceso directo (normalmente un array).
  • Una estructura de datos con una clave
  • Una función resumen (hash) cuyo dominio sea el espacio de claves y su imagen (o rango) los números naturales.

Inserción

  1. Para almacenar un elemento en la tabla hash se ha de convertir su clave a un número. Esto se consigue aplicando la función resumen (hash) a la clave del elemento.
  2. El resultado de la función resumen ha de mapearse al espacio de direcciones del vector que se emplea como soporte, lo cual se consigue con la función módulo. Tras este paso se obtiene un índice válido para la tabla.
  3. El elemento se almacena en la posición de la tabla obtenido en el paso anterior.
    1. Si en la posición de la tabla ya había otro elemento, se ha producido una colisión. Este problema se puede solucionar asociando una lista a cada posición de la tabla, aplicando otra función o buscando el siguiente elemento libre. Estas posibilidades han de considerarse a la hora de recuperar los datos.

Búsqueda

  1. Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la función resumen.
  2. El valor obtenido se mapea al espacio de direcciones de la tabla.
  3. 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.
Other Languages
العربية: جدول هاش
български: Хеш-таблица
bosanski: Heš tabela
dansk: Hashtabel
Deutsch: Hashtabelle
English: Hash table
Esperanto: Hakettabelo
eesti: Paisktabel
français: Table de hachage
hrvatski: Hash tablica
magyar: Hash tábla
italiano: Hash table
한국어: 해시 테이블
latviešu: Jaucējtabula
മലയാളം: ഹാഷ് ടേബിൾ
Nederlands: Hashtabel
norsk nynorsk: Hashtabell
norsk bokmål: Hashtabell
русский: Хеш-таблица
Simple English: Hash table
slovenčina: Hašovacia tabuľka
српски / srpski: Хеш табела
svenska: Hashtabell
Tagalog: Tablang hash
українська: Хеш-таблиця
Tiếng Việt: Bảng băm
中文: 哈希表