Hash Table Data Structure in Python – Complete Tutorial with Examples

Step-by-Step Explanation

What This Program Does

This program implements a small hash table using separate chaining. Each bucket is the head of a singly linked list, and new entries are inserted at the front of that list.

1. The insert function

def insert(buckets, key, value):
    index = hash_key(key, len(buckets))
    new_node = Node(key, value)
    new_node.next = buckets[index]
    buckets[index] = new_node

Step-by-step:

• hash_key(key, len(buckets)) calculates the bucket index for the given key. The number of buckets is passed so that the result stays within valid indexes.
• Node(key, value) creates a new linked-list node holding the key and its value.
• new_node.next = buckets[index] links the new node to the current first node in that bucket. If the bucket is empty, buckets[index] is None, so new_node.next becomes None.
• buckets[index] = new_node makes the new node the new head of that bucket’s linked list.

So the function always inserts the newest entry at the front of the bucket list. This is a common separate-chaining approach: when multiple keys hash to the same bucket, they are stored in the same linked list.

2. Creating empty buckets

buckets = [None] * 5

This creates an array of five empty buckets:

Bucket 0: None
Bucket 1: None
Bucket 2: None
Bucket 3: None
Bucket 4: None

Each None means that bucket currently has no linked list.

3. Inserting values

insert(buckets, "Alice", 100)
insert(buckets, "Bob", 200)
insert(buckets, "John", 300)
insert(buckets, "Kevin", 400)
insert(buckets, "Kennedy", 500)

For every call:

• The key is hashed to find a bucket index.
• A node is created for the key-value pair.
• The node is linked to the existing bucket head.
• The bucket now points to the new node.

For example, if "Alice" hashes to bucket 2:

Before:

Bucket 2: None

After:

Bucket 2: Alice -> 100 -> None

If "Kevin" later hashes to the same bucket 2:

Bucket 2: Kevin -> 400 -> Alice -> 100 -> None

Kevin appears first because it was inserted at the front.

4. Displaying the hash table

for idx, bucket in enumerate(buckets):
    print(f"Bucket {idx}")

    current = bucket

    while current is not None:
        print(f"    {current.key} -> {current.value}")
        current = current.next

Step-by-step:

• enumerate(buckets) gives both the bucket index and the head node of that bucket.
• print(f"Bucket {idx}") prints the bucket number.
• current = bucket starts traversal at the head of that bucket’s linked list.
• The while loop runs until current becomes None.
• Each node’s key and value are printed.
• current = current.next moves to the next node in the chain.

5. Example output format

The exact bucket positions depend on hash_key(), but the output will look like this:

Bucket 0
    Kennedy -> 500
Bucket 1
Bucket 2
    Kevin -> 400
    Alice -> 100
Bucket 3
    Bob -> 200
Bucket 4
    John -> 300

Buckets that contain None print only their bucket number because their linked list is empty.

Important note

This insert function does not check whether the same key already exists. If you insert "Alice" twice, the program will store two separate Alice nodes in the same bucket instead of updating the original value. A complete hash table usually searches the bucket first and updates the value when the key already exists.

Step-by-Step Explanation

What This Program Does

This program implements an insert-or-update operation for a hash table that uses separate chaining. If the key already exists in its bucket, the function changes its value; otherwise, it creates a new node and inserts it at the front of that bucket’s linked list.

1. insert_or_update Explanation

def insert_or_update(buckets, key, value):
    index = hash_key(key, len(buckets))
    current = buckets[index]

• hash_key(key, len(buckets)) finds the bucket index for the key.
• current = buckets[index] starts at the first node in that bucket’s linked list.
• If the bucket is empty, current is None.

    while current is not None:
        if current.key == key:
            current.value = value
            return
        current = current.next

• The loop checks every node in the bucket.
• If it finds a node whose key matches the input key, it updates that node’s value.
• return stops the function immediately, so no duplicate node is created.
• If the key is not found, current eventually becomes None and the loop ends.

    new_node = Node(key, value)
    new_node.next = buckets[index]
    buckets[index] = new_node

• A new node is created for the key and value.
• new_node.next = buckets[index] links the new node to the previous head of the bucket.
• buckets[index] = new_node makes the new node the new head of the bucket.

This is called insert at front. It is efficient because it does not need to walk to the end of the linked list.

