Structures de données Go: table de hachage

Analyse et implémentation de la structure de données de la table de hachage dans Go

Une table de hachage est une implémentation de hachage d'une structure de données de table de hachage. Au lieu d'utiliser une clé personnalisée pour stocker la valeur dans une carte, la structure de données exécute une fonction de hachage sur la clé pour renvoyer l'index exact d'un élément du tableau.

Mise en œuvre

En interne, la table de hachage sera représentée par unmaptapez, et je vais exposer le

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

méthodes.

Je vais créer unValueHashtabletype générique, sécurisé pour la concurrence, qui peut générer des tables de hachage contenant n'importe quel type. Les clés peuvent être de n'importe quel type tant qu'elles implémentent leStringerinterface. En exécutantgo generatele code créera une implémentation de table de hachage spécifique au type, encapsulant la structure de données spécifique à la valeur réelle contenant les données.

// 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) }

Des tests

Les tests décrivent l'utilisation de l'implémentation ci-dessus. Notez que nous n'interagissons jamais avec le sous-jacentmaptype, qui pourrait tout aussi bien être implémenté d'une autre manière si seulement Go ne nous fournissait pas déjà un type de carte.

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) } }

Création d'une structure de données de table de hachage concrète

Vous pouvez utiliser cette implémentation générique pour générer des tables de hachage spécifiques au type, en utilisant

//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”


Plus de tutoriels go: