A new hash table for the Lwan web server
3 points by lafp
3 points by lafp
Now there's a name I have not heard in a long, long time...
The H2 hash has only 7 bits, with one bit left to signal if an item is empty, in use, or deleted.
How does all that fit in a single bit?
How does all that fit in a single bit?
"Oh that little guy? Yeah, that's our favorite bit. He's a quantum bit, you see, and can triple your storage space. No, we couldn't afford 8 quantum bits, but one is enough."
Thanks, I'll try making that clearer later.
The upper bit is set if there's nothing in that particular slot; it's unset otherwise. When the upper bit is unset -- that particular slot is full -- H2 fits in the lower 7 bits. When the upper bit is set, other bits in the lower 7 bits can be reused to signal other things.
It might be a good idea to watch the original CppCon 2017 talk about Swiss Tables: https://youtu.be/ncHmEUmJZf4?t=1633
Ah, that makes sense - thank you. I find a little mind bending that the bit is set, means empty, and unset means other data is set... But ok I guess :)