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: