Hash index for equality in PostgreSQL - Time & Space Complexity

Time Complexity: Hash index for equality

O(1)

Understanding Time Complexity

When we use a hash index in a database, it helps us find rows quickly by matching exact values.

We want to know how the time to find data changes as the table grows bigger.

Scenario Under Consideration

Analyze the time complexity of the following query using a hash index.

CREATE INDEX idx_hash_name ON users USING hash (name);

SELECT * FROM users WHERE name = 'Alice';
    

This code creates a hash index on the column name and then searches for rows where name equals 'Alice'.

Identify Repeating Operations

Look at what happens when the query runs:

• Primary operation: Computing the hash of the search value and looking up the matching bucket.
• How many times: Once per query, no scanning through all rows.

How Execution Grows With Input

As the table grows, the hash index keeps the search fast by jumping directly to the right place.

Input Size (n)	Approx. Operations
10	About 1 to 2 steps
100	Still about 1 to 2 steps
1000	Still about 1 to 2 steps

Pattern observation: The number of steps stays almost the same no matter how big the table gets.

Final Time Complexity

Time Complexity: O(1)

This means the time to find a row by exact match using a hash index stays constant even if the table grows very large.

Common Mistake

[X] Wrong: "Searching with a hash index takes longer as the table gets bigger because it has to check more rows."

[OK] Correct: The hash index jumps directly to the matching entries, so it does not scan all rows. The search time stays about the same.

Interview Connect

Understanding how hash indexes keep searches fast helps you explain efficient data lookup in real projects and shows you know how databases handle big data smoothly.

Self-Check

"What if we changed the query to search with a range condition instead of exact match? How would the time complexity change?"