Coding a Hash Table in Golang

Hash Tables stand at the heart of key-value stores. A Hash table is a data structure used to store key-value pairs, allowing for fast lookup of values by computing a hash for each key and using it as an index into an underlying array.

Below are two approaches:

1. Custom HashTable Implementation

Implementing from scratch offers a deep dive into hashing functions, collision handling (here using separate chaining with linked lists), and resizing strategies.

package main

import (
  "fmt"
)

const ArraySize = 7

type HashTable struct {
  array [ArraySize]*bucket
}

type bucketNode struct {
  key  string
  next *bucketNode
}

type bucket struct {
  head *bucketNode
}

func (h *HashTable) Insert(key string) {
  index := hash(key)
  h.array[index].insert(key)
}

func (h *HashTable) Search(key string) bool {
  index := hash(key)
  return h.array[index].search(key)
}

func (h *HashTable) Delete(key string) {
  index := hash(key)
  h.array[index].delete(key)
}

func (b *bucket) insert(k string) {
  if !b.search(k) {
    newNode := &bucketNode{key: k, next: b.head}
    b.head = newNode
  }
}

func (b *bucket) search(k string) bool {
  current := b.head
  for current != nil {
    if current.key == k {
      return true
    }
    current = current.next
  }
  return false
}

func (b *bucket) delete(k string) {
  if b.head == nil {
    return
  }
  if b.head.key == k {
    b.head = b.head.next
    return
  }
  prev := b.head
  for prev.next != nil {
    if prev.next.key == k {
      prev.next = prev.next.next
      return
    }
    prev = prev.next
  }
}

func hash(key string) int {
  sum := 0
  for _, v := range key {
    sum += int(v)
  }
  return sum % ArraySize
}

func Initialize() *HashTable {
  ht := &HashTable{}
  for i := range ht.array {
    ht.array[i] = &bucket{}
  }
  return ht
}

func main() {
  ht := Initialize()
  ht.Insert("Alice")
  ht.Insert("Bob")
  fmt.Println(ht.Search("Alice")) // true
  fmt.Println(ht.Search("Eve"))   // false
}

2. Using Go Maps

Go's built-in maps provide a simple and efficient hash table implementation out-of-the-box, behaving idiomatically:

package main

import (  
  "fmt"
)

func main() {
  m := make(map[string]int)
  m["Alice"] = 30
  m["Bob"] = 25

  fmt.Println(m["Alice"]) // 30
  delete(m, "Bob")
  fmt.Println(m["Bob"])   // 0 (zero value)
}