Explain how Dart's Map works internally. How does it handle collisions? What is the time complexity of get/set operations?

Overview

Hash Map (Hash Table) is a fundamental data structure that stores key-value pairs and provides extremely fast lookups, insertions, and deletions. It uses a hash function to compute an index into an array of buckets from which the desired value can be found. Think of it as a super-efficient dictionary where you can instantly find any word without flipping through pages.

Hash maps are the backbone of modern programming, powering database indexes, caches, symbol tables in compilers, and countless everyday programming tasks. Understanding how hash maps work internally is essential for writing efficient code and is one of the most frequently asked interview topics.

Key characteristics:

• Average O(1) time for get, set, and delete operations
• Worst case O(n) when many collisions occur
• Uses hash function to map keys to array indices
• Handles collisions with chaining or open addressing
• Dynamic resizing when load factor exceeds threshold

When to use:

• Fast lookups by key (constant time on average)
• Frequency counting (character/word frequency)
• Caching and memoization
• Detecting duplicates
• Implementing sets
• Symbol tables and dictionaries

Core Concepts

How Hash Maps Work:

1. Hash Function: Converts key to integer hash code
2. Index Calculation:
   textCopy

   index = hashCode % arraySize

3. Storage: Store value at calculated index
4. Collision Handling: Resolve when two keys map to same index
5. Load Factor: Ratio of entries to buckets (triggers resize)

Visualization:

textCopy
Key "apple" → hashCode(456789) → index = 456789 % 10 = 9
Key "banana" → hashCode(123456) → index = 123456 % 10 = 6

Array (buckets):
[0] → null
[1] → null
...
[6] → "banana": 10
...
[9] → "apple": 5

Hash Function

A good hash function should:

• Be deterministic (same input → same output)
• Distribute keys uniformly across buckets
• Be fast to compute
• Minimize collisions

Dart's Built-in Hash:

dartCopy
void main() {
  String key1 = "flutter";
  String key2 = "dart";

  print(key1.hashCode);  // e.g., 235847264
  print(key2.hashCode);  // e.g., 87394624

  // Same string always produces same hash
  assert("test".hashCode == "test".hashCode);
}

Custom Hash Function:

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

void main() {
  print(simpleHash("apple", 10));   // Index in range 0-9
  print(simpleHash("banana", 10));  // Different index
}

Collision Handling

When two keys hash to the same index, a collision occurs. Two main strategies:

1. Chaining (Separate Chaining)

Each bucket stores a linked list of entries.

dartCopy
class Entry<K, V> {
  K key;
  V value;
  Entry<K, V>? next;

  Entry(this.key, this.value, [this.next]);
}

class HashMapChaining<K, V> {
  static const int _initialCapacity = 16;
  late List<Entry<K, V>?> _buckets;
  int _size = 0;

  HashMapChaining() {
    _buckets = List.filled(_initialCapacity, null);
  }

  int _hash(K key) {
    return key.hashCode.abs() % _buckets.length;
  }

  /// Set key-value pair - O(1) average
  void set(K key, V value) {
    int index = _hash(key);
    Entry<K, V>? current = _buckets[index];

    // Check if key already exists (update)
    while (current != null) {
      if (current.key == key) {
        current.value = value;  // Update existing
        return;
      }
      current = current.next;
    }

    // Insert new entry at head (prepend)
    _buckets[index] = Entry(key, value, _buckets[index]);
    _size++;

    // Resize if load factor > 0.75
    if (_size / _buckets.length > 0.75) {
      _resize();
    }
  }

  /// Get value by key - O(1) average
  V? get(K key) {
    int index = _hash(key);
    Entry<K, V>? current = _buckets[index];

    while (current != null) {
      if (current.key == key) {
        return current.value;
      }
      current = current.next;
    }

    return null;  // Key not found
  }

  /// Remove key - O(1) average
  bool remove(K key) {
    int index = _hash(key);
    Entry<K, V>? current = _buckets[index];
    Entry<K, V>? prev;

    while (current != null) {
      if (current.key == key) {
        if (prev == null) {
          _buckets[index] = current.next;  // Remove head
        } else {
          prev.next = current.next;  // Remove middle/tail
        }
        _size--;
        return true;
      }
      prev = current;
      current = current.next;
    }

    return false;  // Key not found
  }

