IIRC, NRK started down this path because normal hash tables without free leak memory on every resize.<p>The original series of articles had me thinking about how to implement the normal hash table without leaking. I think it’s possible:<p>First consider a hash table using linear probing with a dedicated arena (restriction will be lifted later). That means memory can grow for free. However, resizing is still tricky because we need to rehash in place while ensuring we don’t “strand” any entries. This can be accomplished by iterating through the hash table entries in order, but starting at an empty entry and looping around. (Proof left as an exercise for the reader)<p>So now we have a hash table that can use realloc to grow. How to generalize for arenas? The key is that the HT will maintain a page map of sorts. The first page is of size M, the second is of size M, and thereafter they’ll be of size 2^n * M. Basically on each resize we double the total capacity by adding a new page. Since the pages are of variable width, though, how to map indexes to pages quickly? The key is to use ffs or ctz to get a rounded log2.