Aprenda Creating Custom Hash Tables

Deslize para mostrar o menu

Defining a Custom Hash Table in Go

A hash table is a data structure that stores key-value pairs for efficient lookup, insertion, and deletion. In Go, you can create a custom hash table by defining a struct and using an underlying data structure, such as a slice of buckets, to store the entries.

Struct Definition

You start by defining an entry struct to hold a key-value pair. Then, create a HashTable struct to manage the hash table’s buckets and size.

// Entry holds a key-value pair.
type entry struct {
    key   string
    value interface{}
    next  *entry
}

// HashTable manages an array of buckets.
type HashTable struct {
    buckets []*entry
    size    int
}

Underlying Data Structure

The buckets field is a slice of pointers to entry structs;
Each bucket stores entries that hash to the same index, handling collisions using a linked list;
The size field tracks the number of buckets.

This design allows you to efficiently store and retrieve key-value pairs by hashing the key to determine the correct bucket. Each bucket contains a linked list to handle keys that collide (produce the same hash index).

You can expand this structure by adding methods for common operations, such as Put, Get, and Delete. The next steps include implementing a hash function and these methods to complete your custom hash table.

main.go


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
            
package main

import (
	"fmt"
)

// HashTable is a custom hash table implementation using separate chaining.
type HashTable struct {
	buckets [][]entry
	size    int
}

type entry struct {
	key   string
	value int
}

// NewHashTable initializes a new HashTable with the given number of buckets.
func NewHashTable(size int) *HashTable {
	buckets := make([][]entry, size)
	return &HashTable{
		buckets: buckets,
		size:    size,
	}
}

// hash calculates a simple hash value for a given key.
func (ht *HashTable) hash(key string) int {
	hash := 0
	for i := 0; i < len(key); i++ {
		hash = (hash*31 + int(key[i])) % ht.size
	}
	return hash
}

// Put adds a key-value pair to the hash table.
func (ht *HashTable) Put(key string, value int) {
	idx := ht.hash(key)
	for i, e := range ht.buckets[idx] {
		if e.key == key {
			// Update existing entry
			ht.buckets[idx][i].value = value
			return
		}
	}
	// Add new entry
	ht.buckets[idx] = append(ht.buckets[idx], entry{key, value})
}

// Get retrieves a value for a given key.
func (ht *HashTable) Get(key string) (int, bool) {
	idx := ht.hash(key)
	for _, e := range ht.buckets[idx] {
		if e.key == key {
			return e.value, true
		}
	}
	return 0, false
}

func main() {
	ht := NewHashTable(8)

	ht.Put("apple", 5)
	ht.Put("banana", 12)
	ht.Put("orange", 8)

	value, found := ht.Get("banana")
	if found {
		fmt.Println("banana:", value)
	} else {
		fmt.Println("banana not found")
	}

	value, found = ht.Get("grape")
	if found {
		fmt.Println("grape:", value)
	} else {
		fmt.Println("grape not found")
	}
}

Inserting Key-Value Pairs into a Custom Hash Table

To store data in a custom hash table, you need to insert key-value pairs. This process involves two main steps: hashing the key to find the correct bucket and handling any collisions that may occur.

Hashing the Key

Use a hash function to convert the key into an integer;
The hash function should distribute keys uniformly to minimize collisions;
Compute the index by taking the remainder of the hash value divided by the number of buckets (using the modulo operator);
Example: if your hash table has 10 buckets and the hash function returns 23 for a key, the index is 23 % 10 = 3.

Collision Handling

Collisions happen when two keys hash to the same index. You need a strategy to handle them. Common methods include:

Chaining: store a linked list or slice at each bucket; add new key-value pairs to the list if a collision occurs;
Open addressing: find another open bucket using a probing sequence if the original bucket is occupied; common methods are linear probing or quadratic probing.

Example: Chaining Approach

Suppose you use chaining for collision handling. When inserting a key-value pair:

Hash the key to get the bucket index;
Check if the bucket already contains a list;
If the list exists, search for the key. If found, update the value; if not, append the new key-value pair;
If the bucket is empty, create a new list and add the pair.

This approach ensures your hash table can store multiple items that hash to the same bucket, maintaining fast access and insertion times.

main.go


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
            
package main

import (
	"fmt"
)

type entry struct {
	key   string
	value string
	next  *entry
}

type HashTable struct {
	buckets []*entry
	size    int
}

func NewHashTable(size int) *HashTable {
	buckets := make([]*entry, size)
	return &HashTable{buckets: buckets, size: size}
}

func (h *HashTable) hash(key string) int {
	hash := 0
	for i := 0; i < len(key); i++ {
		hash = (31*hash + int(key[i])) % h.size
	}
	return hash
}

func (h *HashTable) Insert(key, value string) {
	idx := h.hash(key)
	current := h.buckets[idx]
	for current != nil {
		if current.key == key {
			current.value = value
			return
		}
		current = current.next
	}
	newEntry := &entry{key: key, value: value, next: h.buckets[idx]}
	h.buckets[idx] = newEntry
}

func (h *HashTable) Get(key string) (string, bool) {
	idx := h.hash(key)
	current := h.buckets[idx]
	for current != nil {
		if current.key == key {
			return current.value, true
		}
		current = current.next
	}
	return "", false
}

