What Is The Time Complexity Of Various Operations In A Hash Table ?

A hash table is a data structure that uses a hash function to map keys to their associated values. It is commonly used for efficient data storage and retrieval because it allows for nearly constant-time complexity for various operations. Hash tables are used in data structures like Java’s HashMap and HashSet.

Definition

A hash table is a data structure that maps keys to values using a hashing function. It typically uses an array (called the bucket array) to store data and distributes the keys across this array based on each key’s hash code. The hash function determines the index in the array where the value should be stored. If two keys have the same hash code, a collision occurs, and a strategy like chaining or open addressing is used to resolve it.

Time Complexity of Various Operations

Insertion: O(1)O(1)O(1) on average, O(n)O(n)O(n) in the worst case

On average, inserting a key-value pair into a hash table is constant-time, O(1)O(1)O(1), because the hash function quickly determines the position. In rare cases, with too many collisions, it can degrade to O(n)O(n)O(n).

Deletion: O(1)O(1)O(1) on average, O(n)O(n)O(n) in the worst case

Deleting an element is generally fast and has constant-time complexity if the hash table has minimal collisions. However, if there are many collisions, it can take longer.

Search (Lookup): O(1)O(1)O(1) on average, O(n)O(n)O(n) in the worst case

On average, the lookup operation is also constant-time because the hash function maps the key to its corresponding index. In a worst-case scenario with heavy collisions, the time complexity can degrade to O(n)O(n)O(n)

Example

import java.util.LinkedList;

class HashTable {
    private LinkedList<String>[] table;
    private int size;
    
    // Constructor
    public HashTable(int size) {
        this.size = size;
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // Hash function to compute index
    private int hash(String key) {
        return key.hashCode() % size;
    }

    // Insert operation
    public void insert(String key) {
        int index = hash(key);
        table[index].add(key);  // Handle collisions using LinkedList
        System.out.println("Inserted: " + key);
    }

    // Search operation
    public boolean search(String key) {
        int index = hash(key);
        return table[index].contains(key);
    }

    // Delete operation
    public void delete(String key) {
        int index = hash(key);
        if (table[index].remove(key)) {
            System.out.println("Deleted: " + key);
        } else {
            System.out.println(key + " not found.");
        }
    }
}

public class HashTableExample {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(10);
        
        // Insert elements
        hashTable.insert("apple");
        hashTable.insert("banana");
        hashTable.insert("cherry");
        
        // Search elements
        System.out.println("Search 'apple': " + hashTable.search("apple"));  // Expected: true
        System.out.println("Search 'grape': " + hashTable.search("grape"));  // Expected: false
        
        // Delete elements
        hashTable.delete("banana");  // Expected: Deleted: banana
        hashTable.delete("grape");   // Expected: grape not found.
    }
}

Output:

Inserted: apple
Inserted: banana
Inserted: cherry
Search 'apple': true
Search 'grape': false
Deleted: banana
grape not found.

Features of a Hash Table

• Provides efficient O(1) access time on average for insertion, deletion, and search.
• Hash tables often resize automatically to maintain a reasonable load factor.
• Techniques like chaining and open addressing handle hash collisions effectively.
• Keys are not stored in any particular order.

Advantages of a Hash Table

• Ideal for scenarios where fast lookups, insertions, and deletions are needed.
• Supports keys of any object type, as long as a proper hashCode() function is implemented.
• Offers a balance between memory and access efficiency through dynamic resizing and load factor control.