Bloom Filter Implementation

Introduction

A Bloom filter is a probabilistic data structure used to test the membership of an element in a set. It was introduced by Burton Howard Bloom in 1970. The primary goal of a Bloom filter is to efficiently determine whether an element is likely to be a member of a large set, with a low probability of false positives.

The Bloom filter operates by using a bit array, typically implemented as a fixed-size array of bits or a bitmap. Initially, all the bits in the array are set to 0. To add an element to the filter, the element is hashed multiple times using different hash functions, and the corresponding bits in the array are set to 1 at the respective hash positions. The number of hash functions used and the size of the array are parameters that influence the performance and accuracy of the filter.

To check if an element is present in the set, the element is hashed using the same hash functions as before, and the corresponding bits in the array are checked. If all the bits are set to 1, the element is probably in the set. However, if any of the bits are 0, the element is definitely not in the set. This property of the Bloom filter makes it susceptible to false positives but not false negatives.

Bloom filters are commonly used in scenarios where approximate membership queries are acceptable and where the cost of false positives is relatively low. They find applications in various fields, including network routers for efficient routing table lookups, web caching to determine if a web page has been accessed before, spell checkers, and duplicate elimination in databases.

It's important to note that Bloom filters do not support element deletion directly, as removing an element would require resetting the corresponding bits in the array, which can cause false negatives for other elements. However, several variants and extensions of Bloom filters exist that address this limitation, such as counting Bloom filters and scalable Bloom filters.

Hash collision

Bloom filters utilize multiple hash functions to mitigate the effects of hash collisions. Hash collisions occur when two different elements produce the same hash value. While collisions are inevitable due to the finite size of the bit array, the use of multiple hash functions helps distribute the collisions across different bits, reducing their impact on the filter's accuracy.

When adding an element to the Bloom filter, it is hashed using multiple independent hash functions, each producing a different hash value. These hash values determine the positions in the bit array where the corresponding bits will be set to 1. By using different hash functions, the likelihood of collisions is reduced because even if two elements produce the same hash value for one function, they are unlikely to produce the same hash values for all the other functions. This increases the spread of the bits set in the bit array.

During membership testing, the same hash functions are applied to the query element, and the corresponding positions in the bit array are checked. If any of the bits are 0, it means that the element is definitely not in the set. However, if all the bits are set to 1, it is probable that the element is in the set due to potential collisions. The probability of false positives increases as more elements are added to the filter and collisions become more likely.

The number of hash functions used and the size of the bit array are design parameters that affect the trade-off between the filter's space usage and its accuracy. Increasing the number of hash functions reduces the probability of collisions but increases the number of bits that need to be checked during membership testing. Similarly, increasing the size of the bit array reduces the probability of false positives but increases the memory requirements.

It's important to note that while Bloom filters can minimize the impact of hash collisions, they cannot completely eliminate them. The probability of false positives can be controlled by adjusting the parameters of the filter, but false negatives (the inability to detect the presence of an element) are not possible with a Bloom filter.

Hash Algorithms

I used the following hash algorithms to implement the bloom filter.

Apply the Kirsch-Mitzenmacher-Optimization to only compute 2 instead of k hash functions (hash_i = hash1 + i x hash2):

unsigned long *_hashes(const char *s, unsigned long max)
{
    unsigned long *hashes = calloc(KHASHES, sizeof(unsigned long));
    unsigned long h = _hash(s);
    int len = strlen(s);
    srand(h * (len * s[0] + s[(len - 1)]));
    unsigned long h2 = h;
    for (int i = 0; i < KHASHES; i++)
    {
        h2 = 33 * h2 ^ rand();
        hashes[i] = h2 % max;
    }
    return hashes;
}

djb2:

/* djb2 Hash function reference:
   http://www.cse.yorku.ca/~oz/hash.html */
unsigned long _hash(const char *s)
{
    unsigned long hash = 5381;
    int c;
    while ((c = *s++))
    {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash;
}

Murmur3

/* Murmur3 Hash function reference:
   https://en.wikipedia.org/wiki/MurmurHash */
uint32_t murmurhash(const void* key, uint32_t len, uint32_t seed) {
    const uint32_t m = 0x5bd1e995;
    const int r = 24;
    uint32_t h = seed ^ len;

    const uint8_t* data = (const uint8_t*)key;

    while (len >= 4) {
        uint32_t k;
        memcpy(&k, data, sizeof(uint32_t));
        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        data += 4;
        len -= 4;
    }

    switch (len) {
        case 3:
            h ^= data[2] << 16;
        case 2:
            h ^= data[1] << 8;
        case 1:
            h ^= data[0];
            h *= m;
    };

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}

Implementation: check if a word is in the dictionary

/* Returns true if the word is already in the dictionary,
   false otherwise.*/
bool dict_spelling(dict *x, const char *s)
{
    if (x == NULL)
    {
        return false;
    }
    // Erace the calibration
    char *rs = eracepunc(s);
    if (strcmp(rs, "") == 0)
    {
        return true;
    }
    unsigned long *h = _hashes(rs, x->size);
    int flag = 0;
    for (int i = 0; i < KHASHES; i++)
    {
        if (x->table[h[i]])
        {
            flag++;
        }
    }
    free(h);
    free(rs);
    return flag == KHASHES;
}