- // If the load of the hash table is more than 3/4, grow it.
- if (NumEntries*4 >= NumBuckets*3) {
+ return InsertIntoBucket(Key, ValueT(), TheBucket)->second;
+ }
+
+private:
+ BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
+ BucketT *TheBucket) {
+ // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
+ // the buckets are empty (meaning that many are filled with tombstones),
+ // grow the table.
+ //
+ // The later case is tricky. For example, if we had one empty bucket with
+ // tons of tombstones, failing lookups (e.g. for insertion) would have to
+ // probe almost the entire table until it found the empty bucket. If the
+ // table completely filled with tombstones, no lookup would ever succeed,
+ // causing infinite loops in lookup.
+ if (NumEntries*4 >= NumBuckets*3 ||
+ NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {