Skip to main content

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.

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)O(1)
  • Worst Case: O(n)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.