Explicación de la tabla hash: qué es y cómo implementarla

Una tabla hash, también conocida como mapa hash, es una estructura de datos que asigna claves a valores. Es una parte de una técnica llamada hash, la otra es una función hash. Una función hash es un algoritmo que produce un índice de dónde se puede encontrar o almacenar un valor en la tabla hash.

Algunas notas importantes sobre las tablas hash:

1. Los valores no se almacenan en orden.
2. Debes tener en cuenta las posibles colisiones. Esto generalmente se hace con una técnica llamada encadenamiento. Encadenar significa crear una lista vinculada de valores, cuyas claves se asignan a un índice determinado.

Implementación de una tabla hash

La idea básica detrás del hash es distribuir pares clave / valor a través de una matriz de marcadores de posición o "cubos" en la tabla hash.

Una tabla hash es normalmente una matriz de listas enlazadas. Cuando desee insertar un par clave / valor, primero debe usar la función hash para asignar la clave a un índice en la tabla hash. Dada una clave, la función hash puede sugerir un índice donde se puede encontrar o almacenar el valor:

index = f(key, array_size)

A menudo, esto se hace en dos pasos:

hash = hashfunc(key) index = hash % array_size

El uso de este método hashes independiente del tamaño de la tabla hash. hashse reduce a un índice, un número entre 0, el inicio de la matriz y array_size - 1el final de la matriz, utilizando el operador de módulo (%).

Considere la siguiente cadena S:

string S = “ababcd”

Debe contar la frecuencia de todos los caracteres en S. La forma más fácil de hacer esto es iterar a través de todos los caracteres posibles y contar la frecuencia de cada uno, uno por uno.

Esto funciona, pero es lento: la complejidad de tiempo de este enfoque es O (26 * N), Nsiendo el tamaño de la cadena Smultiplicado por 26 caracteres posibles de AZ.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Salida:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Echemos un vistazo a una solución que usa hash.

Tome una matriz y use la función hash para codificar los 26 caracteres posibles con índices de la matriz. Luego, repita Sy aumente el valor del carácter actual de la cadena con el índice correspondiente para cada carácter.

La complejidad de este enfoque de hash es O (N), donde N es el tamaño de la cadena.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Salida

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Colisiones de hash

Dado que su mapa hash probablemente será significativamente más pequeño que la cantidad de datos que está procesando, las colisiones hash son inevitables. Hay dos enfoques principales para manejar colisiones: encadenamiento y direccionamiento abierto .

Encadenamiento

Como se mencionó anteriormente, el encadenamiento significa que cada par clave / valor en la tabla hash, el valor es una lista vinculada de datos en lugar de una sola celda.

Por ejemplo, imagine que la clave 152 tiene el valor "John Smith". Si se agrega el valor "Sandra Dee" a la misma clave, "Sandra Dee" se agrega como otro elemento a la clave 152, justo después de "John Smith".

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

El principal inconveniente del encadenamiento es el aumento de la complejidad del tiempo. En lugar de 0 (1) como con una tabla hash normal, cada búsqueda llevará más tiempo ya que necesitamos recorrer cada lista enlazada para encontrar el valor correcto.

Direccionamiento abierto

El direccionamiento abierto significa que, una vez que se asigna un valor a una clave que ya está ocupada, se mueve a lo largo de las claves de la tabla hash hasta encontrar una que está vacía. Por ejemplo, si "John Smith" se asignó a 152, "Sandra Dee" se asignará al siguiente índice abierto:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

El principal inconveniente del direccionamiento abierto es que, cuando busca valores, es posible que no estén en el mapa clave en el que los espera. En cambio, debe recorrer diferentes partes de la tabla hash para encontrar el valor que está buscando.