Bloom Filter C implementation

Question

this is my first C program. It creates a bloom filter from an array of N char arrays and k hash functions.

I'm not particularly concerned about maximum performance at this point, as I'm just starting with C. Any suggestions on making my code more idiomatic would be highly appreciated.

// Bloomfilter.c
#include <stdio.h>

// Function headers
int modularHash(char string[], int R, int M);
int sh1(char string[]);
int sh2(char string[]);
int sh3(char string[]);

int main()
{
    enum
    {
        N = 3,  // the number of strings
        M = 10, // the size of the bloom filter
        k = 3,  // the number of hash functions
    };

    char *strings[N] = {"abc", "777", "xyz"};

    int bloom_filter[M] = {0}; // array of `n` 0s.

    // array of pointers to hash functions.
    int (*hashers[k])() = {sh1, sh2, sh3};

    // Fill the bloom filter
    for (int j = 0; j < N; j++)
        for (int i = 0; i < k; i++)
        {
            {
                // Compute the hash of string j using the k'th hash function
                // Map the hash to a position in the bloom filter
                // then add this position to the bloom filter.
                int result = hashers[i](strings[j]);
                int position = result % M;
                bloom_filter[position] = 1;
            }
        }

    // Print the bloom filter
    for (int i = 0; i < M; i++)
        printf("%d ", bloom_filter[i]);


    // TODO implement a function for checking a string against the bloom filter.
    return 0;
}

/*
 Compute the modular hash of a char array
    @param string, array of characters to hash
    @param R: a seed value, should be a prime
    @param M: a seed value, should also be a prime
*/
int modularHash(char string[], int R, int M)
{
    int chars = 3; // the number of characters
    int hash = 0;

    char s;
    int n;

    for (int i = 0; i < chars - 1; i++)
        s = string[i];
    n = (int)s;
    hash = (R * hash + n) % M;
    return hash;
}

int sh1(char string[])
{
    int M = 3;
    int R = 31;
    return modularHash(string, M, R);
}

int sh2(char string[])
{
    int M = 47;
    int R = 17;
    return modularHash(string, M, R);
}

int sh3(char string[])
{
    int M = 97;
    int R = 29;
    return modularHash(string, M, R);
}

```

Answer 1

Questionable code

Why assign s multiple times?

for (int i = 0; i < chars - 1; i++)
    s = string[i];

Above is same as

s = string[chars - 1 - 1];

Instead of one % operation after the loop (R * hash + n) % M, I'd expect that in the loop.

% is not mod

modularHash() returns values in the (-M ... M) range, not [0 ... M) as char may be signed.

Consider the UB caused when result < 0.

int result = hashers[i](strings[j]);
int position = result % M;
bloom_filter[position] = 1;  // UB

Instead, use unsigned math.

unsigned modularHash(char string[], unsigned R, unsigned M) {
  unsigned char *ustring = (unsigned char *) string; 
  ...
  unsigned hash = 0;
  ...
    s = ustring[i];

Avoid signed overflow

R * hash + n, with int math, may overflow with large R leading to undefined behavior (UB). Does not apply with this code given the modest constants.

Use const

In functions that do not alter referenced data, use const. This allows for wider function application, self-documents code's usage and allows select optimization not allows otherwise seen by a compiler.

// int modularHash(char string[], int R, int M)
int modularHash(const char string[], int R, int M)

Avoid hard coded limits

Rather than 3 (an undescribed magic number), consider iterating to end of the string.

unsigned modularHash(const char string[], unsigned char R, unsigned char M) {
  const unsigned char *ustring = (const unsigned char *) string; 
  unsigned hash = 0;

  while (*ustring) {
    hash = (R*hash + *ustring) % M;
  }
  return hash;
}

If looking to limit up to 3, use more descriptive names and consider a string may be shorter than 3.

  int limit = 3;
  for (int i = 0; i < limit && *ustring; i++) {
    hash = (R*hash + *ustring) % M;
  }

Avoid defining twice

Below defines the number of strings twice, once with 3 and once with initializers.

    N = 3,  // the number of strings
char *strings[N] = {"abc", "777", "xyz"};

Consider below, where the string size is only defined by the number of initializers.

char *strings[] = {"abc", "777", "xyz"};
size_t N = sizeof strings / sizeof strings[0];

Likewise for hashers[].

Unclear code

Why -1 in for (int i = 0; i < chars - 1; i++)?