Hash Table Concept and Hash Functions in DSA C - Time & Space Complexity

Time Complexity: Hash Table Concept and Hash Functions

O(n)

Understanding Time Complexity

We want to understand how fast a hash table can find or store data.

The question is: how does the time to do these actions change as the data grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple hash function example
unsigned int hash(char *str, unsigned int table_size) {
    unsigned int hash_value = 0;
    for (int i = 0; str[i] != '\0'; i++) {
        hash_value = (hash_value * 31 + (unsigned char)str[i]) % table_size;
    }
    return hash_value;
}
    

This code calculates a hash value for a string to find its place in a hash table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each character in the input string.
• How many times: Once for every character in the string (length n).

How Execution Grows With Input

As the string gets longer, the time to compute the hash grows in a straight line.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows directly with the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute the hash grows linearly with the input size.

Common Mistake

[X] Wrong: "Hash functions always run in constant time no matter the input size."

[OK] Correct: The hash function must look at every character in the input, so time grows with input length.

Interview Connect

Understanding how hash functions work and their time cost helps you explain why hash tables are fast and when they might slow down.

Self-Check

"What if the hash function only looked at the first few characters of the string? How would the time complexity change?"