Searching & Hashing: Techniques, Analysis & Applications

TAKEAWAYS:

• Searching algorithms differ in time complexity: $O(n)$ for linear, $O(\log n)$ for binary, and $O(\log \log n)$ for interpolation (best for sorted, uniformly distributed data).
• Hashing converts keys to array indices using hash functions, but collisions require resolution via chaining or open addressing.
• Load factor ($\lambda =\frac{n}{m}$) determines performance: high $\lambda$ degrades hashing efficiency, requiring resizing.
• Perfect hashing eliminates collisions but is impractical for dynamic datasets; universal hashing provides probabilistic guarantees.
• Applications: Hash tables power databases (e.g., SQLite), compilers (symbol tables), and caching (e.g., Redis).
• Exam focus: Compare algorithms, derive time complexities, and analyze hash table operations (insertion/deletion/search).

1. Searching Algorithms

Searching locates an element in a dataset. Efficiency depends on data structure and access method.

1.1 Linear Search

• Definition: Sequentially checks each element until the target is found or the list ends.
• Time Complexity:
  • Best case: $O(1)$ (first element matches).
  • Average/Worst case: $O(n)$.
• Use Case: Unsorted or small datasets.
• Code Example (C):

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

• Trace:

  Step	i	arr[i]	Key Found?
  1	0	10	No
  2	1	20	Yes

Visualization:

flowchart LR
    A["Start"] --> B["i = 0"]
    B --> C["Check arr[0] == key?"]
    C -->|"No"| D["i++"]
    D --> B
    C -->|"Yes"| E["Return index"]

1.2 Binary Search

• Definition: Repeatedly divides a sorted array in half to locate the target.
• Time Complexity: $O(\log n)$.
• Steps:
  1. Compare target with middle element.
  2. If equal, return index.
  3. If target < middle, search left half; else, search right half.
• Code Example (C):

  int binarySearch(int arr[], int l, int r, int key) {
      while (l <= r) {
          int mid = l + (r - l) / 2;
          if (arr[mid] == key) return mid;
          if (arr[mid] < key) l = mid + 1;
          else r = mid - 1;
      }
      return -1;
  }
  

• Trace (Array: [10, 20, 30, 40, 50], Key: 30):

  Step	l	r	mid	arr[mid]	Action
  1	0	4	2	30	Found
  2	0	1	0	10	Search right

Visualization:

1.3 Interpolation Search

• Definition: Estimates the position of the target based on its value distribution (works best for uniformly distributed sorted data).
• Formula: $$pos=low+\lfloor \frac{(key-arr[low])\times (high-low)}{arr[high]-arr[low]}\rfloor$$
• Time Complexity: $O(\log \log n)$ (best case), $O(n)$ (worst case).
• Example: Searching for "Nepal" in a sorted phonebook.

Comparison Table:

2. Hashing

Hashing maps keys to array indices using a hash function, enabling $O(1)$ average-time operations.

2.1 Hash Tables

• Components:
  • Hash Function: $h(k)=k\mathrm{mod}m$ (where $m$ = table size).
  • Array: Stores key-value pairs at computed indices.
  • Collision Resolution: Methods to handle hash conflicts.

Visualization (Initial State):

2.2 Collision Handling

A. Chaining (Separate Chaining)

• Method: Each slot holds a linked list of colliding keys.
• Pros: Simple, handles dynamic resizing.
• Cons: Wastes memory for pointers; worst-case $O(n)$ search.

Visualization (After Insertions):

B. Open Addressing

• Methods:
  1. Linear Probing: Check next slot sequentially.
  2. Quadratic Probing: $h(k,i)=(h(k)+i^2)\mathrm{mod}m$.
  3. Double Hashing: $h(k,i)=(h1(k)+i\cdot h2(k))\mathrm{mod}m$.
• Pros: No extra memory for pointers.
• Cons: Clusters degrade performance; worst-case $O(n)$.

Visualization (Linear Probing):

2.3 Load Factor and Resizing

• Load Factor ($\lambda$): $$\lambda =\frac{\text{Number of elements}}{\text{Table size}}$$
• Threshold: Typically 0.7. When exceeded, resize the table (double the size) and rehash all keys.
• Example: Resize from size 5 to 11 when $\lambda >0.7$.

Visualization (Resizing):

2.4 Perfect and Universal Hashing

• Perfect Hashing: No collisions (precomputed for static datasets).
• Universal Hashing: Uses a family of hash functions to minimize collisions probabilistically.
  • Example: $h(k)=(a\cdot k+b)\mathrm{mod}p$, where $a,b$ are random.

## In the real world

1. eSewa (Nepal):
   • Uses hash tables to store user profiles (key: user ID, value: account details) for $O(1)$ login verification.
   • Binary search optimizes sorted transaction histories for quick fraud detection.

2. Khalti (Digital Payments):

   • Hashing secures passwords (stores hashed values, not plaintext).
   • Interpolation search approximates transaction amounts in ledgers for faster audits.

3. Daraz (E-Commerce):

   • Binary search ranks product listings by price/sales for efficient filtering.
   • Hash tables cache frequently accessed items (e.g., "Best Sellers") to reduce database load.

4. Ncell (Mobile Network):

   • Hashing maps phone numbers to user data in SIM databases for instant lookup.
   • Linear search (rarely) checks unsorted call logs for billing.

5. NEPSE (Stock Exchange):

   • Binary search locates stock prices in sorted historical data for trend analysis.
   • Hash tables store real-time trades (symbol → price) for $O(1)$ updates.

Worked Example (Ncell Billing):

• Problem: Find the 10th highest call duration in a month’s logs (sorted: [5, 12, 15, 20, 22, 25, 30, 35, 40, 45, ...]).
• Solution: Binary search to locate the 10th element in $O(\log n)$ time.
  • Step 1: Mid = 5th element (22). Need higher → search right half.
  • Step 2: Mid = 8th element (35). Need lower → search left half.
  • Result: 10th element = 40 minutes.

3. Exam Tip

1. Searching:

   • Binary search requires sorted data; interpolation search needs uniform distribution.
   • Derive time complexities from recurrence relations (e.g., $T(n)=T(n/2)+O(1)$ → $O(\log n)$).

2. Hashing:

   • Load factor is critical: high $\lambda$ → more collisions → degrade to $O(n)$.
   • Resizing: Always double the table size to keep $\lambda$ efficient.
   • Collision resolution: Chaining is simpler; open addressing avoids pointers but risks clustering.

3. Common Pitfalls:

   • Forgetting to resize the hash table (leads to $O(n)$ operations).
   • Applying binary search on unsorted data (incorrect).
   • Ignoring worst-case scenarios (e.g., all keys hash to the same slot).

4. Practical Questions:

   • Given a hash function $h(k)=k\mathrm{mod}7$, show collisions for keys [10, 17, 24].
   • Compare the time to search [1, 3, 5, 7] using linear vs. binary search.
   • Design a hash table for 1000 students with IDs 100–1099 (choose size and method).

Key Formulae to Memorize:

1. Binary Search Midpoint: $mid=low+\frac{high-low}{2}$ (avoids overflow).
2. Load Factor: $\lambda =\frac{n}{m}$.
3. Interpolation Search Position: $$pos=low+\lfloor \frac{(key-arr[low])\times (high-low)}{arr[high]-arr[low]}\rfloor$$