Hash Table Implementation in Golang

1. Introduction

A Hash Table is a data structure that provides constant time average complexity for search, insert, and delete operations. It uses a hash function to compute an index into an array in which an element will be inserted or searched. Collision handling is a significant part of hash table design, and there are various methods to deal with it. One of the popular methods is chaining, where each cell of the hash table points to a linked list of records with the same hash.

2. Implementation Steps

1. Define a KeyValuePair structure to store the key-value pairs.

2. Implement a HashTable structure that will contain an array of linked lists.

3. Implement a simple hash function.

4. Implement methods for insertion (Put), retrieval (Get), and deletion (Delete).

3. Implementation in Golang

package main
import (
	"fmt"
	"linkedlist"
)
type KeyValuePair struct {
	Key   string
	Value string
}
type HashTable struct {
	size  int
	table []*linkedlist.LinkedList
}
func NewHashTable(size int) *HashTable {
	return &HashTable{
		size:  size,
		table: make([]*linkedlist.LinkedList, size),
	}
}
func (h *HashTable) hashFunction(key string) int {
	sum := 0
	for _, v := range key {
		sum += int(v)
	}
	return sum % h.size
}
func (h *HashTable) Put(key, value string) {
	index := h.hashFunction(key)
	if h.table[index] == nil {
		h.table[index] = linkedlist.NewLinkedList()
	}
	node := &linkedlist.Node{Value: KeyValuePair{Key: key, Value: value}}
	h.table[index].Append(node)
}
func (h *HashTable) Get(key string) string {
	index := h.hashFunction(key)
	list := h.table[index]
	for node := list.Head; node != nil; node = node.Next {
		if node.Value.(KeyValuePair).Key == key {
			return node.Value.(KeyValuePair).Value
		}
	}
	return ""
}
func (h *HashTable) Delete(key string) {
	index := h.hashFunction(key)
	list := h.table[index]
	for node := list.Head; node != nil; node = node.Next {
		if node.Value.(KeyValuePair).Key == key {
			list.Delete(node)
			return
		}
	}
}
func main() {
	hashTable := NewHashTable(10)
	hashTable.Put("name", "John")
	hashTable.Put("age", "25")
	fmt.Println("Name:", hashTable.Get("name"))
	fmt.Println("Age:", hashTable.Get("age"))
	hashTable.Delete("name")
	fmt.Println("Name after delete:", hashTable.Get("name"))
}

Output:

Name: John
Age: 25
Name after delete:

Explanation:

1. KeyValuePair structure represents the key-value pair to be stored in the hash table.

2. HashTable structure represents the actual hash table containing an array of linked lists, which is a common approach for handling collisions using chaining.

3. NewHashTable initializes the hash table with a given size.

4. The hashFunction computes an index for a given key. This is a simple hash function based on the ASCII values of the characters in the key.

5. Put method inserts a key-value pair into the hash table.

6. Get method retrieves the value associated with a key from the hash table.

7. Delete method removes a key-value pair from the hash table.

8. The main function demonstrates the use of the hash table, showing the insertion, retrieval, and deletion of key-value pairs.

The Hash Table provides efficient search, insert, and delete operations. However, the choice of the hash function and collision resolution technique can significantly affect its performance.