¿Qué es un hashtable?
En informática, una hashtable es una estructura de datos para almacenar datos que consiste en una lista de valores, llamadas claves, que se combinan con una lista correspondiente de valores, llamada matriz. Por ejemplo, un nombre comercial podría 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 a cada valor clave a un hash, que conecta el nombre comercial con su dirección, su número de teléfono y su categoría de negocios, 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 formatearse correctamente para que una hashtable funcione correctamente.
El rendimiento de una hashtable en un conjunto de datos depende de la eficiencia de su función hash. Una buena función de hash típicoAlly proporciona una búsqueda uniforme de claves y una distribución uniforme de mapeos en la matriz correspondiente. Una colisión hash ocurre 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 un hashtable generalmente se fija, a veces puede haber claves duplicadas. Aun así, una hashtable bien diseñada tiene funciones de hash efectivas que asignan cada clave a un valor correspondiente único en la matriz.
A veces, las funciones de hash ineficientes en un hashtable también pueden producir un grupo de mapeos. Si una función hash crea un clúster de asignaciones para las 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 hash generalmente buscan la próxima posición disponible en la matriz. Si un grupo grandeYa se ha asignado valores, generalmente tomarí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 hashs ya existentes en relación con el tamaño general de la matriz correspondiente en un hashtable. 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 grupos hasta cierto punto. A menudo, este umbral se puede usar para determinar cuán 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 de la informática se han esforzado por producir la función hash perfecta, una que no produce colisiones ni grupos dado un factor de carga creciente. En teoría, la clave para producir un hashtable perfecto esDuce una función hash perfecta. En general, los investigadores creen que una función hash perfecta debe 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 el hashing constante sin alcanzar un umbral.