Data Structure in Dart – Hashing (Hash Tables, HashMap & HashSet in Dart)

1. Why Hashing Is So Powerful

Hashing allows us to:

Search data in O(1) average time
Avoid scanning entire lists
Build fast lookups (keys → values)

Almost every modern system relies on hashing:

User authentication
Caching (Redis, in-memory cache)
Databases indexing
Dictionaries, Maps, Sets

If you understand hashing well, your apps become fast and scalable.

2. What Is Hashing?

Hashing is the process of converting:

Key  →  Hash Function  →  Index

Example:

"user_123" → hash() → 42 → table[42]

A Hash Table stores data in an array-like structure using this index.

3. Hash Function

A hash function:

Takes a key (string, number, object)
Produces an integer (hash code)
Should be:
- Fast
- Deterministic
- Uniform (minimize collisions)

Simple Hash Function Example (Educational)

int simpleHash(String key, int tableSize) {
  int hash = 0;
  for (int i = 0; i < key.length; i++) {
    hash += key.codeUnitAt(i);
  }
  return hash % tableSize;
}

This is not production-grade, but useful for understanding.

4. Hash Collision

A collision occurs when:

hash(key1) == hash(key2)

Example:

"abc" → index 5
"cab" → index 5

Collisions are unavoidable.
The real question is: How do we handle them?

5. Collision Handling Techniques

1. Separate Chaining

Each index holds a Linked List of entries.

Index 3 → [key1 → value1] → [key2 → value2]

Pros

Simple
Works well with many collisions

Cons

Extra memory
Worst case → O(n)

2. Open Addressing

If a spot is taken, find another one:

Linear probing
Quadratic probing
Double hashing

Index 5 (occupied)
→ check 6
→ check 7

6. HashMap in Dart

Dart provides Map<K, V> which is implemented using hashing.

Basic Example

void main() {
  Map<String, int> ages = {
    "Alice": 25,
    "Bob": 30,
  };

  ages["Charlie"] = 28;

  print(ages["Alice"]); // 25
}

Time Complexity (Average)

Insert → O(1)
Search → O(1)
Delete → O(1)

7. HashSet in Dart

A Set stores only unique values and is also hash-based.

void main() {
  Set<String> fruits = {"Apple", "Banana"};

  fruits.add("Apple"); // ignored (duplicate)
  fruits.add("Mango");

  print(fruits); // Apple, Banana, Mango
}

Use cases:

Remove duplicates
Membership testing
Visited nodes in graph algorithms

8. Real-World Flutter Use Cases

1. User Cache (Fast Lookup)

class User {
  final String id;
  final String name;

  User(this.id, this.name);
}

class UserCache {
  final Map<String, User> _cache = {};

  void addUser(User user) {
    _cache[user.id] = user;
  }

  User? getUser(String id) {
    return _cache[id];
  }
}

Perfect for:

Offline data
Avoiding repeated API calls

2. Form Validation (Seen Emails)

bool hasDuplicateEmails(List<String> emails) {
  Set<String> seen = {};

  for (var email in emails) {
    if (seen.contains(email)) return true;
    seen.add(email);
  }
  return false;
}

9. Classic Hashing Problems

1. Two Sum Problem

List<int> twoSum(List<int> nums, int target) {
  Map<int, int> map = {};

  for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (map.containsKey(complement)) {
      return [map[complement]!, i];
    }
    map[nums[i]] = i;
  }
  return [];
}

Time: O(n)
Space: O(n)

2. First Non-Repeating Character

String? firstUniqueChar(String s) {
  Map<String, int> count = {};

  for (var c in s.split('')) {
    count[c] = (count[c] ?? 0) + 1;
  }

  for (var c in s.split('')) {
    if (count[c] == 1) return c;
  }
  return null;
}

10. Custom Objects as Keys (Important!)

When using custom classes as keys, you must override:

==
hashCode

class Point {
  final int x, y;

  Point(this.x, this.y);

  @override
  bool operator ==(Object other) =>
      other is Point && other.x == x && other.y == y;

  @override
  int get hashCode => Object.hash(x, y);
}

Without this, HashMap behaves incorrectly.

11. Complexity Summary

Operation	Hash Table (Avg)	Worst Case
Insert	O(1)	O(n)
Search	O(1)	O(n)
Delete	O(1)	O(n)

Worst case happens when many collisions occur.

12. Common Mistakes

Using List instead of Map for lookups
Forgetting to override hashCode
Assuming HashMap is always ordered
Ignoring worst-case scenarios

13. Summary

Hashing provides fast access using keys
Collisions are inevitable → must be handled
Dart Map and Set are hash-based
Widely used in Flutter apps, backend, databases
Essential for interviews & real systems