Ir a estructuras de datos: tabla hash

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 unmaptipo, y expondré el

  • Put()
  • Remove()
  • Get()
  • Size()

métodos.

Voy a crear unValueHashtabletipo 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 laStringerinterfaz. Mediante la ejecucióngo generateel 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 subyacentemaptype, 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:


Tech Wiki en línea!