[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_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.

[sra1, 2017/08/17 18:33:17]

It might be better not to have the hybrid scheme where the main list holds both
pairs and sub-arrays.
With a pure 1-level or 2-level scheme, it should be possible to choose the
1-level or 2-level code with a simple comparison on the mask.
Also, on the transition between 1-level and 2-level, _data can become the first
page without copying (but it still needs to be rehashed)

+  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;
+  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_DATA - 1);
+        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_DATA - 1);
+      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_DATA - 1);
+            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_DATA - 1);
+      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_DATA - 1);
+      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_DATA - 1);
+          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_DATA - 1);
+          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 90 matching lines @@
   _CompactIterator(table, this._data, this._len, this._offset, this._step)
       : _table = table,
         _checkSum = table._checkSum;
 
   bool moveNext() {
     if (_table._isModifiedSince(_data, _checkSum)) {
       throw new ConcurrentModificationError(_table);
     }
     do {
       _offset += _step;
-    } while (_offset < _len && _HashBase._isDeleted(_data, _data[_offset]));
+    } while (_offset < _len &&
+        _offset < _HashBase._MAX_LINEAR_DATA &&
+        _HashBase._isDeleted(_data, _data[_offset]));
+    if (_offset < _len && _offset >= _HashBase._MAX_LINEAR_DATA) {
+      List sublist = _HashBase._indexToList(_data, _offset);
+      int modulus = _offset & (_HashBase._MAX_LINEAR_DATA - 1);
+      while (_HashBase._isDeleted(_data, sublist[modulus])) {
+        _offset += _step;
+        modulus += _step;
+        if (_offset >= _len) break;
+        if (modulus >= _HashBase._MAX_LINEAR_DATA) {
+          modulus = 0;
+          sublist = _HashBase._indexToList(_data, _offset);
+        }
+      }
+    }
     if (_offset < _len) {
-      current = _data[_offset];
+      List sublist = _HashBase._indexToList(_data, _offset);
+      int modulus = _offset & (_HashBase._MAX_LINEAR_DATA - 1);
+      current = sublist[modulus];
       return true;
     } else {
       current = null;

[sra1, 2017/08/17 18:33:17]

If the current sublist from _data is held in a field '_sublist', the logic to
scan would be the same as the old version except at this point we check to move
to the next sublist. Most of this switch to the next sublist could be in a
separate method call. Hopefully the inner loop _sublist scan gets inlined even
if the switch-over does not.

       return false;
     }
   }
 }
 
 // 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_DATA - 1);
+        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_DATA - 1);
+            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_DATA - 1);
+      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_DATA - 1);
+            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_DATA - 1);
+            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);
 }