3 ms·

What happens if you have a sequence of puts that triggers an expansion and some keys get migrated, but all of a sudden you get a series of removes, such that yo

• coliveira 6y ago
  Hash tables are not great for data structures that change dramatically in size. If you have this situation, the best thing to do is to copy one hash table into another and discard the original data structure.
  • rurban 6y ago
    Hash tables do that automatically. Rehashing is controlled by various tunable strategies: Load factor (0.5-1), growth policy (primed or power2), growth factor (1.5, golden ratio or 2). Linked list tables don't need to throw away nodes, they can just be relinked. But compaction is always better, because cache dominates. Most rehash do exactly that. Esp. multithreaded. The best thing to do is to take a good one and don't touch it, unless you want a monster as in perl5. Eg the recent siphash security theater broke performance in all dynamic languages, even the linux kernel. Everything is perl now. You don't want that.
  • vladf 6y ago
    I think parent’s construction works just fine if you disallow removes, so it grows monotonically, regardless of how dramatic the increase in keys, so long as you move over 2 keys for every update to your map. My comment was a description of a precise “drastic change” where incrementality becomes sophisticated. (Though in part I was hoping for a response which identifies an elegant approach without the complication I mentioned.)