Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Go

Basic Operations in Hash Table

Explore the fundamental operations of hash tables: insertion, search, and deletion. Understand how keys are indexed using hash functions, how data is stored and retrieved efficiently, and learn the time and space complexity involved. This lesson uses Go to implement these operations and highlights the importance of handling collisions and proper deletion.

We'll cover the following...

After understanding what a hash table is and how a hash function works, the next step is to study the three fundamental operations that make hash tables useful in practice: insertion, search, and deletion. These operations allow data to be stored, retrieved, and removed efficiently using a key.

In a hash table, each operation begins in the same way: the key is passed through the hash function to compute an index in the underlying slice. Once that index is known, the table can access the corresponding location directly.

Hash table structure

To understand how insertion, search, and deletion work, it is helpful to first look at the internal structure of a simple hash table. In this lesson, the hash table is implemented using a single slice called table. Each position in this slice represents one slot in the hash table and can store either nil or a (key, value) entry.

The struct also includes a helper method called hash(), which computes a simple deterministic hash value for a string key and then uses the modulo operator to convert the result into a valid slice index.

Go (1.24.2)
type Entry struct {
	key   string
	value int
}
type HashTable struct {
	size  int
	table []*Entry
}
func NewHashTable(size int) *HashTable {
	return &HashTable{
		size:  size,
		table: make([]*Entry, size),
	}
}
func (h *HashTable) hash(key string) int {
	// Compute an index using a simple deterministic hash function
	hashValue := 0
	for i, ch := range key {
		hashValue += (i + 1) * int(ch)
	}
	return hashValue % h.size
}
A hash table struct

Each index in table represents one slot in the hash table. When a key is inserted, searched for, or deleted, the hash function determines which slot should be used. This simple structure provides the foundation for the three basic operations of hash tables.

The insertion operation

The insertion operation adds a new key-value pair to the hash table.

When a key is inserted, the hash function computes the index where the pair should be stored. The key and value are then placed at that position in the underlying slice.

If the key already exists in the table, insertion usually updates its associated value instead of creating a duplicate entry. This ensures that each key appears at most once in the table.

Steps for insertion

The insertion process can be described as the following sequence of steps:

  1. Compute the hash of the key to determine the index.

  2. If the target location is empty, store the new key-value pair there.

  3. Otherwise, if the target location is not empty:

    1. If the same key is already present, update its value.

    2. If a different key is already present at that index, a collision has occurred.

Let's look at the following interactive visualizer for a better understanding of insertion in hash tables.

Go implementation

The following method implements the insertion operation for the hash table struct:

Go (1.24.2)
func (h *HashTable) Insert(key string, value int) error {
	// Compute the index for the key
	index := h.hash(key)
	// If the slot is empty, insert the new key-value pair
	if h.table[index] == nil {
		h.table[index] = &Entry{key: key, value: value}
		return nil
	}
	// If the key already exists, update its value
	if h.table[index].key == key {
		h.table[index].value = value
		return nil
	}
	// A different key is already stored at this index
	return fmt.Errorf("collision detected - collision handling required")
}
Insertion in hash tables

This method first computes the slice index using the hash function. If that location is empty, the key and value are stored there. If the same key is already present, the old value is replaced by the new one. If the location contains a different key, the insertion fails because this simplified implementation does not yet handle collisions. Collisions will be discussed later in the chapter.

Time complexity

The insertion operation involves several steps.

  • Computing the hash value of the key takes O(k)O(k) ...