Estructura de datos que facilita la inserción y eliminación
Una tabla hash (también llamada tabla hash) es una estructura de datos a la que se puede acceder directamente en función de los valores clave. En otras palabras, acelera las búsquedas asignando valores clave a una ubicación en la tabla para acceder a los registros. Esta función de mapeo se llama función hash y la matriz que almacena los registros se llama tabla hash.
Dada una tabla m, existe una función f(clave). Para cualquier valor de clave dado, si se puede obtener después de sustituir la dirección del registro en la tabla que contiene esa clave en la función, entonces la tabla m se llama tabla hash y la función f(clave) es la función hash.
En promedio, la estructura de datos con la velocidad de búsqueda más rápida y la capacidad de acomodar inserciones y eliminaciones es una tabla hash.
Características de las tablas hash
1.
Dado que la tabla hash tiene una función hash, todas las claves especificadas se pueden asignar a una dirección, por lo que al acceder al valor (Valor) correspondiente a una determinada clave, no es necesario buscar una por una. y puedes saltar directamente a esta dirección. Por lo tanto, cuando agregamos, eliminamos, modificamos, buscamos, etc. a la tabla hash, la velocidad es muy rápida.
2. Requiere espacio adicional
En primer lugar, la tabla hash en realidad no está satisfecha. Si la tabla hash está llena, debe ser una coincidencia. Y cuando la utilización de elementos en la tabla hash aumenta cada vez más, el rendimiento disminuirá, por lo que generalmente se elige la expansión para resolver este problema.
Además, si hay conflictos, se requiere espacio adicional para almacenarlos, como el método de dirección en cadena, que no solo requiere espacio adicional, sino que también requiere el uso de otras estructuras de datos. Existe una palabra muy común para expresar esta característica, se llama “espacio por tiempo”. En la mayoría de los casos, para lograr un mejor rendimiento, normalmente consideramos sacrificar algo de espacio para que el algoritmo sea más rápido.
3. Caos
Otra característica obvia de las tablas hash es el desorden. Para acceder a los elementos más rápido, la tabla hash encuentra directamente la dirección de almacenamiento de acuerdo con la función hash, de modo que nuestra velocidad de acceso puede ser más rápida, pero no hay forma de manejar el acceso ordenado.
4. Pueden producirse colisiones.
No existe una función hash perfecta, siempre se producirán colisiones, por lo que es necesario resolverlas, lo que también hace que las tablas hash sean más complejas. En general, la resolución de conflictos no es necesariamente la misma en diferentes implementaciones de lenguajes de alto nivel.