Hash Table Operations (Insert, Delete, Search)

Hash Table Operations: Put, Get, and Delete

The true power of hash tables lies in their ability to perform core operations – insertion, retrieval, and deletion – with remarkable efficiency. While we've discussed the theory of hashing and collision resolution, let's now examine how these principles translate into the mechanics of these essential operations. The goal for all these operations is an average time complexity of O(1).

---

1. Insertion (put or set)

The put (or set) operation is used to add a new key-value pair to the hash table or update the value associated with an existing key.

• Purpose: To store data that can be quickly retrieved later using its unique key.

• Steps:

  1. Hash the Key: The provided key is passed to the hash function. This function computes an integer hash code.
  2. Calculate Index: The hash code is then usually put through a modulo operation (e.g., hashCode % arraySize) to get an index that falls within the bounds of the hash table's underlying array (its "buckets").
  3. Check for Existing Key (Update): At this calculated index, the hash table checks if the key already exists.
     • If the key is found, its associated value is updated.
  4. Handle Collision (Insert New): If the key is not found at the initial index, or if the index is already occupied by a different key (a collision):
     • Chaining: The new key-value pair is added to the linked list (or other structure) at that bucket's index.
     • Open Addressing: The hash table follows its probing sequence (linear, quadratic, double hashing) to find the next available empty slot, where the key-value pair is then inserted.
  5. Update Size & Check Load Factor: The number of elements in the hash table is incremented. If the load factor (number of elements / number of buckets) exceeds a predefined threshold (e.g., 0.7), the hash table typically triggers a rehashing operation to resize itself.

• Time Complexity:

  • Average Case: O(1). This is because hashing and direct access to the bucket take constant time. If collisions are minimal, the operations within the bucket (adding to a short list or finding an empty slot) are also constant time.
  • Worst Case: O(N). This can occur if:
    • All N keys hash to the same bucket (in chaining, requiring traversal of an N-length linked list).
    • The table becomes very full, leading to extremely long probe sequences (in open addressing).
    • A rehashing operation is triggered, which involves re-inserting all N elements into a new, larger table.

---

2. Retrieval (get)

The get operation is used to find and return the value associated with a given key.

• Purpose: To quickly look up data based on its key.

• Steps:

  1. Hash the Key: The key is passed to the hash function to compute its hash code.
  2. Calculate Index: The hash code is used to determine the exact index in the underlying array.
  3. Search at Index: The hash table goes directly to this index and searches for the key:
     • Chaining: It traverses the linked list at that bucket, comparing the input key with the key of each node until a match is found.
     • Open Addressing: It follows the same probing sequence used during insertion, searching for the key. The search stops if the key is found, or if an empty slot is encountered (meaning the key is not in the table).
  4. Return Value: If the key is found, its associated value is returned. Otherwise, null, undefined, or an appropriate indicator is returned.

• Time Complexity:

  • Average Case: O(1). Similar to insertion, fast hash calculation and minimal collision resolution make it constant time.
  • Worst Case: O(N). If all keys are in one long collision chain (chaining) or require traversing almost the entire table (open addressing), retrieval becomes linear.

---

3. Deletion (delete)

The delete operation removes a key-value pair from the hash table.

• Purpose: To remove data and free up its associated storage.

• Steps:

  1. Hash the Key & Calculate Index: The process begins identically to get and put, hashing the key to find its potential index.
  2. Locate Key: The hash table navigates to that index and searches for the key using the appropriate collision resolution method (traversing a linked list for chaining, or following a probe sequence for open addressing).
  3. Remove Pair:
     • Chaining: Once the matching key is found within the linked list at that bucket, the node containing the key-value pair is simply removed from the list (standard linked list deletion).
     • Open Addressing: This is more complex. Simply emptying the slot could break the probe sequence for other elements that hashed to the same initial index but were placed further down. To avoid this, the slot is typically marked with a special "deleted" flag (sometimes called a tombstone). The deleted slot is ignored during lookups but can be reused for future insertions.
  4. Update Size: The number of elements in the hash table is decremented.

• Time Complexity:

  • Average Case: O(1).
  • Worst Case: O(N). Similar reasons as put and get.

---

4. The Amortized O(1) of Rehashing

While the primary operations aim for O(1), it's crucial to understand how rehashing (resizing the table) fits in. Put operations, in particular, can trigger rehashing if the load factor becomes too high.

• Impact: A rehashing operation involves creating a new, larger array and then re-inserting all existing N elements into this new table. This is an O(N) process.
• Amortized Analysis: Despite this O(N) occasional cost, hash tables are still said to have O(1) average time complexity. This is because rehashing happens infrequently (e.g., only when the table doubles in size), and its cost is "amortized" or spread out over many O(1) operations. The total cost of M operations, including some rehashes, is proportional to M, making the average cost per operation O(1).

---

Key Takeaway: Hash table operations (put, get, delete) achieve remarkable O(1) average-case time complexity by leveraging hash functions to quickly locate data. While collisions and periodic rehashing can lead to O(N) worst-case scenarios, the overall amortized performance remains constant time, making hash tables incredibly efficient for dynamic key-value storage.