En informática, una tabla hash es una estructura de datos para almacenar datos que consta de una lista de valores, llamados claves, que se emparejan con una lista de valores correspondiente, llamada matriz. Por ejemplo, el nombre de una empresa puede emparejarse con su dirección. Normalmente, cada valor de 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 de la empresa a su dirección, su número de teléfono y su categoría de empresa, 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 hash. 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 de hash cuando se asignan dos claves al mismo valor correspondiente. Cuando ocurre una colisión de hash, la función de hash generalmente se ejecuta nuevamente hasta que se encuentra un valor correspondiente único; esto comúnmente da como resultado tiempos de hash más largos. Aunque la cantidad de claves en una tabla hash generalmente es fija, 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 ineficaces 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 claves futuras, ya que la mayoría de las funciones hash generalmente buscan la siguiente posición disponible en la matriz. Si ya se ha asignado un gran grupo de valores, normalmente se necesitará mucho más tiempo para 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 hash ya existentes en relación con el tamaño total de la matriz correspondiente en una tabla hash. Por lo general, 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 agrupaciones hasta cierto punto. A menudo, este umbral se puede utilizar para determinar qué tan eficiente es una función hash con un número determinado de claves 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 o agrupaciones dado 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 agrupaciones) 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.