Tabla de picadillo
En informática , una tabla hash ( mapa hash ) es una estructura de datos que implementa un tipo de datos abstracto de matriz asociativa , una estructura que puede asignar claves a valores . Una tabla hash usa una función hash para calcular un índice , también llamado código hash , en una matriz de cubos o ranuras , a partir de los cuales se puede encontrar el valor deseado. Durante la búsqueda, se aplica un hash a la clave y el hash resultante indica dónde se almacena el valor correspondiente.
Idealmente, la función hash asignará cada clave a un cubo único, pero la mayoría de los diseños de tablas hash emplean una función hash imperfecta, lo que podría causar colisiones hash donde la función hash genera el mismo índice para más de una clave. Por lo general, estas colisiones se adaptan de alguna manera.
En una tabla hash bien dimensionada, el costo promedio (número de instrucciones ) para cada búsqueda es independiente del número de elementos almacenados en la tabla. Muchos diseños de tablas hash también permiten inserciones y eliminaciones arbitrarias de pares clave-valor , a un costo promedio constante ( amortizado [2] ) por operación. [3] [4]
En muchas situaciones, las tablas hash resultan ser, en promedio, más eficientes que los árboles de búsqueda o cualquier otra tabla de estructura de búsqueda. Por esta razón, se utilizan ampliamente en muchos tipos de software de computadora , particularmente para matrices asociativas , indexación de bases de datos , cachés y conjuntos .
La ventaja de usar hash es que la dirección de la tabla de un registro se puede calcular directamente desde la clave. El hash implica que una función , cuando se aplica a una clave , produce un hash . Sin embargo, dado que podría ser potencialmente grande, el resultado hash debe asignarse a entradas finitas en la tabla hash, o ranuras, se pueden usar varios métodos para asignar las claves al tamaño de la tabla hash . El método más común es el método de división, en el que se utiliza aritmética modular para calcular la ranura. [5] : 110
Un requisito básico es que la función debe proporcionar una distribución uniforme de valores hash. Una distribución no uniforme aumenta el número de colisiones y el costo de resolverlas. La uniformidad a veces es difícil de asegurar por diseño, pero puede evaluarse empíricamente usando pruebas estadísticas, por ejemplo, una prueba de chi-cuadrado de Pearson para distribuciones uniformes discretas. [6] [7]
