2 Jan 2025

The Battle of 3 Kings - Binary Search vs Hashmap vs Linear Search

When dealing with a dataset, sometimes the most important thing is to find the data as quickly as possible. Sometimes this means sacrificing memory and sometimes performance.In this article we will make a brief comparison of 3 data search algorithms for 1M (1.000.000) entries.

1 - Use a Hashmap (Best for Fast Exact Matches)

When to Choose

You need exact match searches (e.g., "Does this exact string exist?").
Searches are frequent (e.g., user types a query in real-time).
You can afford extra memory (~40-100 MB for 1M entries).

Pros

Lookup Time: O(1) (instant after hashmap creation).
Setup Time: O(n) (one-time cost).
Dynamic Data: Supports quick additions/removals (unlike sorted arrays).

Cons

Memory overhead (duplicates keys).
Only works for exact matches, not substrings or ranges.

Example

// Preprocess onceconst hashMap = new Map();
 
// Use a unique key like "id"
data.forEach(item => hashMap.set(item.id, item));
 
// Real-time search
const result = hashMap.get(userInput);

2 - Sort + Binary Search (Best for Memory Efficiency)

When to Choose

You need exact or range-based searches.
Memory is tight (no extra overhead).
Data is static (no frequent additions/removals).

Pros

Lookup Time: O(log n) (fast for large data).
Memory: No extra memory beyond the sorted array.

Cons

Setup Time: O(n log n) (sorting cost).
Dynamic Data: Adding/removing elements requires re-sorting (O(n)).

Example

// Sort once - Sort by keyconst sortedData = [...data].sort((a, b) => a.id.localeCompare(b.id));
 
// Binary search function
function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid].id === target) return arr[mid];
    else if (arr[mid].id < target) low = mid + 1;
    else high = mid - 1;
  }
  return null;
}
 
// Usage
const result = binarySearch(sortedData, userInput);

3 - Linear Search (Avoid for Large Data)

When to Choose

You search rarely (e.g., once).
Data is tiny (e.g., <10.000 entries).

Pros

No setup time.
Simple to implement.

Cons

Lookup Time: O(n) (unbearably slow for 1M entries).

Example

// Avoid this for large data!const result = data.find(item => item.id === userInput);

Conclusion

For Exact Matches: Hashmap is the clear winner (speed trumps memory for large data).
For Range Queries or Memory Constraints: Sort the data and use binary search.
Never Use Linear Search for 1M entries unless you have no other choice.