func main() {
	ht := NewHashTable(10)

	ht.Insert("apple", "red")
	ht.Insert("banana", "yellow")
	ht.Insert("grape", "purple")

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

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

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

Retrieving Values by Key

To retrieve a value from your custom hash table, you use the key associated with that value. The hash table uses a hash function to compute the index where the key-value pair is stored.

Steps to Retrieve a Value

Provide the key you want to search for;
The hash function computes the index for this key;
The hash table checks the bucket at that index;
If the key exists, the value is returned;
If the key does not exist, the hash table should indicate that the key was not found.

Example: Retrieving a Value

Suppose your hash table stores user ages by username. To get the age for the username "alice", you would use the Get method:

age, found := hashTable.Get("alice")
if found {
    fmt.Println("Alice's age:", age)
} else {
    fmt.Println("Key not found")
}

Handling Missing Keys

When a key is not found, always return a clear indication. In Go, you typically return a second boolean value from the Get method. This boolean is true if the key was found, and false if not. This approach prevents confusion between a missing key and a value that could be the zero value for the data type (such as 0 for integers).

Key points:

Always check the boolean result when retrieving values;
Handle missing keys gracefully by providing a default message or behavior.

This method ensures your custom hash table is robust and user-friendly.

main.go


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
            
package main

import (
	"fmt"
)

type entry struct {
	key   string
	value string
	next  *entry
}

type HashTable struct {
	buckets []*entry
	size    int
}

func NewHashTable(size int) *HashTable {
	buckets := make([]*entry, size)
	return &HashTable{
		buckets: buckets,
		size:    size,
	}
}

func (ht *HashTable) hash(key string) int {
	hash := 0
	for i := 0; i < len(key); i++ {
		hash = (hash*31 + int(key[i])) % ht.size
	}
	return hash
}

func (ht *HashTable) Put(key, value string) {
	idx := ht.hash(key)
	current := ht.buckets[idx]
	for current != nil {
		if current.key == key {
			current.value = value
			return
		}
		current = current.next
	}
	newEntry := &entry{key: key, value: value, next: ht.buckets[idx]}
	ht.buckets[idx] = newEntry
}

func (ht *HashTable) Get(key string) (string, bool) {
	idx := ht.hash(key)
	current := ht.buckets[idx]
	for current != nil {
		if current.key == key {
			return current.value, true
		}
		current = current.next
	}
	return "", false
}

func main() {
	ht := NewHashTable(8)

	ht.Put("apple", "red")
	ht.Put("banana", "yellow")
	ht.Put("grape", "purple")

	value, found := ht.Get("banana")
	if found {
		fmt.Println("banana:", value)
	} else {
		fmt.Println("banana not found")
	}

	value, found = ht.Get("cherry")
	if found {
		fmt.Println("cherry:", value)
	} else {
		fmt.Println("cherry not found")
	}
}

Deleting Key-Value Pairs from a Custom Hash Table

To remove a key-value pair from your custom hash table, follow these steps:

Compute the hash for the key to find the correct bucket;
Search the bucket for the key;
If the key exists, remove the key-value pair from the bucket;
If the key is not found, do nothing.

Here is a simple example showing how to implement the Delete method for a custom hash table in Go:

func (h *HashTable) Delete(key string) {
    index := h.hash(key)
    bucket := h.buckets[index]
    for i, kv := range bucket {
        if kv.key == key {
            // Remove the key-value pair from the bucket
            h.buckets[index] = append(bucket[:i], bucket[i+1:]...)
            return
        }
    }
}

The Delete method first calculates the hash index for the key using the hash function.
It then iterates through the bucket at that index, searching for the key.
If the key is found, it uses slicing to remove the key-value pair from the bucket.
If the key does not exist, the method simply returns without making changes.

This approach ensures that your hash table stays accurate and does not retain unnecessary data after a key-value pair is deleted.

main.go


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
            
package main

import (
	"fmt"
)

type entry struct {
	key   string
	value string
	next  *entry
}

type HashTable struct {
	buckets []*entry
	size    int
}

func NewHashTable(size int) *HashTable {
	return &HashTable{
		buckets: make([]*entry, size),
		size:    size,
	}
}

func (ht *HashTable) hash(key string) int {
	hash := 0
	for _, ch := range key {
		hash = (hash*31 + int(ch)) % ht.size
	}
	return hash
}

func (ht *HashTable) Put(key, value string) {
	idx := ht.hash(key)
	current := ht.buckets[idx]
	for current != nil {
		if current.key == key {
			current.value = value
			return
		}
		current = current.next
	}
	newEntry := &entry{key: key, value: value, next: ht.buckets[idx]}
	ht.buckets[idx] = newEntry
}

func (ht *HashTable) Get(key string) (string, bool) {
	idx := ht.hash(key)
	current := ht.buckets[idx]
	for current != nil {
		if current.key == key {
			return current.value, true
		}
		current = current.next
	}
	return "", false
}

func (ht *HashTable) Delete(key string) bool {
	idx := ht.hash(key)
	current := ht.buckets[idx]
	var prev *entry
	for current != nil {
		if current.key == key {
			if prev == nil {
				ht.buckets[idx] = current.next
			} else {
				prev.next = current.next
			}
			return true
		}
		prev = current
		current = current.next
	}
	return false
}

func main() {
	ht := NewHashTable(8)

	ht.Put("apple", "red")
	ht.Put("banana", "yellow")
	ht.Put("grape", "purple")

	fmt.Println("Before deletion:")
	if val, ok := ht.Get("banana"); ok {
		fmt.Println("banana:", val)
	}

	deleted := ht.Delete("banana")
	fmt.Println("Deleted banana:", deleted)

	fmt.Println("After deletion:")
	if _, ok := ht.Get("banana"); !ok {
		fmt.Println("banana not found")
	}
	if val, ok := ht.Get("apple"); ok {
		fmt.Println("apple:", val)
	}
	if val, ok := ht.Get("grape"); ok {
		fmt.Println("grape:", val)
	}
}

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 1. Capítulo 9

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Seção 1. Capítulo 9