Hash Tables

ABSTRACT

A Hash Table is an array-based data structure that leverages a hash function to map keys to specific array indices. Its defining characteristic is that its average-case performance is independent of the number of elements ($n$) it stores, allowing for $O(1)$ operations in most practical scenarios.

---

1. The “Constant Time” Disclaimer

In computer science, we frequently label Hash Table operations as $O(1)$. However, it is important to understand what this measurement excludes:

• Ignoring the Hash Function: The $O(1)$ designation refers to the array access after the hash value is calculated.
• The Cost of $k$: For complex data types like strings or lists, a good hash function must iterate over all $k$ elements in the collection. Therefore, hashing a string of length $k$ is technically an $O(k)$ operation.
• Why we say $O(1)$: We use $O(1)$ because the time complexity does not grow as you add more items to the table. Unlike a Binary Search Tree (where search time increases as the tree gets taller), a Hash Table’s “jump” to an index remains constant regardless of the total number of entries.

---

2. Formal Definition

A Hash Table consists of:

1. Backing Array: An array of size $M$, where $M$ is the Capacity.
2. Hash Function ($H$): A function that maps a key to a valid index $(0\le \text{index}<M)$. A common simple function is $H(k)=k(\mathrm{mod}M)$.

The Core Operations (Simplified)

Below is the logic for a “collision-free” Hash Table (assuming every key maps to a unique index):

insert(key)

index = H(key)
if arr[index] is empty:
    arr[index] = key

find(key)

index = H(key)
return arr[index] == key

---

3. The “Unordered” Property

A critical trade-off of the Hash Table is that it is unordered. Because hash functions often use complex math (like $H(k)=2^k(\mathrm{mod}M)$) to randomize where keys land and avoid collisions, the physical order of elements in the array has no relationship to their actual values.

• Sorted Iteration: There is no efficient way to print a Hash Table in alphabetical or numerical order.
• C++ Implementation: The standard library calls this structure unordered_set to explicitly remind programmers that the sequence of elements is not guaranteed.

// Example: Output order is non-deterministic
unordered_set<string> animals = {"Giraffe", "Polar Bear", "Toucan"};
for(auto s : animals) {
    cout << s << endl; // Likely outputs: Toucan, Giraffe, Polar Bear
}

---

4. The Challenge of Collisions

In any real-world Hash Table, the number of possible keys (e.g., all possible human names) is vastly larger than the table’s capacity ($M$). This leads to collisions.

Collision: When two different keys, $k_1$ and $k_2$, result in the same hash value: $H(k_1)=H(k_2)$.

Collisions are the primary cause of performance degradation in Hash Tables. If many keys map to the same index, the $O(1)$ performance can slide toward $O(n)$.

---

5. Summary Analysis

Feature	Complexity (Average)	Logic
Find	$O(1)$	Compute index $\to$ Direct array access.
Insert	$O(1)$	Compute index $\to$ Place in array.
Remove	$O(1)$	Compute index $\to$ Clear array slot.
Order	Unordered	Indices are randomized to reduce collisions.