How Unix spell ran in 64 kB of RAM (2025)

https://prog21.dadgum.com/29.html

inigyou a day ago | parent | prev | next [-]

Would a bloom filter be more or less effective if each hash function was given a separate bit-table rather than sharing the same one?

▲

Someone a day ago | parent | next [-]

Assuming independent hash functions, giving each hash function it’s own bit table is equivalent to having one bit table with a number of bits equal to that of the sum of the numbers of bits in each hash function.

It would be more effective in avoiding false positives, but require more (typically a lot more) space.

▲

inigyou a day ago | parent [-]

What's your basis for claiming either of these two things?

▲

Someone 11 hours ago | parent [-]

Logic.

“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.

	▲	jstanley 7 hours ago \| parent [-]
		> giving each hash function it’s own bit table is equivalent to having one bit table with a number of bits equal to that of the sum of the numbers of bits in each hash function. 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.

▲

jstanley a day ago | parent | prev [-]

Seems to me that as long as the total number of bits is the same it makes no difference whether each hash function has a separate table or not.

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.

▲

a day ago | parent | prev | next [-]

[deleted]

▲

vee-kay a day ago | parent | prev [-]

[dead]