Just a few weeks until the 2021 JavaScript Full-Stack Bootcamp opens.
Signup to the waiting list!
An Hash Table is a hash implementation of a hash table data structure. Instead of using a custom key to store the value in a map, the data structure performs a hashing function on the key to return the exact index of an item in the array.
Implementation
Internally the hash table will be represented with a map
type, and I’ll expose the
Put()
Remove()
Get()
Size()
methods.
I’ll create a ValueHashtable
generic type, concurrency safe, that can generate hash tables containing any type. Keys can be any type as long as it implements the Stringer
interface. By running go generate
the code will create a type-specific Hash Table implementation, encapsulating the actual value-specific data structure containing the data.
// Package hashtable creates a ValueHashtable data structure for the Item type
package hashtable
import (
"fmt"
"sync"
"github.com/cheekybits/genny/generic"
)
// 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)
}
Tests
The tests describe the usage of the above implementation. Notice that we never interact with the underlying map
type, which might as well be implemented in another way if only Go didn’t provide us a map type already.
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)
}
}
Creating a concrete hash table data structure
You can use this generic implemenation to generate type-specific hash tables, using
//generate a `IntHashtable` hash table of `int` values
genny -in hashtable.go -out hashtable-int.go gen "Value=int"
//generate a `StringHashtable` hash table of `string` values
genny -in hashtable.go -out hashtable-string.go gen "Value=string"
The 2021 JavaScript Full-Stack Bootcamp will start at the end of March 2021. Don't miss this opportunity, signup to the waiting list!
More go tutorials:
- Using NGINX Reverse Proxy to serve Go services
- Making a copy of a struct in Go
- The basics of a Go Web Server
- Sorting a map type in Go
- Go pointers in a nutshell
- Go Tags explained
- Go Date and Time Formatting
- JSON processing with Go
- Go Variadic Functions
- Go Strings Cheat Sheet
- The Go Empty Interface Explained
- Debugging Go with VS Code and Delve
- Named Go returns parameters
- Generating random numbers and strings in Go
- Filesystem Structure of a Go project
- Binary Search Algorithm Implemented in Go
- Using Command Line Flags in Go
- GOPATH Explained
- Build a Command Line app with Go: lolcat
- Building a CLI command with Go: cowsay
- Using Shell Pipes with Go
- Go CLI tutorial: fortune clone
- List the files in a folder with Go
- Use Go to get a list of repositories from GitHub
- Go, append a slice of strings to a file
- Go, convert a string to a bytes slice
- Visualize your local Git contributions with Go
- Getting started with Go CPU and memory profiling
- Solving the "does not support indexing" error in a Go program
- Measuring execution time in a Go program
- Building a Web Crawler with Go to detect duplicate titles
- Go Best Practices: Pointer or value receivers?
- Go Best Practices: Should you use a method or a function?
- Go Data Structures: Set
- Go Maps Cheat Sheet
- Generate implementations for generic types in Go
- Go Data Structures: Dictionary
- Go Data Structures: Hash Table
- Implement Events Listeners in Go through Channels
- Go Data Structures: Stack
- Go Data Structures: Queue
- Go Data Structures: Binary Search Tree
- Go Data Structures: Graph
- Go Data Structures: Linked List
- The complete guide to Go Data Structures
- Comparing Go Values
- Is Go object oriented?
- Working with a SQL Database in Go
- Using environment variables in Go
- Go tutorial: REST API backed by PostgreSQL
- Enabling CORS on a Go Web Server
- Deploying a Go Application in a Docker Container
- Why Go is a powerful language to learn as a PHP developer
- Go, remove the io.Reader.ReadString newline char
- Go, how to watch changes and rebuild your program
- Go, count the months since a date
- Accessing HTTP POST parameters in Go