¿Qué es una tabla hash?

En informática, una tabla hash es una estructura de datos para almacenar datos que consiste en una lista de valores, llamados claves, que se combinan con una lista correspondiente de valores, llamada matriz. Por ejemplo, un nombre comercial puede emparejarse con su dirección. Por lo general, cada valor en la matriz tiene un número de posición denominado hash. La función hash es generalmente un conjunto de instrucciones o un algoritmo que asigna cada valor clave a un hash, conectando el nombre comercial a su dirección, su número de teléfono y su categoría comercial, por ejemplo. El propósito de la función hash es asignar cada clave a un valor correspondiente único en la matriz; Esto se conoce comúnmente como hashing. Las funciones hash deben estar formateadas correctamente para que una tabla hash funcione correctamente.

El rendimiento de una tabla hash en un conjunto de datos depende de la eficiencia de su función hash. Una buena función hash normalmente proporciona una búsqueda uniforme de claves y una distribución uniforme de asignaciones en la matriz correspondiente. Se produce una colisión hash cuando se asignan dos claves al mismo valor correspondiente. Cuando se produce una colisión hash, la función hash generalmente se ejecuta nuevamente hasta que se encuentra un valor correspondiente único; esto comúnmente resulta en tiempos de hashing más largos. Aunque el número de claves en una tabla hash generalmente es fijo, a veces puede haber claves duplicadas. Aun así, una tabla hash bien diseñada tiene funciones hash efectivas que asignan cada clave a un valor correspondiente único en la matriz.

A veces, las funciones hash ineficientes en una tabla hash también pueden producir un grupo de asignaciones. Si una función hash crea un grupo de asignaciones para claves existentes, esto puede aumentar la cantidad de tiempo que lleva buscar los valores correspondientes. Esto puede ralentizar el hash para futuras claves, ya que la mayoría de las funciones de hash generalmente buscan la siguiente posición disponible en la matriz. Si ya se ha asignado un gran grupo de valores, normalmente llevaría mucho más tiempo buscar un valor no asignado para una nueva clave.

El factor de carga es otro concepto relacionado con la eficiencia de una función hash; el factor de carga es la cantidad de hashings ya existentes en relación con el tamaño general de la matriz correspondiente en una tabla hash. Generalmente se define dividiendo el número de claves ya asignadas por el tamaño de la matriz correspondiente. A medida que aumenta el factor de carga, una buena función hash normalmente mantendrá un número constante de colisiones y grupos hasta cierto punto. A menudo, este umbral se puede usar para determinar qué tan eficiente es una función hash con un número dado de teclas y cuándo puede ser necesaria una nueva función hash.

Muchos investigadores en ciencias de la computación se han esforzado por producir la función hash perfecta, una que no produzca colisiones ni grupos debido a un factor de carga creciente. En teoría, la clave para producir una tabla hash perfecta es producir una función hash perfecta. En general, los investigadores creen que una función hash perfecta debería tener un rendimiento constante (el número de colisiones y grupos) con un factor de carga creciente. En el peor de los casos, una función hash perfecta aún permitiría un hash constante sin alcanzar un umbral.