[7/100] #100DaysOfC0D3
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.
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).
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]++
}
}
main.go.log
- 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%