2. Example Execution

buckets = [None] * 5

insert_or_update(buckets, "Alice", 100)
insert_or_update(buckets, "Bob", 200)
insert_or_update(buckets, "Alice", 300)
insert_or_update(buckets, "Kennedy", 400)

Assume "Alice" and "Kennedy" hash to the same bucket, while "Bob" hashes to another bucket.

First call

insert_or_update(buckets, "Alice", 100)

• The bucket is empty.
• A node Alice -> 100 is created.
• It becomes the head of its bucket.

Bucket: Alice -> 100 -> None

Second call

insert_or_update(buckets, "Bob", 200)

• "Bob" hashes to its own bucket.
• The bucket is empty.
• A node Bob -> 200 is created.

Bucket: Bob -> 200 -> None

Third call

insert_or_update(buckets, "Alice", 300)

• "Alice" hashes to the same bucket as before.
• The loop finds the existing Alice node.
• Its value changes from 100 to 300.
• No new node is added.

Bucket: Alice -> 300 -> None

Fourth call

insert_or_update(buckets, "Kennedy", 400)

• "Kennedy" hashes to Alice’s bucket.
• The loop checks Alice, but the key does not match.
• A new node is created and placed at the front.

Bucket: Kennedy -> 400 -> Alice -> 300 -> None

3. Display Loop

for idx, bucket in enumerate(buckets):
    print(f"Buckest {idx}")

    current = bucket
    while current is not None:
        print(f"    {current.key} -> {current.value}")
        current = current.next

• enumerate(buckets) gives the bucket number and its head node.
• current = bucket starts traversal from the bucket head.
• The while loop prints every node in the chain.
• current = current.next moves to the next node.
• When current becomes None, the loop stops.

The output will look like this, depending on the bucket indexes produced by hash_key():

Buckest 0
Buckest 1
    Bob -> 200
Buckest 2
    Kennedy -> 400
    Alice -> 300
Buckest 3
Buckest 4

Key Difference from Plain Insert

A plain insert always adds a new node, even if the key already exists. This function first searches the bucket, so repeated keys are updated rather than duplicated. That behavior matches the usual put operation in a hash map.

Step-by-Step Explanation

What This Program Does

This program shows how to search for a key in a hash table built with separate chaining. get() returns the stored value for a key, while contains_key() uses get() to return True or False.

1. get() explanation

def get(buckets, key):
    index = hash_key(key, len(buckets))
    current = buckets[index]

• hash_key(key, len(buckets)) calculates the bucket index where the key should be stored.
• current = buckets[index] starts at the first node in that bucket’s linked list.
• If the bucket is empty, current is None.

    while current is not None:
        if current.key == key:
            return current.value
        current = current.next

• The loop checks each node in the bucket.
• If current.key == key, the matching node has been found.
• The function immediately returns current.value.
• If the keys do not match, current = current.next moves to the next node.
• If the loop ends without finding the key, the function returns None.

In a separate-chaining hash table, each bucket holds a linked list, and a lookup scans only that bucket’s chain rather than every entry in the table.

2. contains_key() explanation

def contains_key(buckets, key):
    return get(buckets, key) is not None

• It calls get(buckets, key).
• If get() returns a value, the key exists, so the result is True.
• If get() returns None, the key does not exist, so the result is False.

For example:

contains_key(buckets, "Alice")

returns:

True

because "Alice" was inserted earlier.

contains_key(buckets, "David")

returns:

False

because "David" was never inserted.

3. insert() explanation

def insert(buckets, key, value):
    index = hash_key(key, len(buckets))
    new_node = Node(key, value)
    new_node.next = buckets[index]
    buckets[index] = new_node

• The key is hashed to find its bucket index.
• A new node is created with the key and value.
• new_node.next = buckets[index] links the new node to the current head of that bucket.
• buckets[index] = new_node makes the new node the new head of the bucket.

So every insertion places the newest node at the front of its bucket’s linked list.

4. Creating and filling the table

buckets = [None] * 5

This creates five empty buckets:

Bucket 0: None
Bucket 1: None
Bucket 2: None
Bucket 3: None
Bucket 4: None

insert(buckets, "Alice", 100)
insert(buckets, "Bob", 200)
insert(buckets, "John", 300)
insert(buckets, "Kevin", 400)
insert(buckets, "Kennedy", 500)

