3 Min Read
Published in

3 Min Read

What are Bloom filters?

A tale of code, dinner, and a favour with unexpected consequences.

Genesis

Hashing

b3f9b3a3504ccb29c4183730a42c8d56
uint32_t SuperFastHash (const char * data, int len) {
uint32_t hash = len, tmp;
int rem;

if (len <= 0 || data == NULL) return 0;
rem = len & 3;
len >>= 2;

/* Main loop */
for (;len > 0; len--) {
hash += get16bits (data);
tmp = (get16bits (data + 2) << 11) ^ hash;
hash = (hash << 16) ^ tmp;
data += 2 * sizeof (uint16_t);
hash += hash >> 11;
}

/* Handle end cases */
switch (rem) {
case 3: hash += get16bits (data);
hash ^= hash << 16;
hash ^= ((signed char)data[sizeof (uint16_t)]) << 18;
hash += hash >> 11;
break;
case 2: hash += get16bits (data);
hash ^= hash << 11;
hash += hash >> 17;
break;
case 1: hash += (signed char)*data;
hash ^= hash << 10;
hash += hash >> 1;
}
/* Force "avalanching" of final 127 bits */
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 4;
hash += hash >> 17;
hash ^= hash << 25;
hash += hash >> 6;

return hash;
}

A quick favour

This

Returning the favour

[mwichary][9:08 AM] BTW I was supposed to send you possible issues to work on: https://github.com/Medium/medium/issues/xxxx
[mwichary][1:24 PM] this is a periodic reminder that you owe me this https://github.com/Medium/medium/issues/xxxxx or a Paul Ford-esque article.

Time and space

Check, please

In Bloom

Digestif

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jamie Talbot

Ex-gaijin, kangaroo-loving software simian from Merrie England, leading folks at @Axios. Formerly @Mailchimp, @Medium, and @StumbleUpon.