Searching and Hashing: Linear, Binary Search, Hash Functions and Collisions

Sequential (linear) search

Compare the key with each element in turn until it is found or the list ends.

int linearSearch(int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key) return i;
    return -1;
}

• Best case O(1) (the first element); worst and average O(n).
• Works on unsorted data and on linked lists.

Binary search

Works only on a sorted array. Compare the key with the middle element: if it is equal, done; if smaller, search the left half; if larger, search the right half.

int binarySearch(int a[], int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;       /* avoids overflow of lo + hi */
        if (a[mid] == key) return mid;
        if (key < a[mid]) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

Trace: search 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

• lo = 0, hi = 9, mid = 4 → 16 < 23, so lo = 5
• lo = 5, hi = 9, mid = 7 → 56 > 23, so hi = 6
• lo = 5, hi = 6, mid = 5 → 23 found at index 5

Each step halves the range, so the time is O(log n). A million sorted items need at most about 20 comparisons.

Hashing

Hashing stores and finds records in (average) O(1) time. A hash function h(k) converts a key into an index in an array called the hash table.

Good hash functions

A good hash function is fast and spreads keys uniformly.

• Division method: h(k) = k mod m (m is usually a prime not close to a power of 2).
• Mid-square method: square the key and take the middle digits. k = 3205, k² = 10272025, take the middle digits "72".
• Folding method: split the key into parts and add them. 123456789 → 123 + 456 + 789 = 1368, then take mod m.
• Multiplication method: h(k) = ⌊m (kA mod 1)⌋, with 0 < A < 1.

Collisions

A collision occurs when two different keys hash to the same index. With h(k) = k mod 10, keys 25 and 35 both go to index 5. Collisions are unavoidable when there are more possible keys than slots, so they must be handled.

1. Separate chaining

Each table slot holds a linked list of all keys that hash to it. Insertion is O(1); search takes O(1 + α) on average, where the load factor α = n / m. The table never gets "full".

2. Open addressing

All keys are stored in the table itself. On a collision, probe for another empty slot.

• Linear probing: try h, h + 1, h + 2, … (mod m). Simple, but causes primary clustering.
• Quadratic probing: try h, h + 1², h + 2², h + 3², … Reduces primary clustering.
• Double hashing: try h₁(k) + i·h₂(k), with a second hash function for the step. This gives the best distribution.

Example (linear probing, m = 10): insert 25, 35, 45, 12.

• 25 → slot 5
• 35 → 5 is taken → slot 6
• 45 → 5 and 6 are taken → slot 7
• 12 → slot 2

Deleting from an open-addressed table needs a special "deleted" marker, so that later searches do not stop early at the gap.

Rehashing

When the load factor gets too high, create a larger table (about double the size, a prime) and insert every key again with the new hash function.

Exam tip

For hashing questions, draw the table with its indexes, insert the keys one by one, and say which slot each collision probes. Name the clustering problem when you use linear probing.