Each key is hashed to one of the five buckets. If two keys hash to the same bucket, both remain in that bucket as a linked list.

For example, if "Kevin" and "Kennedy" hash to bucket 2, the bucket may look like this:

Bucket 2: Kennedy -> 500 -> Kevin -> 400 -> None

Kennedy appears first because it was inserted after Kevin.

5. Expected output

print("Alice exists:", contains_key(buckets, "Alice"))
print("David exists:", contains_key(buckets, "David"))

The output is:

Alice exists: True
David exists: False

Important limitation

This get() returns None both when the key is missing and when a stored value is actually None. In this program, all stored values are numbers, so that is not a problem. For a more general hash table, it is better to use a separate contains_key() check before calling get().

Step-by-Step Explanation

What This Program Does

This program implements deletion in a hash table that uses separate chaining. It finds the bucket for a key, removes the matching node from that bucket’s linked list, and prints the table before and after deletion.

1. Program structure (delete_by_key)

def delete_by_key(buckets, key):
    index = hash_key(key, len(buckets))
    current = buckets[index]
    previous = None

• hash_key(key, len(buckets)) finds the bucket index for the key.
• current = buckets[index] points to the first node in that bucket’s linked list.
• previous = None means no node has been visited yet.

    while current is not None:
        if current.key == key:

• The loop checks each node in the bucket.
• If current.key == key, the node to delete has been found.

            if previous is None:
                buckets[index] = current.next

If the matching node is the first node in the bucket, the bucket head is changed to the next node. This removes the first node from the chain.

            else:
                previous.next = current.next
            return True

If the matching node is not the first node, the previous node is linked directly to the node after the deleted node. This removes the current node from the middle or end of the chain. The function returns True because deletion succeeded.

        previous = current
        current = current.next
    return False

• If the current node is not a match, previous becomes the current node.
• current moves to the next node.
• If the loop ends without finding the key, the function returns False.

In separate chaining, each bucket contains a linked list, and deletion removes the matching entry from that chain.

2. insert() explanation

def insert(buckets, key, value):
    index = hash_key(key, len(buckets))
    new_node = Node(key, value)
    new_node.next = buckets[index]
    buckets[index] = new_node

• The key is hashed to find its bucket.
• A new node is created with the key and value.
• new_node.next = buckets[index] links the new node to the current bucket head.
• buckets[index] = new_node makes the new node the new head of that bucket.

So new entries are inserted at the front of the bucket’s linked list.

3. print_buckets() explanation

def print_buckets(buckets):
    for idx, bucket in enumerate(buckets):
        print(f"Bucket {idx}")
        current = bucket
        while current is not None:
            print(f"    {current.key} -> {current.value}")
            current = current.next

• enumerate(buckets) gives each bucket index and its head node.
• current = bucket starts at the first node in that bucket.
• The while loop prints every key-value pair in the bucket.
• current = current.next moves to the next node.
• When current becomes None, the loop stops.

4. Example execution

buckets = [None] * 5

insert(buckets, "Mango", 10)
insert(buckets, "Grape", 20)
insert(buckets, "Lemon", 30)
insert(buckets, "Peach", 40)
insert(buckets, "Melon", 50)
insert(buckets, "Guava", 60)

This creates five empty buckets and inserts six fruit entries. The exact bucket positions depend on hash_key().

Assume "Lemon" hashes to bucket 2, and bucket 2 contains:

Before deleting "Lemon":

Bucket 2: [30] -> [10] -> None

Deleting "Lemon"

delete_by_key(buckets, "Lemon")

Step-by-step:

• "Lemon" hashes to bucket 2.
• current points to the first node, Lemon -> 30.
• previous is None.
• The first comparison finds current.key == "Lemon".
• Since previous is None, the program runs: buckets[index] = current.next.
• Bucket 2 now points to Mango -> 10.
• The Lemon node is removed from the chain.
• The function returns True.

After deleting "Lemon":

Bucket 2: [10] -> None

5. Expected output format

The exact output depends on the hash function, but it will look like this:

Before deleting 'Lemon':
Bucket 0
Bucket 1
    Peach -> 40
Bucket 2
    Lemon -> 30
    Mango -> 10
Bucket 3
    Grape -> 20
    Melon -> 50
Bucket 4
    Guava -> 60

After deleting 'Lemon':
Bucket 0
Bucket 1
    Peach -> 40
Bucket 2
    Mango -> 10
Bucket 3
    Grape -> 20
    Melon -> 50
Bucket 4
    Guava -> 60

6. Deletion cases

The time taken depends on the number of nodes in the target bucket. With a good hash function and reasonably short chains, deletion is efficient on average.

Step-by-Step Explanation

What This Program Does

This program separates the search for a key from the actual deletion. Once the target node and its predecessor are found, delete_node_with_predecessor() removes the node by changing only the necessary links.

1. delete_node_with_predecessor() explanation

def delete_node_with_predecessor(buckets, index, target_node, previous_node):
    if previous_node is None:
        buckets[index] = target_node.next

• target_node is the node to delete.
• previous_node is the node immediately before it in the same bucket.
• If previous_node is None, the target node is the first node in the bucket.
• Therefore, the bucket itself must point to the node after the target: buckets[index] = target_node.next.
• This removes the head node from the bucket’s linked list.

    else:
        previous_node.next = target_node.next

• If the target node is not the first node, the previous node must skip over it.
• previous_node.next = target_node.next links the previous node directly to the node after the target.
• The target node is no longer part of the chain.

For a singly linked list, deletion needs the predecessor because the predecessor’s next pointer must be updated.

2. insert() explanation

def insert(buckets, key, value):
    index = hash_key(key, len(buckets))
    new_node = Node(key, value)
    new_node.next = buckets[index]
    buckets[index] = new_node

• The key is hashed to find its bucket index.
• A new node is created with the key and value.
• new_node.next = buckets[index] links the new node to the current first node in the bucket.
• buckets[index] = new_node makes the new node the new head of that bucket.

So every new entry is inserted at the front of its bucket’s linked list.

3. print_buckets() explanation

def print_buckets(buckets):
    for idx, bucket in enumerate(buckets):
        print(f"Bucket {idx}")
        current = bucket
        while current is not None:
            print(f"    {current.key} -> {current.value}")
            current = current.next

• enumerate(buckets) provides the bucket number and the head node.
• current = bucket starts at the first node in that bucket.
• The while loop prints each key-value pair.
• current = current.next moves to the next node.
• The loop stops when current becomes None.

4. Creating and filling the table

buckets = [None] * 5

insert(buckets, "Tiger", 11)
insert(buckets, "Zebra", 22)
insert(buckets, "Panda", 33)
insert(buckets, "Koala", 44)
insert(buckets, "Eagle", 55)
insert(buckets, "Otter", 66)
insert(buckets, "Whale", 77)

This creates five empty buckets. Each animal key is hashed to one of the five buckets. If several keys hash to the same bucket, they are stored as a linked list in that bucket.

5. Deleting "Koala"

key = "Koala"
index = hash_key(key, len(buckets))
current = buckets[index]
previous = None

• "Koala" is hashed to find its bucket.
• current starts at the first node in that bucket.
• previous starts as None.

while current is not None:
    if current.key == key:
        delete_node_with_predecessor(buckets, index, current, previous)
        break
    previous = current
    current = current.next

• The loop searches for the node containing "Koala".
• When it is found, current is the target node and previous is its predecessor.
• delete_node_with_predecessor() removes the target node.
• break stops the loop because the deletion is complete.
• If the current node is not "Koala", previous moves to current, and current moves to the next node.

Example

Assume bucket 2 contains:

Before deleting "Koala":

Bucket 2: [44] -> [33] -> None

Here:

• target_node = Koala node
• previous_node = None

Because previous_node is None, the program runs:

buckets[index] = target_node.next

So bucket 2 now points to the Panda node:

After deleting "Koala":

Bucket 2: [33] -> None

If "Koala" were in the middle of the chain, the previous node would instead be updated:

previous_node.next = target_node.next

That bypasses the Koala node and keeps the rest of the chain connected.

6. Expected output format

The exact bucket positions depend on hash_key(), but the output will look like this:

Before deleting 'Koala':
Bucket 0
Bucket 1
    Zebra -> 22
Bucket 2
    Koala -> 44
    Panda -> 33
Bucket 3
    Tiger -> 11
    Eagle -> 55
Bucket 4
    Otter -> 66
    Whale -> 77

After deleting 'Koala':
Bucket 0
Bucket 1
    Zebra -> 22
Bucket 2
    Panda -> 33
Bucket 3
    Tiger -> 11
    Eagle -> 55
Bucket 4
    Otter -> 66
    Whale -> 77

7. Why the predecessor matters

Once the target and predecessor are known, deletion itself takes constant time because only one pointer needs to change.

Step-by-Step Explanation

What This Program Does

This program updates the value of an existing key in a hash table that uses separate chaining. It searches only the bucket where the key should be stored, changes the value if the key is found, and returns True; otherwise, it returns False.

1. update_value() explanation

def update_value(buckets, key, new_value):
    index = hash_key(key, len(buckets))
    current = buckets[index]

• hash_key(key, len(buckets)) calculates the bucket index for the key.
• current = buckets[index] starts at the first node in that bucket’s linked list.
• If the bucket is empty, current is None.

    while current is not None:
        if current.key == key:
            current.value = new_value
            return True
        current = current.next
    return False

• The loop checks each node in the bucket.
• If current.key == key, the matching node has been found.
• current.value = new_value replaces the old value with the new value.
• return True immediately ends the function because the update succeeded.
• If the key does not match, current = current.next moves to the next node.
• If the loop reaches the end without finding the key, the function returns False.

In separate chaining, a lookup first hashes the key to locate its bucket and then walks that bucket’s linked list to compare keys.

2. insert() explanation

def insert(buckets, key, value):
    index = hash_key(key, len(buckets))
    new_node = Node(key, value)
    new_node.next = buckets[index]
    buckets[index] = new_node

• The key is hashed to find its bucket index.
• A new node is created with the key and value.
• new_node.next = buckets[index] links the new node to the current head of the bucket.
• buckets[index] = new_node makes the new node the new head of that bucket.

So each new entry is inserted at the front of its bucket’s linked list.

3. print_buckets() explanation

def print_buckets(buckets):
    for idx, bucket in enumerate(buckets):
        print(f"Bucket {idx}")
        current = bucket
        while current is not None:
            print(f"    {current.key} -> {current.value}")
            current = current.next

• enumerate(buckets) gives each bucket index and its head node.
• current = bucket starts at the first node in that bucket.
• The while loop prints every key-value pair in the bucket.
• current = current.next moves to the next node.
• When current becomes None, the loop stops.

4. Creating and filling the table

buckets = [None] * 5

insert(buckets, "Tiger", 11)
insert(buckets, "Zebra", 22)
insert(buckets, "Panda", 33)
insert(buckets, "Koala", 44)
insert(buckets, "Eagle", 55)
insert(buckets, "Otter", 66)
insert(buckets, "Whale", 77)

Each animal key is hashed to one of the five buckets. If multiple keys hash to the same bucket, they are stored in the same linked list.

5. Updating "Tiger"

print("\nupdate_value('Tiger', 99):", update_value(buckets, "Tiger", 99))

Step-by-step:

• "Tiger" is hashed to find its bucket.
• The loop searches that bucket’s linked list.
• When the node with key "Tiger" is found, its value changes from 11 to 99.
• The function returns True.

Before:

Tiger -> 11

After:

Tiger -> 99

6. Trying to update "Lion"

print("update_value('Lion', 1): ", update_value(buckets, "Lion", 1))

• "Lion" is hashed to find its bucket.
• The loop checks every node in that bucket.
• No node has the key "Lion".
• The loop ends, and the function returns False.
• No value is changed and no new node is inserted.

7. Expected output format

The exact bucket positions depend on hash_key(), but the output will look like this:

Before updating 'Tiger':
Bucket 0
Bucket 1
    Zebra -> 22
Bucket 2
    Tiger -> 11
    Panda -> 33
Bucket 3
    Eagle -> 55
Bucket 4
    Koala -> 44
    Otter -> 66
    Whale -> 77

update_value('Tiger', 99): True
update_value('Lion', 1):  False

After updating 'Tiger':
Bucket 0
Bucket 1
    Zebra -> 22
Bucket 2
    Tiger -> 99
    Panda -> 33
Bucket 3
    Eagle -> 55
Bucket 4
    Koala -> 44
    Otter -> 66
    Whale -> 77

8. Result cases

The update operation follows the same two-step pattern as lookup: hash the key to find the bucket, then search that bucket’s chain for the matching key.