Tabla de Hash | Hash Table

Repo: https://github.com/umarquez/100DaysOfC0D3/tree/master/7-hash_table

Es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada. https://es.wikipedia.org/wiki/Tabla_hash

Una Tabla Hash funciona como los buzones de correo de un edificio de departamentos, cada uno pertenece a una familia y están identificados por el número de departamento, no puede haber departamento sin buzón, buzón sin departamento o departamento con más de un buzón; para que alguien pueda enviar una paquete a la familia Robles, primero debemos obtener el identificador del buzón de esta familia, esta sería la función hash pues traduce el nombre de la familia en un identificador único. Si lo pensamos, incluso podría vivir más de una familia con el mismo nombre en el mismo edificio y aún así, este identificador nos ayuda a diferenciar una familia de la otra; así que podemos considerar que esta función hash es muy segura pues previene colisiones (las colisiones ocurren cuando una función genera el mismo identificador o hash a dos valores diferentes).

hash table
hash table

Una vez obtenido el identificador, utilizamos este para referirnos a los datos asociados a este, en este caso el mensajero lo usa para entregar la correspondencia a la familia, y el Sr. Robles lo utiliza para recuperar lo que previamente ha sido entregado.

En Golang podemos aprovechar una estructura de datos propia de la librería estándar para realizar esta implementación: map[]

Ejemplo

Vamos a utilizar una tabla hash para contar la frecuencia con la que aparece cada palabra en un texto aleatorio, al final mostraremos los resultados.

  • Para lograrlo, primero debemos definir la función hash y el tipo de datos que utilizaremos para definir la llave, en este caso: string.

    func Hash(input string) string {
    	// Limpiamos el texto y lo conventimos a minúsculas
    	return strings.TrimSpace(strings.ToLower(input))
    }
    
  • Obtenemos el texto aleatorio

  • Lo separamos en palabras y comenzamos a contar sumando uno a la posición dada por el hash de la palabra actual.

    func main() {
    // Tabla Hash:
    var wordsCounter = make(map[string]int)
    var keys = \[\]string{}
    
    // Texto a analizar
    rndText :=  NewRandomText()
        
    	// Partiendo texto en "palabras" y procesando cada una
    words := strings.Split(rndText.TextOut, " ")
    for _, word := range words {
    		// Obteniendo hash
    		hWord := Hash(word)
    		wordsCounter[hWord]++
    	}
    }
    
    - Palabras totales:
    4996
    
    █████████████  much [200] = 4%
    ████████████  far [186] = 3.72%
    ███████████  and [171] = 3.42%
    ███████  this [108] = 2.16%
    ██████  a [103] = 2.06%
    ██████  that [102] = 2.04%
    ██████  less [98] = 1.96%
    ██████  one [97] = 1.94%
    ██████  some [94] = 1.88%
    █████  more [83] = 1.66%
    █████  the [82] = 1.64%
    ███  darn [47] = 0.94%
    ███  hello [46] = 0.92%
    ██  yikes [44] = 0.88%
    ██  goodness [43] = 0.86%
    ██  crud [42] = 0.84%
    ██  oh [42] = 0.84%
    ██  alas [41] = 0.82%
    ██  in [37] = 0.74%
    ██  wow [37] = 0.74%