How Unix spell ran in 64 kB of RAM (2025)
blog.codingconfessions.com
blog.codingconfessions.com
EDIT: Although, https://chatgpt.com/share/6a67336b-8600-83ed-9671-fab769b485... - it is in fact ever so slightly less effective if you have a separate table for each hash function
EDIT2: In the limit, if the number of hash functions equals the number of bits, then we can see that inserting one element would set all bits in the case where we use separate tables, but only 50% of bits if they use one big shared table.
So the false positive rate is higher if they use separate tables.
It would be more effective in avoiding false positives, but require more (typically a lot more) space.
“It would be more effective in avoiding false positives”: consider a single hash function. To get a false positive, a necessary (but not sufficient) condition is that the bit position that it computes is set.
If you use multiple hash functions with a single table, that happens if any of the hash functions produced the same bit position for a different key.
If you use a single hash function for a bit set, your only chance for that to happen is that that same hash function produced the same bit position for a different key. That probability is lower.
“but require more (typically a lot more) space”: if you give each of your k hash function a separate bit-table, memory usage grows by a factor of k.
This is incorrect, although I also initially had the same incorrect intuition, see my (downvoted) comment in the same thread.
By way of illustration: imagine the limit case where you have the same number of bits as hash functions, so there's only 1 bit per hash function. If you have a separate table for each hash function then every input hashes to the same thing so all inputs are indistinguishable.
But if you put all hash functions in the same table that has a number of bits equal to the number of hash functions, then each hash function only sets 1 bit chosen at random based on the input, instead of always setting the same one.