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

Basic Operations in Hash Table

Explore the fundamental operations of hash tables including insertion, search, and deletion using Python implementations. Learn how each operation works by hashing keys to array indices and handling data efficiently. This lesson helps you understand the underlying mechanics and complexity analysis of these core hash table methods.

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 array. 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 array called table. Each position in this array represents one slot in the hash table and can store either None or a (key, value) pair.

The class also includes a helper method called _hash(), which applies Python’s built-in hash() function to a key and then uses the modulo operator to convert the result into a valid array index.

Python 3.14.0
class HashTable:
    def __init__(self, size=10):
        # Total number of slots in the table
        self.size = size
        
        # Single array to store (key, value) pairs
        self.table = [None] * size
    
    def _hash(self, key):
        # Compute an index using Python's built-in hash function
        return hash(key) % self.size
A hash table class

Each index in self.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 arrays.

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.

Python implementation

The following method implements the insertion operation in the hash table class:

Python 3.14.0
def insert(self, key, value):
    # Compute the index for the key
    index = self._hash(key)
    
    # If the slot is empty, insert the new key-value pair
    if self.keys[index] is None:
        self.keys[index] = key
        self.values[index] = value
        return
    
    # If the key already exists, update its value
    if self.keys[index] == key:
        self.values[index] = value
        return
    
    # A different key is already stored at this index
    raise Exception("Collision detected - collision handling required")
Insertion in hash tables

This method first computes the array 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) ...