You've been using Go's built-in map since day one of this course. It's incredibly efficient, but it's also a "black box." To really understand how data structures work under the hood, we need to build one ourselves. Today, we're implementing a Hash Table from scratch.

The Mailbox Mental Model

Imagine a wall of 100 mailboxes in a lobby. You have a list of people (your keys) and the letters you want to give them (your values). You can't just throw letters randomly into boxes; you need a system to remember where you put them.

So, you create a rule: "Take the person's name, add up the alphabetical position of each letter, and divide by 100. The remainder is their mailbox number." This rule is your hash function. If "Alice" hashes to box 12, you put her letter there. When you need to find Alice's letter later, you don't search every box; you just run her name through the rule again, get 12, and go straight to that box.

But here's the problem: what if "Bob" also hashes to box 12? That's a collision. To fix this, you don't kick Alice out; you just put Bob's letter in the same box, sitting on top of Alice's. In software terms, we call this "chaining"—each mailbox actually holds a small list of entries.

Translating the Analogy to Go

To build this, we need three things: a way to store the entries, a way to handle those collisions, and the hashing logic itself. I'll use a simple slice of slices to represent our mailboxes and the lists inside them.

package main

import (
	"fmt"
)

// Entry represents a single key-value pair
type Entry struct {
	Key   string
	Value string
}

// HashTable represents the overall structure
type HashTable struct {
	buckets [][]Entry
	size    int
}

// NewHashTable initializes a table with a fixed number of buckets
func NewHashTable(size int) *HashTable {
	return &HashTable{
		buckets: make([][]Entry, size),
		size:    size,
	}
}

Turning Strings into Indices

In a production environment, you'd use a library like hash/fnv. But for this lesson, I want you to see the raw logic. We'll create a simple function that sums the bytes of the string. I've added a modulo operation at the end to ensure the result always fits within our slice bounds.

func (h *HashTable) hash(key string) int {
	sum := 0
	for _, char := range key {
		sum += int(char)
	}
	return sum % h.size
}

Handling the Put and Get Operations

When we Put a value, we first find the bucket. If the key already exists in that bucket, we update the value. If not, we append a new entry. This is where that "chaining" from our mailbox analogy happens.

func (h *HashTable) Put(key, value string) {
	index := h.hash(key)
	bucket := h.buckets[index]

	for i, entry := range bucket {
		if entry.Key == key {
			h.buckets[index][i].Value = value
			return
		}
	}
	h.buckets[index] = append(bucket, Entry{Key: key, Value: value})
}

func (h *HashTable) Get(key string) (string, bool) {
	index := h.hash(key)
	bucket := h.buckets[index]

	for _, entry := range bucket {
		if entry.Key == key {
			return entry.Value, true
		}
	}
	return "", false
}

Why This Matters

You might be thinking, "Why bother when map[string]string exists?" Because understanding this helps you understand time complexity. In a perfect world, a Hash Table gives us O(1) access—constant time. But if your hash function is bad and every single key ends up in the same bucket, your Hash Table effectively becomes a linked list, and performance drops to O(n). When you see a performance degradation in a real-world Go app, it's often because a map is dealing with too many collisions or is triggering an expensive resize operation.

📋 Practical Task

Build a Session Token Store

Using the logic from this lesson, implement a specialized SessionStore. Your task is to build a hash table that stores user session tokens. The requirements are:

• Create a SessionStore struct with a bucket size of 16.
• Implement a SaveSession(token string, userID int) method. Note that the value here is an int, not a string.
• Implement a GetUserID(token string) (int, bool) method to retrieve the user associated with a token.
• Implement a DeleteSession(token string) method that removes an entry from the bucket if it exists. Hint: You'll need to slice out the element from the bucket slice.

Test your implementation by saving three different tokens, deleting one, and verifying that the others are still accessible.