Hash Table, Hash Function, Collision, Linear Probing and Quadratic Probing

1. Hash Table

A hash table is a data structure that stores data in an array format, where each data item is placed at a specific position (index) calculated based on the value of the key. The data is stored in an array called a hash table, and the mapping of keys to indices is done so that equal keys map to equal indices. Hash tables are useful for performing searching, insertion, and deletion at a faster rate.

2. Hash Function

A hash function is a function that takes a key as input and computes and returns the position (index) of the record in the hash table, instead of performing comparisons. It maps keys to indices of the hash table.

Common hash functions include:

• Division Method: h(key) = key % table_size
• Mid-Square Method: Square the key and take the middle digits as the index.
• Digit Folding: Divide the key into parts and combine them using simple operations.

Example (Division Method): For keys {52, 68, 99, 84} with table size 10:

h(52) = 52 % 10 = 2
h(68) = 68 % 10 = 8
h(99) = 99 % 10 = 9
h(84) = 84 % 10 = 4

3. Collision in Hashing

A collision is a situation that occurs when two distinct keys produce the same hash value, i.e., two different data items are mapped to the same index in the hash table.

Collisions are unavoidable whenever members of a very large set are mapped to a relatively short bit string (Pigeonhole Principle).

Example:

h(89) = 89 % 10 = 9
h(49) = 49 % 10 = 9   <-- Collision! Both map to index 9

Collision Resolution Methods:

• Open Addressing (Linear Probing, Quadratic Probing, Double Hashing)
• Chaining
• Rehashing
• Hashing using Buckets

4. Linear Probing

Linear probing is an open addressing collision resolution technique in which, when a collision occurs, the algorithm searches for the next empty (vacant) slot sequentially in the array until a free location is found.

Formula:

h(x, i) = (h(x) + i) % table_size

where i = 1, 2, 3, ... is the probe number.

Disadvantage: Linear probing suffers from primary clustering, where a cluster of occupied slots forms, slowing down future insertions and searches.

Example of Linear Probing

Insert keys {89, 49, 18, 58} into a hash table of size 10 using h(x) = x % 10.

Step 1: Insert 89

h(89) = 89 % 10 = 9
Index 9 is empty --> Place 89 at index 9

Step 2: Insert 49

h(49) = 49 % 10 = 9
Index 9 is OCCUPIED (collision!)
Try index (9+1) % 10 = 0 --> Index 0 is empty
Place 49 at index 0

Step 3: Insert 18

h(18) = 18 % 10 = 8
Index 8 is empty --> Place 18 at index 8

Step 4: Insert 58

h(58) = 58 % 10 = 8
Index 8 is OCCUPIED (collision!)
Try index (8+1) % 10 = 9 --> Index 9 is OCCUPIED
Try index (8+2) % 10 = 0 --> Index 0 is OCCUPIED
Try index (8+3) % 10 = 1 --> Index 1 is empty
Place 58 at index 1

Final Hash Table:

5. Quadratic Probing

Quadratic probing is an open addressing collision resolution technique that eliminates the primary clustering problem of linear probing. Instead of probing linearly, it uses a quadratic function to find the next available slot.

Formula:

h(x, j) = (hash_value + j^2) % table_size

where j = 1, 2, 3, ... is the probe number.

• 1st collision: (hash_value + 1^2) % table_size
• 2nd collision: (hash_value + 2^2) % table_size
• 3rd collision: (hash_value + 3^2) % table_size
• and so on...

Advantage: Reduces primary clustering compared to linear probing.

Example of Quadratic Probing

Insert keys {89, 49, 58, 79} into a hash table of size 10 using h(x) = x % 10.

Step 1: Insert 89

h(89) = 89 % 10 = 9
Index 9 is empty --> Place 89 at index 9

Step 2: Insert 49

h(49) = 49 % 10 = 9
Index 9 is OCCUPIED (collision!)
Probe 1: (9 + 1^2) % 10 = (9 + 1) % 10 = 0 --> Index 0 is empty
Place 49 at index 0

Step 3: Insert 58

h(58) = 58 % 10 = 8
Index 8 is empty --> Place 58 at index 8

Step 4: Insert 79

h(79) = 79 % 10 = 9
Index 9 is OCCUPIED (collision!)
Probe 1: (9 + 1^2) % 10 = 0  --> Index 0 is OCCUPIED
Probe 2: (9 + 2^2) % 10 = 3  --> Index 3 is empty
Place 79 at index 3

Final Hash Table:

Notice the difference from linear probing: 79 jumps four slots away to index 3 instead of settling next to the cluster at 0 and 1, so the occupied slots stay spread out.

6. Linear Probing Compared with Quadratic Probing

7. Conclusion

A hash table stores records at positions computed by a hash function rather than found by comparison, which is what gives it average constant time insertion, deletion and search. Because a hash function maps a large key space onto a small index range, collisions cannot be avoided, so a resolution strategy is part of every practical hash table. Linear probing resolves a collision by walking to the next free slot, which is simple but builds long runs of occupied slots, while quadratic probing spreads the probes out as squares of the probe number and so breaks up primary clustering. Both remain efficient only while the table is kept well below full, which is why the load factor is watched and the table is rehashed into a larger prime sized array when it grows too high.

Asymptotic Analysis and Theta Notation

Asymptotic Analysis

Asymptotic analysis of an algorithm refers to defining the mathematical framing of its run-time performance. It is a technique used to evaluate the performance of an algorithm in terms of input size, without measuring the actual running time.

Using asymptotic analysis, we can conclude three scenarios of an algorithm:

Asymptotic analysis helps us compare algorithms independently of machine, language, or implementation details.

Theta Notation (Θ-Notation)

Theta notation is used to define the tight bound (both upper and lower bound) of an algorithm's running time. It represents the average case complexity.

Definition

A function f(n) is said to be Θ(g(n)) if there exist positive constants c1, c2, and n0 such that:

$$c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \quad \text{for all } n \geq n_0$$

This means:

• g(n) is both an upper bound and a lower bound for f(n)
• f(n) grows at the same rate as g(n)

Graphical Representation

f(n) is sandwiched between c1*g(n) and c2*g(n)

  |        c2*g(n)
  |       /
  |      / f(n)
  |     /
  |    / c1*g(n)
  |___/________________
              n0       n -->

Example

Let f(n) = 2n + 3

We want to show that f(n) = Θ(n), i.e., g(n) = n.

We need to find c1, c2, and n0 such that:

$$c_1 \cdot n \leq 2n + 3 \leq c_2 \cdot n$$

Finding c2 (upper bound):

$$2n + 3 \leq c_2 \cdot n$$

For n >= 1: $$2n + 3 \leq 2n + 3n = 5n$$

So c2 = 5 works.

Finding c1 (lower bound):

$$c_1 \cdot n \leq 2n + 3$$

Clearly: $$2n \leq 2n + 3$$

So c1 = 2 works.

Result:

$$2n \leq 2n + 3 \leq 5n \quad \text{for all } n \geq 1$$

Therefore, f(n) = 2n + 3 = Θ(n) with c1 = 2, c2 = 5, n0 = 1.

Key Points

• Theta notation gives an exact asymptotic behavior
• If f(n) = Θ(g(n)), then f(n) = O(g(n)) AND f(n) = Ω(g(n))
• It is the most precise of the three asymptotic notations
• Example: Linear search has Θ(n) average case complexity