News for hackers. Stuff that matters.
Re:How to implement a hash table in C by coliveira on Friday March 26, 2021 @06:40PM (#26597873)
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.
Re:How to implement a hash table in C by vladf on Sunday March 28, 2021 @11:45AM (#26611271)
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.)

Re:How to implement a hash table in C by rurban on Saturday March 27, 2021 @03:53AM (#26600740)
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.