Análisis e implementación de la estructura de datos de la tabla hash en Go
Una tabla hash es una implementación hash de una estructura de datos de tabla hash. En lugar de utilizar una clave personalizada para almacenar el valor en un mapa, la estructura de datos realiza una función hash en la clave para devolver el índice exacto de un elemento en la matriz.
Implementación
Internamente, la tabla hash se representará con unmap
tipo, y expondré el
Put()
Remove()
Get()
Size()
métodos.
Voy a crear unValueHashtable
tipo genérico, seguro para la concurrencia, que puede generar tablas hash que contengan cualquier tipo. Las claves pueden ser de cualquier tipo siempre que implementen laStringer
interfaz. Mediante la ejecucióngo generate
el código creará una implementación de tabla hash específica de tipo, encapsulando la estructura de datos específica del valor real que contiene los datos.
// Package hashtable creates a ValueHashtable data structure for the Item type
package hashtable
import (
“fmt”
“sync”
<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>
)
// Key the key of the dictionary
type Key generic.Type
// Value the content of the dictionary
type Value generic.Type
// ValueHashtable the set of Items
type ValueHashtable struct {
items map[int]Value
lock sync.RWMutex
}
// the hash() private function uses the famous Horner’s method
// to generate a hash of a string with O(n) complexity
func hash(k Key) int {
key := fmt.Sprintf("%s", k)
h := 0
for i := 0; i < len(key); i++ {
h = 31*h + int(key[i])
}
return h
}
// Put item with value v and key k into the hashtable
func (ht *ValueHashtable) Put(k Key, v Value) {
ht.lock.Lock()
defer ht.lock.Unlock()
i := hash(k)
if ht.items == nil {
ht.items = make(map[int]Value)
}
ht.items[i] = v
}
// Remove item with key k from hashtable
func (ht *ValueHashtable) Remove(k Key) {
ht.lock.Lock()
defer ht.lock.Unlock()
i := hash(k)
delete(ht.items, i)
}
// Get item with key k from the hashtable
func (ht *ValueHashtable) Get(k Key) Value {
ht.lock.RLock()
defer ht.lock.RUnlock()
i := hash(k)
return ht.items[i]
}
// Size returns the number of the hashtable elements
func (ht *ValueHashtable) Size() int {
ht.lock.RLock()
defer ht.lock.RUnlock()
return len(ht.items)
}
Pruebas
Las pruebas describen el uso de la implementación anterior. Tenga en cuenta que nunca interactuamos con el subyacentemap
type, que bien podría implementarse de otra manera si Go no nos hubiera proporcionado ya un tipo de mapa.
package hashtable
import (
“fmt”
“testing”
)
func populateHashtable(count int, start int) *ValueHashtable {
dict := ValueHashtable{}
for i := start; i < (start + count); i++ {
dict.Put(fmt.Sprintf(“key%d”, i), fmt.Sprintf(“value%d”, i))
}
return &dict
}
func TestPut(t *testing.T) {
dict := populateHashtable(3, 0)
if size := dict.Size(); size != 3 {
t.Errorf(“wrong count, expected 3 and got %d”, size)
}
dict.Put(“key1”, “value1”) //should not add a new one, just change the existing one
if size := dict.Size(); size != 3 {
t.Errorf(“wrong count, expected 3 and got %d”, size)
}
dict.Put(“key4”, “value4”) //should add it
if size := dict.Size(); size != 4 {
t.Errorf(“wrong count, expected 4 and got %d”, size)
}
}
func TestRemove(t *testing.T) {
dict := populateHashtable(3, 0)
dict.Remove(“key2”)
if size := dict.Size(); size != 2 {
t.Errorf(“wrong count, expected 2 and got %d”, size)
}
}
Crear una estructura de datos de tabla hash concreta
Puede usar esta implementación genérica para generar tablas hash específicas de tipo, usando
//generate a `IntHashtable` hash table of `int` values
genny -in hashtable.go -out hashtable-int.go gen "Value=int"
//generate a </span>StringHashtable<span style="color:#e6db74">
hash table of </span>string<span style="color:#e6db74">
values
genny -in hashtable.go -out hashtable-string.go gen “Value=string”
Más tutoriales de go:
- Uso de NGINX Reverse Proxy para brindar servicios de Go
- Hacer una copia de una estructura en Go
- Los conceptos básicos de un servidor web Go
- Ordenar un tipo de mapa en Go
- Ir consejos en pocas palabras
- Explicación de las etiquetas Go
- Ir al formato de fecha y hora
- Procesamiento JSON con Go
- Ir a funciones variadas
- Hoja de referencia de Go Strings
- Explicación de la interfaz Go Empty
- Depuración de Go con VS Code y Delve
- Parámetros de devoluciones de Go Named
- Generación de cadenas y números aleatorios en Go
- Estructura del sistema de archivos de un proyecto de Go
- Algoritmo de búsqueda binaria implementado en Go
- Uso de indicadores de línea de comando en Go
- GOPATH explicado
- Cree una aplicación de línea de comandos con Go: lolcat
- Construyendo un comando CLI con Go: cowsay
- Uso de Shell Pipes con Go
- Tutorial de Go CLI: clon de la fortuna
- Enumere los archivos en una carpeta con Go
- Use Ir para obtener una lista de repositorios de GitHub
- Ve, agrega un trozo de cadenas a un archivo
- Ve, convierte una cadena en un segmento de bytes
- Visualice sus contribuciones locales de Git con Go
- Introducción a la creación de perfiles de memoria y CPU de Go
- Resolver el error "no admite la indexación" en un programa Go
- Medir el tiempo de ejecución en un programa Go
- Creación de un rastreador web con Go para detectar títulos duplicados
- Siga las mejores prácticas: ¿puntero o receptores de valor?
- Siga las mejores prácticas: ¿Debería utilizar un método o una función?
- Ir a estructuras de datos: Establecer
- Hoja de referencia de Go Maps
- Genere implementaciones para tipos genéricos en Go
- Ir a estructuras de datos: diccionario
- Ir a estructuras de datos: tabla hash
- Implementar oyentes de eventos en canales de paso
- Ir a estructuras de datos: apilar
- Ir a estructuras de datos: cola
- Ir a estructuras de datos: árbol de búsqueda binaria
- Ir a estructuras de datos: gráfico
- Ir a estructuras de datos: lista vinculada
- La guía completa de Go Data Structures
- Comparación de valores de Go
- ¿Go está orientado a objetos?
- Trabajar con una base de datos SQL en Go
- Usar variables de entorno en Go
- Ir al tutorial: API REST respaldada por PostgreSQL
- Habilitación de CORS en un servidor web Go
- Implementación de una aplicación Go en un contenedor Docker
- Por qué Go es un lenguaje poderoso para aprender como desarrollador PHP
- Ve, elimina el carácter de nueva línea io.Reader.ReadString
- Ir, cómo ver los cambios y reconstruir su programa
- Ve, cuenta los meses desde una fecha
- Acceder a los parámetros HTTP POST en Go