Dynamic hash tables

> What is the point of having an allocated table that is only partly used?

When the table points to buckets, and space is allocated at the bucket level, not the item level. So having more buckets than you need wastes a LOT of space. Which is cheaper - a few bytes for unused pointers in the table, or many kb for unused space in the buckets?

Each entry in a hash table points to a bucket. A bucket is a linked list of blocks. And a block can contain (in the generic case) any number of items. In this case, a block contains 1 item so there are no savings to be made. But in the Pick case, a block can contain maybe 5 typical items, so the difference between a file with an average 4 items per block or 2 items per block is huge.

Which is why dynamic hashing would make a lot of sense for storing i-nodes in a directory! If doubling the size of the hash table doubles the disk space used by the directory, and each block has space for, say, 10 i-nodes then that's a perfect use-case!

I initially didn't twig that memory was allocated at the item level, and dynamic hashing has been around for absolutely years (probably longer than a lot of people here have been alive!).

So this idea of dynamically splitting a hash table has been around for 40+ years, and in WIDESPREAD commercial use for over 30 of them to my personal knowledge. What's new is the trick of splitting them while they are being actively accessed - Pick databases will lock the bucket while they split it. But they only lock one bucket at a time, and reads only need to outnumber writes by a small amount before the cost of splitting is overwhelmed by the benefits of permanent near-perfect hashing. As your hash file gets bigger, the chances of any individual read tripping over a split/merge operation tends to zero ...

Cheers,
Wol