  /// Check if key exists - O(1) average
  bool containsKey(K key) {
    return get(key) != null;
  }

  /// Resize and rehash all entries
  void _resize() {
    List<Entry<K, V>?> oldBuckets = _buckets;
    _buckets = List.filled(oldBuckets.length * 2, null);
    _size = 0;

    // Rehash all entries
    for (var bucket in oldBuckets) {
      Entry<K, V>? current = bucket;
      while (current != null) {
        set(current.key, current.value);
        current = current.next;
      }
    }
  }

  int get size => _size;
  bool get isEmpty => _size == 0;

  @override
  String toString() {
    final entries = <String>[];
    for (var bucket in _buckets) {
      Entry<K, V>? current = bucket;
      while (current != null) {
        entries.add('${current.key}: ${current.value}');
        current = current.next;
      }
    }
    return '{${entries.join(', ')}}';
  }
}

void main() {
  var map = HashMapChaining<String, int>();

  map.set('apple', 5);
  map.set('banana', 10);
  map.set('cherry', 15);

  print(map.get('apple'));   // 5
  print(map.get('banana'));  // 10
  print(map.size);           // 3

  map.remove('banana');
  print(map.size);           // 2
  print(map);                // {apple: 5, cherry: 15}
}

Chaining Pros/Cons:

• ✅ Simple to implement
• ✅ Never "full" - can always add more
• ✅ Performance degrades gracefully
• ❌ Extra memory for linked list pointers
• ❌ Cache-unfriendly (pointer chasing)

2. Open Addressing (Linear Probing)

Store all entries in the array itself. On collision, probe for next empty slot.

dartCopy
class HashMapOpenAddressing<K, V> {
  static const int _initialCapacity = 16;
  late List<K?> _keys;
  late List<V?> _values;
  late List<bool> _occupied;
  int _size = 0;

  HashMapOpenAddressing() {
    _keys = List.filled(_initialCapacity, null);
    _values = List.filled(_initialCapacity, null);
    _occupied = List.filled(_initialCapacity, false);
  }

  int _hash(K key) {
    return key.hashCode.abs() % _keys.length;
  }

  /// Find slot for key (linear probing)
  int _findSlot(K key) {
    int index = _hash(key);
    int startIndex = index;

    while (_occupied[index]) {
      if (_keys[index] == key) {
        return index;  // Key found
      }
      index = (index + 1) % _keys.length;  // Linear probe

      if (index == startIndex) {
        throw StateError('Hash table is full');
      }
    }

    return index;  // Empty slot
  }

  /// Set key-value pair - O(1) average
  void set(K key, V value) {
    if (_size / _keys.length > 0.75) {
      _resize();
    }

    int index = _findSlot(key);

    if (!_occupied[index]) {
      _size++;
    }

    _keys[index] = key;
    _values[index] = value;
    _occupied[index] = true;
  }

  /// Get value by key - O(1) average
  V? get(K key) {
    int index = _hash(key);
    int startIndex = index;

    while (_occupied[index]) {
      if (_keys[index] == key) {
        return _values[index];
      }
      index = (index + 1) % _keys.length;

      if (index == startIndex) break;
    }

    return null;
  }

  void _resize() {
    List<K?> oldKeys = _keys;
    List<V?> oldValues = _values;
    List<bool> oldOccupied = _occupied;

    _keys = List.filled(oldKeys.length * 2, null);
    _values = List.filled(oldKeys.length * 2, null);
    _occupied = List.filled(oldKeys.length * 2, false);
    _size = 0;

    for (int i = 0; i < oldKeys.length; i++) {
      if (oldOccupied[i]) {
        set(oldKeys[i]! as K, oldValues[i]! as V);
      }
    }
  }

  int get size => _size;
  bool get isEmpty => _size == 0;
}

Open Addressing Pros/Cons:

