[VM-corelib] Improve performance for very big maps and sets.

runtime/lib/compact_hash.dart

 // Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 import 'dart:typed_data' show Uint32List;
 import 'dart:_internal' as internal;
 
 // Hash table with open addressing that separates the index from keys/values.
 
 abstract class _HashFieldBase {
@@ skipping 53 matching lines @@
   // are doubled when _data is full. Thus, _index will have a max load factor
   // of 1/2, which enables one more bit to be used for the hash.
   // TODO(koda): Consider growing _data by factor sqrt(2), twice as often.
   static const int _INITIAL_INDEX_BITS = 3;
   static const int _INITIAL_INDEX_SIZE = 1 << (_INITIAL_INDEX_BITS + 1);
 
   // Unused and deleted entries are marked by 0 and 1, respectively.
   static const int _UNUSED_PAIR = 0;
   static const int _DELETED_PAIR = 1;
 
+  static const int _MAX_LINEAR_DATA = 4096;
+  static const int _MAX_LINEAR_MASK = 4095;
+  static const int _MAX_LINEAR_DATA_LOG_2 = 12;
+
+  // For sizes up to _MAX_LINEAR_DATA the size of the _data array is just the
+  // size we ask for.  Above that size we add enough elements onto the _data
+  // array to hold _MAX_LINEAR_DATA-sized sub-arrays for the rest of the
+  // entries.
+  static int _sizeToBaseListSize(int size) {
+    if (size <= _MAX_LINEAR_DATA) return size;
+    // Round up.
+    size = ((size - 1) | (_MAX_LINEAR_DATA - 1)) + 1;
+    // First few entries are in the linear area.
+    size -= _MAX_LINEAR_DATA;
+    // Enough entries for the sub-arrays.
+    size >>= _MAX_LINEAR_DATA_LOG_2;
+    return _MAX_LINEAR_DATA + size;
+  }
+
+  static int _baseListSizeToSize(int baseListSize) {
+    if (baseListSize <= _MAX_LINEAR_DATA) return baseListSize;
+    baseListSize -= _MAX_LINEAR_DATA;
+    baseListSize <<= _MAX_LINEAR_DATA_LOG_2;
+    return baseListSize + _MAX_LINEAR_DATA;
+  }
+
+  static List _indexToList(List base, int index) {
+    if (index < _MAX_LINEAR_DATA) return base;
+    index >>= _MAX_LINEAR_DATA_LOG_2;
+    return base[_MAX_LINEAR_DATA - 1 + index];
+  }
+
+  static List _setSublist(List base, int index, List sublist) {
+    assert(index >= _MAX_LINEAR_DATA);
+    index -= _MAX_LINEAR_DATA;
+    index >>= _MAX_LINEAR_DATA_LOG_2;
+    base[_MAX_LINEAR_DATA + index] = sublist;
+  }
+
   // On 32-bit, the top bits are wasted to avoid Mint allocation.
   // TODO(koda): Reclaim the bits by making the compiler treat hash patterns
   // as unsigned words.
   static int _indexSizeToHashMask(int indexSize) {
     int indexBits = indexSize.bitLength - 2;
     return internal.is64Bit
         ? (1 << (32 - indexBits)) - 1
         : (1 << (30 - indexBits)) - 1;
   }
 
   static int _hashPattern(int fullHash, int hashMask, int size) {
     final int maskedHash = fullHash & hashMask;
     // TODO(koda): Consider keeping bit length and use left shift.
     return (maskedHash == 0) ? (size >> 1) : maskedHash * (size >> 1);
   }
 
   // Linear probing.
   static int _firstProbe(int fullHash, int sizeMask) {
     final int i = fullHash & sizeMask;
     // Light, fast shuffle to mitigate bad hashCode (e.g., sequential).
     return ((i << 1) + i) & sizeMask;
   }
 
   static int _nextProbe(int i, int sizeMask) => (i + 1) & sizeMask;
 
   // A self-loop is used to mark a deleted key or value.
   static bool _isDeleted(List data, Object keyOrValue) =>
-      identical(keyOrValue, data);
-  static void _setDeletedAt(List data, int d) {
-    data[d] = data;
+      identical(data, keyOrValue);
+  static void _setDeletedAt(List data, List sublist, int modulus) {
+    sublist[modulus] = data;
   }
 
   // Concurrent modification detection relies on this checksum monotonically
   // increasing between reallocations of _data.
   int get _checkSum => _usedData + _deletedKeys;
   bool _isModifiedSince(List oldData, int oldCheckSum) =>
       !identical(_data, oldData) || (_checkSum != oldCheckSum);
 }
 
 class _OperatorEqualsAndHashCode {
@@ skipping 25 matching lines @@
 
 class _LinkedHashMapMixin<K, V> {
   int get length => (_usedData >> 1) - _deletedKeys;
   bool get isEmpty => length == 0;
   bool get isNotEmpty => !isEmpty;
 
   void _rehash() {
     if ((_deletedKeys << 2) > _usedData) {
       // TODO(koda): Consider shrinking.
       // TODO(koda): Consider in-place compaction and more costly CME check.
-      _init(_index.length, _hashMask, _data, _usedData);
+      _init(_index.length, _hashMask, _data);
     } else {
       // TODO(koda): Support 32->64 bit transition (and adjust _hashMask).
-      _init(_index.length << 1, _hashMask >> 1, _data, _usedData);
+      _init(_index.length << 1, _hashMask >> 1, _data);
     }
   }
 
   void clear() {
     if (!isEmpty) {
-      // Use _data.length, since _index might be null.
-      _init(_data.length, _hashMask, null, 0);
+      int size = _HashBase._INITIAL_INDEX_SIZE;
+      _init(size, _HashBase._indexSizeToHashMask(size), null);
     }
   }
 
   // Allocate new _index and _data, and optionally copy existing contents.
-  void _init(int size, int hashMask, List oldData, int oldUsed) {
+  void _init(int size, int hashMask, List oldData) {
     assert(size & (size - 1) == 0);
     assert(_HashBase._UNUSED_PAIR == 0);
     _index = new Uint32List(size);
     _hashMask = hashMask;
-    _data = new List(size);
+    if (_deletedKeys == 0 && _data == oldData) {
+      _rebuildIndex(size, oldData);
+      return;
+    }
+    _data = new List(_HashBase._sizeToBaseListSize(size));
+    int oldUsed = _usedData;
     _usedData = 0;
     _deletedKeys = 0;
     if (oldData != null) {
       for (int i = 0; i < oldUsed; i += 2) {
-        var key = oldData[i];
+        List sublist = _HashBase._indexToList(oldData, i);
+        int modulus = i & _HashBase._MAX_LINEAR_MASK;
+        var key = sublist[modulus];
         if (!_HashBase._isDeleted(oldData, key)) {
           // TODO(koda): While there are enough hash bits, avoid hashCode calls.
-          this[key] = oldData[i + 1];
+          this[key] = sublist[modulus + 1];
         }
       }
     }
   }
 
+  void _rebuildIndex(int size, List oldData) {
+    int dataSize = _HashBase._sizeToBaseListSize(size);
+    if (_data.length != dataSize) {
+      _data = new List(dataSize);
+      for (int i = 0; i < oldData.length; i++) {
+        _data[i] = oldData[i];
+      }
+    }
+    int i = 0;
+    int notYetAdded = _usedData;
+    _usedData = 0;
+    for (; i < notYetAdded && i < _HashBase._MAX_LINEAR_DATA; i += 2) {
+      _setAlreadyThere(oldData[i]);
+    }
+    for (; i < oldData.length; i++) {
+      notYetAdded -= _HashBase._MAX_LINEAR_DATA;
+      List sublist = oldData[i];
+      for (int j = 0; j < notYetAdded && j < sublist.length; j += 2) {
+        _setAlreadyThere(sublist[j]);
+      }
+    }
+  }
+
   int _getIndexLength() {
     return (_index == null) ? _regenerateIndex() : _index.length;
   }
 
   int _regenerateIndex() {
     assert(_index == null);
-    _index = new Uint32List(_data.length);
+    _index = new Uint32List(_HashBase._baseListSizeToSize(_data.length));
     assert(_hashMask == 0);
     _hashMask = _HashBase._indexSizeToHashMask(_index.length);
-    final int tmpUsed = _usedData;
-    _usedData = 0;
-    for (int i = 0; i < tmpUsed; i += 2) {
-      // TODO(koda): Avoid redundant equality tests and stores into _data.
-      this[_data[i]] = _data[i + 1];
-    }
+    _rebuildIndex(_data.length, _data);
     return _index.length;
   }
 
   void _insert(K key, V value, int hashPattern, int i) {
-    if (_usedData == _data.length) {
+    if (_usedData == _getIndexLength()) {
       _rehash();
       this[key] = value;
     } else {
       assert(1 <= hashPattern && hashPattern < (1 << 32));
       final int index = _usedData >> 1;
       assert((index & hashPattern) == 0);
       _index[i] = hashPattern | index;
-      _data[_usedData++] = key;
-      _data[_usedData++] = value;
+      List sublist = _HashBase._indexToList(_data, _usedData);
+      if (sublist == null) {
+        sublist = new List(_HashBase._MAX_LINEAR_DATA);
+        _HashBase._setSublist(_data, _usedData, sublist);
+      }
+      int modulus = _usedData & _HashBase._MAX_LINEAR_MASK;
+      sublist[modulus] = key;
+      sublist[modulus + 1] = value;
+      _usedData += 2;
     }
   }
 
   // If key is present, returns the index of the value in _data, else returns
   // the negated insertion point in _index.
   int _findValueOrInsertPoint(K key, int fullHash, int hashPattern, int size) {
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     int i = _HashBase._firstProbe(fullHash, sizeMask);
     int firstDeleted = -1;
     int pair = _index[i];
     while (pair != _HashBase._UNUSED_PAIR) {
       if (pair == _HashBase._DELETED_PAIR) {
         if (firstDeleted < 0) {
           firstDeleted = i;
         }
       } else {
         final int entry = hashPattern ^ pair;
         if (entry < maxEntries) {
           final int d = entry << 1;
-          if (_equals(key, _data[d])) {
-            return d + 1;
+          List sublist = _HashBase._indexToList(_data, d);
+          if (sublist != null) {
+            int modulus = d & _HashBase._MAX_LINEAR_MASK;
+            if (_equals(key, sublist[modulus])) {
+              return d + 1;
+            }
           }
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return firstDeleted >= 0 ? -firstDeleted : -i;
   }
 
+  // Adds a key to the index where the (key, value) are already in the data.
+  void _setAlreadyThere(K key) {
+    final int size = _getIndexLength();
+    final int sizeMask = size - 1;
+    final int fullHash = _hashCode(key);
+    final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
+
+    final int maxEntries = size >> 1;
+    int i = _HashBase._firstProbe(fullHash, sizeMask);
+    int pair = _index[i];
+    while (pair != _HashBase._UNUSED_PAIR) {
+      i = _HashBase._nextProbe(i, sizeMask);
+      pair = _index[i];
+    }
+
+    assert(1 <= hashPattern && hashPattern < (1 << 32));
+    final int index = _usedData >> 1;
+    assert((index & hashPattern) == 0);
+    _index[i] = hashPattern | index;
+    _usedData += 2;
+  }
+
   void operator []=(K key, V value) {
     final int size = _getIndexLength();
     final int sizeMask = size - 1;
     final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     final int d = _findValueOrInsertPoint(key, fullHash, hashPattern, size);
     if (d > 0) {
-      _data[d] = value;
+      List sublist = _HashBase._indexToList(_data, d);
+      int modulus = d & _HashBase._MAX_LINEAR_MASK;
+      sublist[modulus] = value;
     } else {
       final int i = -d;
       _insert(key, value, hashPattern, i);
     }
   }
 
   V putIfAbsent(K key, V ifAbsent()) {
     final int size = _getIndexLength();
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     final int d = _findValueOrInsertPoint(key, fullHash, hashPattern, size);
     if (d > 0) {
-      return _data[d];
+      List sublist = _HashBase._indexToList(_data, d);
+      int modulus = d & _HashBase._MAX_LINEAR_MASK;
+      return sublist[modulus];
     }
     // 'ifAbsent' is allowed to modify the map.
     List oldData = _data;
     int oldCheckSum = _checkSum;
     V value = ifAbsent();
     if (_isModifiedSince(oldData, oldCheckSum)) {
       this[key] = value;
     } else {
       final int i = -d;
       _insert(key, value, hashPattern, i);
     }
     return value;
   }
 
   V remove(Object key) {
     final int size = _getIndexLength();
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     final int fullHash = _hashCode(key);
     final int 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 int entry = hashPattern ^ pair;
         if (entry < maxEntries) {
           final int d = entry << 1;
-          if (_equals(key, _data[d])) {
+          List sublist = _HashBase._indexToList(_data, d);
+          int modulus = d & _HashBase._MAX_LINEAR_MASK;
+          if (_equals(key, sublist[modulus])) {
             _index[i] = _HashBase._DELETED_PAIR;
-            _HashBase._setDeletedAt(_data, d);
-            V value = _data[d + 1];
-            _HashBase._setDeletedAt(_data, d + 1);
+            _HashBase._setDeletedAt(_data, sublist, modulus);
+            V value = sublist[modulus + 1];
+            _HashBase._setDeletedAt(_data, sublist, modulus + 1);
             ++_deletedKeys;
             return value;
           }
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return null;
   }
 
   // If key is absent, return _data (which is never a value).
   Object _getValueOrData(Object key) {
     final int size = _getIndexLength();
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     final int fullHash = _hashCode(key);
     final int 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 int entry = hashPattern ^ pair;
         if (entry < maxEntries) {
           final int d = entry << 1;
-          if (_equals(key, _data[d])) {
-            return _data[d + 1];
+          List sublist = _HashBase._indexToList(_data, d);
+          int modulus = d & _HashBase._MAX_LINEAR_MASK;
+          if (_equals(key, sublist[modulus])) {
+            return sublist[modulus + 1];
           }
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return _data;
   }
 
   bool containsKey(Object key) => !identical(_data, _getValueOrData(key));
@@ skipping 75 matching lines @@
 
   int get length => _table.length;
   bool get isEmpty => length == 0;
   bool get isNotEmpty => !isEmpty;
 }
 
 class _CompactIterator<E> implements Iterator<E> {
   final _table;
   final List _data;
   final int _len;
+  int _limit;
+  List _currentList;
   int _offset;
   final int _step;
   final int _checkSum;
   E current;
 
   _CompactIterator(table, this._data, this._len, this._offset, this._step)
       : _table = table,
-        _checkSum = table._checkSum;
+        _checkSum = table._checkSum {
+    _limit = -3;
+    _currentList = _data;
+  }
 
   bool moveNext() {
     if (_table._isModifiedSince(_data, _checkSum)) {
       throw new ConcurrentModificationError(_table);
     }
+    int offset = _offset + _step;
+    if (offset < _limit &&
+        !_HashBase._isDeleted(_data,
+            current = _currentList[offset & _HashBase._MAX_LINEAR_MASK])) {
+      _offset = offset;
+      return true;
+    }
+
     do {
+      current = null;
       _offset += _step;
-    } while (_offset < _len && _HashBase._isDeleted(_data, _data[_offset]));
-    if (_offset < _len) {
-      current = _data[_offset];
-      return true;
-    } else {
-      current = null;
-      return false;
-    }
+      int page = _offset >> _HashBase._MAX_LINEAR_DATA_LOG_2;
+      _currentList =
+          page == 0 ? _data : _data[_HashBase._MAX_LINEAR_DATA - 1 + page];
+      if (page == _len >> _HashBase._MAX_LINEAR_DATA_LOG_2) {
+        _limit = _len;
+      } else {
+        _limit = (page + 1) << _HashBase._MAX_LINEAR_DATA_LOG_2;
+      }
+    } while (_offset < _limit &&
+        _HashBase._isDeleted(_data,
+            current = _currentList[_offset & _HashBase._MAX_LINEAR_MASK]));
+
+    return _offset < _limit;
   }
 }
 
 // Set implementation, analogous to _CompactLinkedHashMap.
 class _CompactLinkedHashSet<E> extends _HashFieldBase
     with _HashBase, _OperatorEqualsAndHashCode, SetMixin<E>
     implements LinkedHashSet<E> {
   _CompactLinkedHashSet() : super(_HashBase._INITIAL_INDEX_SIZE >> 1) {
     assert(_HashBase._UNUSED_PAIR == 0);
   }
 
   int get length => _usedData - _deletedKeys;
 
   void _rehash() {
     if ((_deletedKeys << 1) > _usedData) {
-      _init(_index.length, _hashMask, _data, _usedData);
+      _init(_index.length, _hashMask, _data);
     } else {
-      _init(_index.length << 1, _hashMask >> 1, _data, _usedData);
+      _init(_index.length << 1, _hashMask >> 1, _data);
     }
   }
 
   void clear() {
     if (!isEmpty) {
-      _init(_index.length, _hashMask, null, 0);
+      int size = _HashBase._INITIAL_INDEX_SIZE;
+      _init(size, _HashBase._indexSizeToHashMask(size), null);
     }
   }
 
-  void _init(int size, int hashMask, List oldData, int oldUsed) {
+  void _init(int size, int hashMask, List oldData) {
     _index = new Uint32List(size);
     _hashMask = hashMask;
-    _data = new List(size >> 1);
+    if (_deletedKeys == 0 && _data == oldData) {
+      _rebuildIndex(size, oldData);
+      return;
+    }
+    _data = new List(_HashBase._sizeToBaseListSize(size >> 1));
+    int oldUsed = _usedData;
     _usedData = 0;
     _deletedKeys = 0;
     if (oldData != null) {
       for (int i = 0; i < oldUsed; i += 1) {
-        var key = oldData[i];
+        List sublist = _HashBase._indexToList(oldData, i);
+        int modulus = i & _HashBase._MAX_LINEAR_MASK;
+        var key = sublist[modulus];
         if (!_HashBase._isDeleted(oldData, key)) {
           add(key);
         }
       }
     }
   }
 
+  void _rebuildIndex(int size, List oldData) {
+    int dataSize = _HashBase._sizeToBaseListSize(size >> 1);
+    if (_data.length != dataSize) {
+      _data = new List(dataSize);
+      for (int i = 0; i < oldData.length; i++) {
+        _data[i] = oldData[i];
+      }
+    }
+    _usedData = 0;
+    // Unlike in the map case, this Set method is only called when the
+    // data array and sublists are full, so we don't need to keep track of
+    // the number of entries, we can just add everything from the data arrays
+    // to the new index.
+    for (int i = 0; i < oldData.length; i++) {
+      if (i < _HashBase._MAX_LINEAR_DATA) {
+        _addAlreadyThere(oldData[i]);
+      } else {
+        List sublist = oldData[i];
+        for (int j = 0; j < sublist.length; j++) {
+          _addAlreadyThere(sublist[j]);
+        }
+      }
+    }
+  }
+
   bool add(E key) {
     final int size = _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     final int fullHash = _hashCode(key);
     final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
     int i = _HashBase._firstProbe(fullHash, sizeMask);
     int firstDeleted = -1;
     int pair = _index[i];
     while (pair != _HashBase._UNUSED_PAIR) {
       if (pair == _HashBase._DELETED_PAIR) {
         if (firstDeleted < 0) {
           firstDeleted = i;
         }
       } else {
         final int d = hashPattern ^ pair;
-        if (d < maxEntries && _equals(key, _data[d])) {
-          return false;
+        if (d < maxEntries) {
+          List sublist = _HashBase._indexToList(_data, d);
+          if (sublist != null) {
+            int modulus = d & _HashBase._MAX_LINEAR_MASK;
+            if (_equals(key, sublist[modulus])) {
+              return false;
+            }
+          }
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
-    if (_usedData == _data.length) {
+    if (_usedData == maxEntries) {
       _rehash();
       add(key);
     } else {
       final int insertionPoint = (firstDeleted >= 0) ? firstDeleted : i;
       assert(1 <= hashPattern && hashPattern < (1 << 32));
       assert((hashPattern & _usedData) == 0);
       _index[insertionPoint] = hashPattern | _usedData;
-      _data[_usedData++] = key;
+      List sublist = _HashBase._indexToList(_data, _usedData);
+      if (sublist == null) {
+        sublist = new List(_HashBase._MAX_LINEAR_DATA);
+        _HashBase._setSublist(_data, _usedData, sublist);
+      }
+      int modulus = _usedData & _HashBase._MAX_LINEAR_MASK;
+      sublist[modulus] = key;
+      _usedData++;
     }
     return true;
   }
 
+  // Adds a key to the index which is already in the data.
+  void _addAlreadyThere(E key) {
+    final int size = _index.length;
+    final int sizeMask = size - 1;
+    final int maxEntries = size >> 1;
+    final int fullHash = _hashCode(key);
+    final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
+    int i = _HashBase._firstProbe(fullHash, sizeMask);
+    int pair = _index[i];
+    while (pair != _HashBase._UNUSED_PAIR) {
+      i = _HashBase._nextProbe(i, sizeMask);
+      pair = _index[i];
+    }
+
+    assert(1 <= hashPattern && hashPattern < (1 << 32));
+    assert((hashPattern & _usedData) == 0);
+    _index[i] = hashPattern | _usedData;
+    _usedData++;
+  }
+
   // If key is absent, return _data (which is never a value).
   Object _getKeyOrData(Object key) {
     final int size = _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     final int fullHash = _hashCode(key);
     final int 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 int d = hashPattern ^ pair;
-        if (d < maxEntries && _equals(key, _data[d])) {
-          return _data[d]; // Note: Must return the existing key.
+        if (d < maxEntries) {
+          List sublist = _HashBase._indexToList(_data, d);
+          if (sublist != null) {
+            int modulus = d & _HashBase._MAX_LINEAR_MASK;
+            if (_equals(key, sublist[modulus])) {
+              return sublist[modulus]; // Note: Must return the existing key.
+            }
+          }
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return _data;
   }
 
   E lookup(Object key) {
     var k = _getKeyOrData(key);
     return identical(_data, k) ? null : k;
   }
 
   bool contains(Object key) => !identical(_data, _getKeyOrData(key));
 
   bool remove(Object key) {
     final int size = _index.length;
     final int sizeMask = size - 1;
     final int maxEntries = size >> 1;
     final int fullHash = _hashCode(key);
     final int 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 int d = hashPattern ^ pair;
-        if (d < maxEntries && _equals(key, _data[d])) {
-          _index[i] = _HashBase._DELETED_PAIR;
-          _HashBase._setDeletedAt(_data, d);
-          ++_deletedKeys;
-          return true;
+        if (d < maxEntries) {
+          List sublist = _HashBase._indexToList(_data, d);
+          if (sublist != null) {
+            int modulus = d & _HashBase._MAX_LINEAR_MASK;
+            if (_equals(key, sublist[modulus])) {
+              _index[i] = _HashBase._DELETED_PAIR;
+              _HashBase._setDeletedAt(_data, sublist, modulus);
+              ++_deletedKeys;
+              return true;
+            }
+          }
         }
       }
       i = _HashBase._nextProbe(i, sizeMask);
       pair = _index[i];
     }
     return false;
   }
 
   Iterator<E> get iterator =>
       new _CompactIterator<E>(this, _data, _usedData, -1, 1);
@@ skipping 21 matching lines @@
   E lookup(Object o) => _validKey(o) ? super.lookup(o) : null;
   bool remove(Object o) => _validKey(o) ? super.remove(o) : false;
 
   _CompactLinkedCustomHashSet(this._equality, this._hasher, validKey)
       : _validKey = (validKey != null) ? validKey : new _TypeTest<E>().test;
 
   Set<E> toSet() =>
       new _CompactLinkedCustomHashSet<E>(_equality, _hasher, _validKey)
         ..addAll(this);
 }