Hash Tables

A hash table (or hash map) is a data structure that provides fast insertion, deletion, and lookup of key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Using Go's map Data Structure

Go provides a built-in map type, which makes it very easy to use hash tables. Here's an example of basic operations with Go's map:

go
package main

import (
    "fmt"
)

func main() {
    // Create a new map
    hashMap := make(map[string]int)

    // Insert key-value pairs
    hashMap["apple"] = 5
    hashMap["banana"] = 3
    hashMap["cherry"] = 8

    // Retrieve a value
    appleCount := hashMap["apple"]
    fmt.Println("Apple count:", appleCount)

    // Update a value
    hashMap["apple"] = 10
    fmt.Println("Updated apple count:", hashMap["apple"])

    // Check if a key exists
    if _, exists := hashMap["banana"]; exists {
        fmt.Println("Banana exists in the hash map")
    }

    // Delete a key
    delete(hashMap, "cherry")
    fmt.Println("Cherry deleted")

    // Iterate over all key-value pairs
    for key, value := range hashMap {
        fmt.Printf("%s: %d\n", key, value)
    }
}

3. Implementing a Custom Hash Table

While Go's map is highly optimized, understanding how to implement a hash table can be very educational. Here's a simple custom implementation:

go
package main

import (
    "fmt"
)

const ArraySize = 7

// HashTable structure
type HashTable struct {
    array [ArraySize]*bucket
}

// Bucket structure
type bucket struct {
    head *bucketNode
}

// BucketNode structure
type bucketNode struct {
    key  string
    value int
    next *bucketNode
}

// Insert a key-value pair
func (h *HashTable) Insert(key string, value int) {
    index := hash(key)
    h.array[index].insert(key, value)
}

// Search for a value by key
func (h *HashTable) Search(key string) (int, bool) {
    index := hash(key)
    return h.array[index].search(key)
}

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

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

// Insert a key-value pair into a bucket
func (b *bucket) insert(key string, value int) {
    if b.head == nil {
        b.head = &bucketNode{key: key, value: value}
        return
    }
    currentNode := b.head
    for currentNode.next != nil {
        if currentNode.key == key {
            currentNode.value = value
            return
        }
        currentNode = currentNode.next
    }
    if currentNode.key == key {
        currentNode.value = value
    } else {
        currentNode.next = &bucketNode{key: key, value: value}
    }
}

// Search for a value in a bucket by key
func (b *bucket) search(key string) (int, bool) {
    currentNode := b.head
    for currentNode != nil {
        if currentNode.key == key {
            return currentNode.value, true
        }
        currentNode = currentNode.next
    }
    return 0, false
}

// Delete a key-value pair from a bucket
func (b *bucket) delete(key string) {
    if b.head == nil {
        return
    }
    if b.head.key == key {
        b.head = b.head.next
        return
    }
    previousNode := b.head
    for previousNode.next != nil {
        if previousNode.next.key == key {
            previousNode.next = previousNode.next.next
            return
        }
        previousNode = previousNode.next
    }
}

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

func main() {
    hashTable := Init()
    hashTable.Insert("apple", 5)
    hashTable.Insert("banana", 3)
    hashTable.Insert("cherry", 8)

    value, found := hashTable.Search("apple")
    if found {
        fmt.Println("Apple count:", value)
    } else {
        fmt.Println("Apple not found")
    }

    hashTable.Delete("cherry")
    value, found = hashTable.Search("cherry")
    if found {
        fmt.Println("Cherry count:", value)
    } else {
        fmt.Println("Cherry not found")
    }
}

Explanation:

1. HashTable Structure: Contains an array of buckets.
2. Bucket Structure: Each bucket is a linked list of bucket nodes.
3. BucketNode Structure: Represents each key-value pair.
4. Insert: Adds a key-value pair to the appropriate bucket.
5. Search: Finds the value associated with a key.
6. Delete: Removes a key-value pair from the bucket.
7. Hash Function: Simple hash function based on the sum of character codes modulo the array size.
8. Init Function: Initializes the hash table with empty buckets.

This custom implementation provides a basic understanding of how hash tables work under the hood.