Understanding Dart’s HashMap and LinkedHashMap: Implementation Details and Interview Questions

Preface

Many interviewees have encountered HashMap questions, especially Java/Android developers, and with the rise of Flutter, Dart's HashMap is now a frequent topic. This article lists typical interview questions and walks through the source code to give concise answers.

Typical Interview Questions

What is the difference between HashMap and LinkedHashMap ?

When creating a map with final map = Map(); , which concrete class is returned?

What is the underlying data structure of HashMap ?

What is the default size of a HashMap ?

How does HashMap handle hash collisions?

When and how does HashMap resize?

What is the underlying data structure of LinkedHashMap ?

How does LinkedHashMap handle hash collisions?

When and how does LinkedHashMap resize?

Using HashMap and LinkedHashMap

Create a HashMap instance

final map = HashMap();

Create a LinkedHashMap instance

final map = LinkedHashMap();

Create a generic Map instance

final map = Map();

The generic Map() factory actually returns a LinkedHashMap instance, as shown by the factory constructor in the source.

@patch
class Map<K, V> {
  ...
  @patch
  factory Map() => new LinkedHashMap<K, V>();
  ...
}

HashMap Implementation

Constructor

@patch
class HashMap<K, V> {
  @patch
  factory HashMap({bool equals(K key1, K key2)?, int hashCode(K key)?, bool isValidKey(potentialKey)?}) {
    if (isValidKey == null) {
      if (hashCode == null) {
        if (equals == null) {
          return new _HashMap<K, V>();
        }
        ...
      }
    }
  }
}

Without optional parameters, the constructor returns a private _HashMap instance; with parameters it may return _IdentityHashMap or _CustomHashMap .

Underlying Structure

var _buckets = List<_HashMapEntry<K, V>?>.filled(_INITIAL_CAPACITY, null);

The buckets are an array of linked‑list entries, i.e., an array‑plus‑linked‑list design. The initial capacity is 8 (Dart) compared with Java's 16.

Lookup Operation

V? operator [](Object? key) {
  final hashCode = key.hashCode;
  final buckets = _buckets;
  final index = hashCode & (buckets.length - 1);
  var entry = buckets[index];
  while (entry != null) {
    if (hashCode == entry.hashCode && entry.key == key) {
      return entry.value;
    }
    entry = entry.next;
  }
  return null;
}

The key's hash code is masked with length‑1 to obtain the bucket index, then the linked list is traversed. This mirrors Java's pre‑JDK 8 HashMap implementation.

Put Operation

void operator []=(K key, V value) {
  final hashCode = key.hashCode;
  final buckets = _buckets;
  final length = buckets.length;
  final index = hashCode & (length - 1);
  var entry = buckets[index];
  while (entry != null) {
    if (hashCode == entry.hashCode && entry.key == key) {
      entry.value = value;
      return;
    }
    entry = entry.next;
  }
  _addEntry(buckets, index, length, key, value, hashCode);
}

If the key exists, its value is overwritten; otherwise a new entry is added via _addEntry , which inserts at the head of the bucket list and updates the element count.

Resize Operation

void _resize() {
  final oldBuckets = _buckets;
  final oldLength = oldBuckets.length;
  final newLength = oldLength << 1;
  final newBuckets = List<_HashMapEntry<K, V>?>.filled(newLength, null);
  for (int i = 0; i < oldLength; i++) {
    var entry = oldBuckets[i];
    while (entry != null) {
      final next = entry.next;
      final hashCode = entry.hashCode;
      final index = hashCode & (newLength - 1);
      entry.next = newBuckets[index];
      newBuckets[index] = entry;
      entry = next;
    }
  }
  _buckets = newBuckets;
}

When the load factor exceeds 0.75, the bucket array size doubles and all entries are re‑hashed using head‑insertion.

Deletion

void _removeEntry(_HashMapEntry<K, V> entry, _HashMapEntry<K, V>? previousInBucket, int bucketIndex) {
  if (previousInBucket == null) {
    _buckets[bucketIndex] = entry.next;
  } else {
    previousInBucket.next = entry.next;
  }
}

Deletion follows normal linked‑list removal semantics.

Iteration

void forEach(void action(K key, V value)) {
  final stamp = _modificationCount;
  final buckets = _buckets;
  final length = buckets.length;
  for (int i = 0; i < length; i++) {
    var entry = buckets[i];
    while (entry != null) {
      action(entry.key, entry.value);
      if (stamp != _modificationCount) {
        throw new ConcurrentModificationError(this);
      }
      entry = entry.next;
    }
  }
}

Iteration order is bucket order, not insertion order, and a fail‑fast check throws ConcurrentModificationError if the map changes during traversal.

LinkedHashMap Implementation

Unlike Java's linked‑hash map that uses a doubly‑linked node, Dart's version keeps two parallel arrays: _index (hash‑to‑position mapping) and _data (key/value pairs stored in insertion order).

Constructor

@patch
class LinkedHashMap<K, V> {
  @patch
  factory LinkedHashMap({bool equals(K key1, K key2)?, int hashCode(K key)?, bool isValidKey(potentialKey)?}) {
    if (isValidKey == null) {
      if (hashCode == null) {
        if (equals == null) {
          return new _InternalLinkedHashMap<K, V>();
        }
        ...
      }
    }
  }
}

