Saltar al contenido principal

Tablas hash

Una tabla hash (hash table), también conocidas como conjunto de claves-valor (key-value), diccionario (dictionary) o array asociativo (associative array), es una estructura de datos que permite almacenar y recuperar valores de forma eficiente utilizando claves (keys).

Utiliza una función hash para mapear las claves a índices en una lista, facilitando el acceso directo a los valores asociados. La función hash toma la clave como entrada y produce un número entero que normalmente se modula por el tamaño de la lista asociada a hash table para obtener un índice válido.

Las colisiones ocurren cuando dos claves diferentes producen el mismo índice. Hay varios métodos para manejar colisiones.

Características​

  • Función hash: Transforma la clave en un índice que se usa para almacenar o recuperar el valor asociado.
  • Acceso rápido: Permite un acceso medio en O(1) para operaciones de inserción, eliminación y búsqueda, debido a la función de hash.
  • Colisiones: Puede ocurrir cuando diferentes claves se mapean al mismo índice. Las colisiones son gestionadas mediante técnicas específicas.

Operaciones​

Las operaciones básicas en una estructura de datos de una tabla hash incluyen aquellas que permiten la manipulación y el acceso a los elementos de la tabla hash.

  • Insert(Clave, valor): Añadir un par clave-valor a la tabla hash. Si la clave ya existe, actualizar el valor asociado a esa clave.
  • Get: Obtener el valor asociado a una clave específica.
  • ContainsKey: Verificar si una clave existe en la tabla hash.
  • Delete: Quitar un par clave-valor de la tabla hash utilizando la clave.
  • Size: Determinar el número de pares clave-valor en la tabla hash.
  • IsEmpty: Verificar si la tabla hash no tiene pares clave-valor.

Otras operaciones sobre tablas hash son:

  • KeySet: Obtener todas las claves de la tabla hash.
  • Values: Obtener todos los valores de la tabla hash.

Usos comunes de las tablas hash​

  • Indexación rápida: Para realizar búsquedas rápidas en bases de datos o estructuras de datos.
  • Gestión de datos: Para almacenar y recuperar datos asociados a claves, como en cachés y diccionarios.

Técnica de hashing por Folding​

La técnica de folding (folding method) es un método para crear una función hash a partir de una clave que es un número largo o una cadena de caracteres. Esta técnica divide la clave en partes más pequeñas, realiza algunas operaciones sobre esas partes, y finalmente combina esos resultados para generar el hash final.

Hay varias variantes de la técnica de folding, pero la más común implica los siguientes pasos:

  1. Dividir la clave en partes iguales: La clave se divide en partes más pequeñas, que tienen el mismo número de dígitos o caracteres.
  2. Suma de las partes: Después de dividir la clave, se suman todas las partes. Ejemplo: 123 + 456 + 789 + 000 = 1368
  3. Aplicar modulación (opcional): Si el tamaño de la tabla hash es m, aplicamos la operación de módulo m al resultado de la suma para asegurarnos de que el índice resultante está dentro del rango de la tabla hash.

A continuación, vamos a utilizar la cadena de texto "ABCDEFGH" como clave y aplicar el método de folding para calcular su hash.

  • Convertir la cadena de texto en números. Primero, convertimos cada carácter de la cadena en un número utilizando su valor ASCII (u otro esquema de conversión similar).

    • A = 65
    • B = 66
    • C = 67
    • D = 68
    • E = 69
    • F = 70
    • G = 71
    • H = 72

    Por lo tanto, la cadena "ABCDEFGH" puede ser representada como la secuencia numérica: 65 66 67 68 69 70 71 72.

  • Dividir la Secuencia en Partes: Ahora, dividimos esta secuencia en partes iguales. Supongamos que dividimos en partes de dos dígitos.

  • Suma de las Partes Después de dividir, sumamos todas las partes. 65 + 66 + 67 + 68 + 69 + 70 + 71 + 72 = 548

  • Aplicar Modulación (opcional) Finalmente, si estamos trabajando con una tabla hash que tiene un tamaño fijo, aplicamos la operación de módulo m para asegurar que el resultado se encuentre dentro del rango de la tabla. Si el tamaño de la tabla hash es 100, entonces calculamos 548 % 100 = 48. El índice final en la tabla hash sería 48.

Ejemplo​

Consideraciones del ejemplo
  • En este ejemplo vamos a suponer que no ocurren colisiones.
  • Utilizaremos la técnica de Hashing por Folding dividiendo en 3 números.
  • El tamaño de la hash table será de 5.