• ✅ Better cache locality (array-based)
• ✅ No extra memory for pointers
• ❌ More complex deletion
• ❌ Performance degrades with high load factor
• ❌ Can become "full" (requires resize)

Load Factor and Resizing

Load Factor = Number of entries / Number of buckets

Default threshold: 0.75 (75% full)

dartCopy
// When to resize
if (_size / _buckets.length > 0.75) {
  _resize();  // Double capacity
}

Why 0.75?

• Good balance between space and time
• Keeps collision rate low
• Prevents performance degradation

Resizing Process:

1. Create new array (typically 2x size)
2. Rehash all existing entries
3. Insert into new array
4. Update reference

Time Complexity:

• Resize operation: O(n) - must rehash all entries
• Amortized insertion: O(1) - resize happens rarely

Dart's Built-in Map

Dart provides optimized

Map

dartCopy
void main() {
  // Literal syntax
  var map = {'apple': 5, 'banana': 10};

  // Constructor
  var emptyMap = Map<String, int>();

  // From iterables
  var fromEntries = Map.fromIterables(
    ['a', 'b', 'c'],
    [1, 2, 3]
  );

  // Operations
  map['cherry'] = 15;           // Set
  print(map['apple']);          // Get → 5
  map.remove('banana');         // Remove
  print(map.containsKey('apple'));  // true
  print(map.length);            // 2

  // Iteration
  map.forEach((key, value) {
    print('$key: $value');
  });

  // Null-safe access
  print(map['missing']);        // null
  print(map['missing'] ?? 0);   // 0 (default)
}

Comparison Table

Where:

• n = number of entries
• m = number of buckets

Use Case Example: Frequency Counter

Count character frequencies in a string.

dartCopy
Map<String, int> characterFrequency(String text) {
  final freq = <String, int>{};

  for (int i = 0; i < text.length; i++) {
    String char = text[i].toLowerCase();
    if (char.trim().isEmpty) continue;  // Skip whitespace

    freq[char] = (freq[char] ?? 0) + 1;
  }

  return freq;
}

void main() {
  String text = "Hello World";
  var freq = characterFrequency(text);

  print(freq);
  // {h: 1, e: 1, l: 3, o: 2, w: 1, r: 1, d: 1}

  // Find most frequent character
  String? mostFrequent;
  int maxCount = 0;

  freq.forEach((char, count) {
    if (count > maxCount) {
      maxCount = count;
      mostFrequent = char;
    }
  });

  print('Most frequent: $mostFrequent ($maxCount times)');
  // Most frequent: l (3 times)
}

Use Case Example: LRU Cache

Implement a Least Recently Used (LRU) cache using hash map.

dartCopy
class LRUCache<K, V> {
  final int _capacity;
  final Map<K, _Node<K, V>> _cache = {};
  _Node<K, V>? _head;
  _Node<K, V>? _tail;

  LRUCache(this._capacity);

  V? get(K key) {
    if (!_cache.containsKey(key)) return null;

    final node = _cache[key]!;
    _moveToHead(node);
    return node.value;
  }

  void put(K key, V value) {
    if (_cache.containsKey(key)) {
      final node = _cache[key]!;
      node.value = value;
      _moveToHead(node);
    } else {
      final node = _Node(key, value);
      _cache[key] = node;
      _addToHead(node);

      if (_cache.length > _capacity) {
        final removed = _removeTail();
        _cache.remove(removed.key);
      }
    }
  }

  void _addToHead(_Node<K, V> node) {
    node.next = _head;
    node.prev = null;

    if (_head != null) {
      _head!.prev = node;
    }
    _head = node;

    if (_tail == null) {
      _tail = node;
    }
  }

  void _moveToHead(_Node<K, V> node) {
    _removeNode(node);
    _addToHead(node);
  }

  void _removeNode(_Node<K, V> node) {
    if (node.prev != null) {
      node.prev!.next = node.next;
    } else {
      _head = node.next;
    }

    if (node.next != null) {
      node.next!.prev = node.prev;
    } else {
      _tail = node.prev;
    }
  }

  _Node<K, V> _removeTail() {
    final node = _tail!;
    _removeNode(node);
    return node;
  }
}

