Basic Hash Table Implementation in Go

 


    package main

    import (
        "fmt"
        "sync"
    )

    // Entry represents a key-value pair in the hash table.
    type Entry struct {
        Key   string
        Value string
    }

    // HashTable represents the hash table structure.
    type HashTable struct {
        buckets [][]Entry
        mu      sync.Mutex
        size    int
    }

    // NewHashTable creates a new hash table with the specified size.
    func NewHashTable(size int) *HashTable {
        return &HashTable{
            buckets: make([][]Entry, size),
            size:    size,
        }
    }

    // hash function generates an index for a given key.
    func (ht *HashTable) hash(key string) int {
        var hash int
        for _, char := range key {
            hash += int(char)
        }
        return hash % ht.size
    }

    // Put inserts a key-value pair into the hash table.
    func (ht *HashTable) Put(key string, value string) {
        ht.mu.Lock()
        defer ht.mu.Unlock()
        index := ht.hash(key)
        for i, entry := range ht.buckets[index] {
            if entry.Key == key {
                ht.buckets[index][i].Value = value
                return
            }
        }
        ht.buckets[index] = append(ht.buckets[index], Entry{Key: key, Value: value})
    }

    // Get retrieves the value for a given key from the hash table.
    func (ht *HashTable) Get(key string) (string, bool) {
        ht.mu.Lock()
        defer ht.mu.Unlock()
        index := ht.hash(key)
        for _, entry := range ht.buckets[index] {
            if entry.Key == key {
                return entry.Value, true
            }
        }
        return "", false
    }

    // Remove deletes a key-value pair from the hash table.
    func (ht *HashTable) Remove(key string) {
        ht.mu.Lock()
        defer ht.mu.Unlock()
        index := ht.hash(key)
        for i, entry := range ht.buckets[index] {
            if entry.Key == key {
                ht.buckets[index] = append(ht.buckets[index][:i], ht.buckets[index][i+1:]...)
                return
            }
        }
    }

    // Main function to demonstrate the hash table.
    func main() {
        ht := NewHashTable(10)

        ht.Put("name", "Alice")
        ht.Put("age", "30")
        ht.Put("city", "New York")

        if value, found := ht.Get("name"); found {
            fmt.Println("Name:", value)
        }

        ht.Remove("age")

        if _, found := ht.Get("age"); !found {
            fmt.Println("Age entry not found.")
        }
    }
    

Program Structure Explanation

The program defines a basic hash table with essential functionalities:

  • Entry struct: Represents a key-value pair.
  • HashTable struct: Contains a slice of buckets (each bucket is a slice of entries), a mutex for concurrent access, and the size of the table.
  • NewHashTable function: Initializes a new hash table with a specified size.
  • hash function: Computes the index for a given key based on the sum of its characters, modulo the size of the table.
  • Put method: Inserts a new key-value pair or updates the value if the key already exists.
  • Get method: Retrieves the value associated with a key, returning a boolean indicating success.
  • Remove method: Deletes a key-value pair from the hash table.
  • main function: Demonstrates how to use the hash table by adding, retrieving, and removing entries.

 

Explanation of the Code:

  1. Data Structures:
    • Entry: Represents each key-value pair in the hash table.
    • HashTable: Contains a slice of buckets, a mutex for safe concurrent access, and the table’s size.
  2. Functions:
    • NewHashTable: Initializes the hash table with a specified size.
    • hash: Computes the index based on the key.
    • Put: Adds or updates a key-value pair.
    • Get: Retrieves a value by key.
    • Remove: Deletes a key-value pair.
  3. Concurrency:
    • Uses a mutex (sync.Mutex) to ensure that the hash table can be safely accessed by multiple goroutines.
  4. Main Function:
    • Demonstrates adding, retrieving, and removing elements in the hash table.

This implementation provides a simple but effective way to understand hash tables in Go, including basic operations and thread safety.

Leave a Reply

Your email address will not be published. Required fields are marked *