Without parameters it creates an _InternalLinkedHashMap instance; other parameter combinations yield specialized internal classes.

Underlying Structure

_InternalLinkedHashMap() {
  _index = new Uint32List(_HashBase._INITIAL_INDEX_SIZE);
  _hashMask = _HashBase._indexSizeToHashMask(_HashBase._INITIAL_INDEX_SIZE);
  _data = new List.filled(_HashBase._INITIAL_INDEX_SIZE, null);
  _usedData = 0;
  _deletedKeys = 0;
}

_index stores a packed integer (hash pattern + entry index) for each bucket, while _data holds keys and values sequentially, preserving insertion order.

Lookup

V? operator [](Object? key) {
  var v = _getValueOrData(key);
  return identical(_data, v) ? null : internal.unsafeCast<V>(v);
}

Object? _getValueOrData(Object? key) {
  final size = _index.length;
  final sizeMask = size - 1;
  final maxEntries = size >> 1;
  final fullHash = _hashCode(key);
  final hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
  int i = _HashBase._firstProbe(fullHash, sizeMask);
  int pair = _index[i];
  while (pair != _HashBase._UNUSED_PAIR) {
    if (pair != _HashBase._DELETED_PAIR) {
      final entry = hashPattern ^ pair;
      if (entry < maxEntries) {
        final d = entry << 1;
        if (_equals(key, _data[d])) {
          return _data[d + 1];
        }
      }
    }
    i = _HashBase._nextProbe(i, sizeMask);
    pair = _index[i];
  }
  return _data;
}

The algorithm uses linear probing: the first probe is a shuffled hash, subsequent probes increment by one. The pair value encodes both the hash pattern and the entry index.

Insertion

void operator []=(K key, V value) {
  final size = _index.length;
  final fullHash = _hashCode(key);
  final hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
  final d = _findValueOrInsertPoint(key, fullHash, hashPattern, size);
  if (d > 0) {
    _data[d] = value;
  } else {
    final i = -d;
    _insert(key, value, hashPattern, i);
  }
}

If the key exists, its value slot in _data is overwritten; otherwise a new slot is allocated in _index and the key/value are appended to _data .

Resize / Rehash

void _rehash() {
  if ((_deletedKeys << 2) > _usedData) {
    _init(_index.length, _hashMask, _data, _usedData);
  } else {
    _init(_index.length << 1, _hashMask >> 1, _data, _usedData);
  }
}

void _init(int size, int hashMask, List? oldData, int oldUsed) {
  _index = new Uint32List(size);
  _hashMask = hashMask;
  _data = new List.filled(size, null);
  _usedData = 0;
  _deletedKeys = 0;
  if (oldData != null) {
    for (int i = 0; i < oldUsed; i += 2) {
      var key = oldData[i];
      if (!_HashBase._isDeleted(oldData, key)) {
        this[key] = oldData[i + 1];
      }
    }
  }
}

If more than half of the entries are marked deleted, a rehash with the same size removes the tombstones; otherwise the array size doubles.

Deletion

V? remove(Object? key) {
  final size = _index.length;
  final sizeMask = size - 1;
  final maxEntries = size >> 1;
  final fullHash = _hashCode(key);
  final hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
  int i = _HashBase._firstProbe(fullHash, sizeMask);
  int pair = _index[i];
  while (pair != _HashBase._UNUSED_PAIR) {
    if (pair != _HashBase._DELETED_PAIR) {
      final entry = hashPattern ^ pair;
      if (entry < maxEntries) {
        final d = entry << 1;
        if (_equals(key, _data[d])) {
          _index[i] = _HashBase._DELETED_PAIR;
          _HashBase._setDeletedAt(_data, d);
          V value = _data[d + 1];
          _HashBase._setDeletedAt(_data, d + 1);
          ++_deletedKeys;
          return value;
        }
      }
    }
    i = _HashBase._nextProbe(i, sizeMask);
    pair = _index[i];
  }
  return null;
}

Deletion marks the bucket as _DELETED_PAIR and the corresponding slots in _data as deleted, increasing the deleted‑key counter.

Iteration

bool moveNext() {
  if (_table._isModifiedSince(_data, _checkSum)) {
    throw new ConcurrentModificationError(_table);
  }
  do {
    _offset += _step;
  } while (_offset < _len && _HashBase._isDeleted(_data, _data[_offset]));
  if (_offset < _len) {
    _current = internal.unsafeCast<E>(_data[_offset]);
    return true;
  } else {
    _current = null;
    return false;
  }
}

Because _data stores entries in insertion order, iteration naturally follows that order, skipping deleted slots.

Conclusion

Dart's HashMap and LinkedHashMap implementations are relatively straightforward, using array‑plus‑linked‑list for HashMap and a dual‑array linear‑probing scheme for LinkedHashMap . While they lack some of the sophisticated optimizations found in Java's JDK, the core design ideas are similar, making it easy for developers familiar with Java to understand Dart's map behavior.