class _Node<K, V> {
  K key;
  V value;
  _Node<K, V>? prev;
  _Node<K, V>? next;

  _Node(this.key, this.value);
}

void main() {
  var cache = LRUCache<int, String>(3);

  cache.put(1, 'one');
  cache.put(2, 'two');
  cache.put(3, 'three');
  print(cache.get(2));  // 'two' (move to front)

  cache.put(4, 'four');  // Evicts key 1
  print(cache.get(1));  // null (evicted)
  print(cache.get(3));  // 'three'
}

Best Practices

1. Choose Appropriate Key Types

dartCopy
// ✅ Good - immutable keys
var map = <String, int>{};
var map2 = <int, String>{};

// ⚠️ Caution - mutable objects as keys
class Person {
  String name;
  Person(this.name);

  @override
  int get hashCode => name.hashCode;

  @override
  bool operator ==(Object other) =>
    other is Person && other.name == name;
}

var people = <Person, int>{};  // OK if hashCode/== overridden

// ❌ Bad - lists as keys (mutable)
var bad = <List<int>, String>{};  // Hash changes if list modified!

2. Use Null-Safe Access

dartCopy
// ✅ Good - handle missing keys
String? value = map['key'];
String value2 = map['key'] ?? 'default';
String value3 = map.putIfAbsent('key', () => 'default');

// ❌ Bad - assumes key exists
String value = map['key']!;  // May throw!

3. Prefer Built-in Map for Production

dartCopy
// ✅ Good - use Dart's optimized Map
var map = <String, int>{};

// ❌ Overkill - custom hash map for simple use
var custom = HashMapChaining<String, int>();  // Use built-in instead

Interview Tips

Common Interview Questions:

Q: "How does a hash map work internally?"

• Hash function converts key to index
• Collisions handled via chaining or open addressing
• Load factor triggers resize (typically 0.75)
• Average O(1) operations, worst O(n)

Q: "What makes a good hash function?"

• Deterministic (same input → same output)
• Uniform distribution across buckets
• Fast to compute
• Minimizes collisions

Q: "Why is hash map O(1) on average but O(n) worst case?"

• O(1): When few collisions, direct bucket access
• O(n): When all keys hash to same bucket (chain/probe through all)

Q: "When would you NOT use a hash map?"

• Need sorted order (use TreeMap/SplayTreeMap)
• Need range queries (use tree-based structure)
• Keys change frequently (rehashing overhead)
• Memory constrained (hash map uses extra space)

Follow-up Questions:

• "HashMap vs TreeMap?" → O(1) vs O(log n), unordered vs sorted
• "Load factor impact?" → Higher = more collisions, lower = wasted space
• "Implement two-sum problem?" → Classic hash map problem

Red Flags to Avoid:

• Not knowing collision handling strategies ❌
• Confusing hash map with hash set ❌
• Not understanding O(1) is average, not guaranteed ❌
• Ignoring load factor and resizing ❌

Real-World Applications

1. Database Indexing

dartCopy
// Fast lookup of records by ID
Map<int, User> userIndex = {};
User? findUser(int id) => userIndex[id];  // O(1)

2. Memoization (Caching)

dartCopy
Map<int, int> _memo = {};

int fibonacci(int n) {
  if (n <= 1) return n;
  if (_memo.containsKey(n)) return _memo[n]!;

  _memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return _memo[n]!;
}

3. Anagram Detection

dartCopy
bool areAnagrams(String s1, String s2) {
  if (s1.length != s2.length) return false;

  var freq = <String, int>{};

  for (int i = 0; i < s1.length; i++) {
    freq[s1[i]] = (freq[s1[i]] ?? 0) + 1;
    freq[s2[i]] = (freq[s2[i]] ?? 0) - 1;
  }

  return freq.values.every((count) => count == 0);
}

4. Graph Adjacency List

dartCopy
// Represent graph using hash map
Map<String, List<String>> graph = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['D'],
  'D': []
};

Resources

• Hash Table - Wikipedia
• Dart Map Class API
• Hash Table Visualization