Go data structure: hash table

Analysis and Implementation of Hash Table Data Structure in Go

The hash table is a hash implementation of the data structure of the hash table. The data structure does not use a custom key to store the value in the map, but performs a hash function on the key to return the exact index of the item in the array.

carried out

Internally, the hash table will usemapType, I will expose

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

method.

I will create aValueHashtableGeneric type, concurrency safety, can generate hash table containing any type. The key can be of any type, as long as it implementsStringerinterface. By runninggo generateThis code will create a type-specific hash table implementation, encapsulating the actual value-specific data structure that contains the data.

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

test

These tests describe the usage of the above implementation. Please note that we never interact with the basemapType, if only Go has not yet provided us with a map type, it can also be implemented in other ways.

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

Create a specific hash table data structure

You can use the following general implementation to generate a type-specific hash table by:

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


More tutorials: