Insertion in Hash Table

Insertion in Hash Table​

The insertion operation in a hash table involves adding a key-value pair. Hashing is used to map the key to an index in the table. If the key already exists, the existing value can be updated.

Video Explanation​

Watch

Steps for Insertion​

1. Hash the Key: Use a hash function to convert the key into an index.
2. Insert at the Computed Index: Place the key-value pair at the index. If there's already data, resolve collisions via methods like chaining or open addressing.
3. Update Value (if Key Exists): If the key already exists, update the associated value.

Time Complexity​

• Average Case: $O(1)$
• Worst Case: $O(n)$ (if many collisions occur)

Example Code (Python)​

class HashTable:
    def __init__(self):
        self.table = {}

    def insert(self, key, value):
        self.table[key] = value

# Example usage
hash_table = HashTable()
hash_table.insert('apple', 10)
hash_table.insert('banana', 20)
hash_table.insert('apple', 30)  # Updates value

Conclusion​

Insertion is a fundamental operation in hash tables, allowing for efficient data storage and retrieval, especially when handling key-value pairs.