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:
- 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.
- 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.
- Concurrency:
- Uses a mutex (
sync.Mutex
) to ensure that the hash table can be safely accessed by multiple goroutines.
- Uses a mutex (
- 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.