文章連結：https://yenslife.notion.site/Problem-1-Hashing-647ee1b56ac34d668c0aba935289e99b

(按三角形可以展開文字方塊)

• 題目

Bloom Filter 實作及測試 (完整版)

1. 先用亂數填滿 A 以及 B 兩字串陣列，兩個陣列分別為互斥集合，陣列大小各為 500

• 使用以下程式來產生字串， A 和 B 的 element 字串大小分別為 13 和 10 個字元 (必定互斥)

// 參考 <https://stackoverflow.com/questions/440133/how-do-i-create-a-random-alpha-numeric-string-in-c>

#include <ctime>
#include <iostream>
#include <unistd.h>

using namespace std;

string gen_random(const int len) {
    char alphanum[] =
        "0123456789"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";
    string tmp_s;
    tmp_s.reserve(len);

    for (int i = 0; i < len; ++i) {
        tmp_s += alphanum[rand() % (sizeof(alphanum) - 1)];
    }
    
    return tmp_s;
}

// g++ -std=c++11 random_string.cpp && ./a.out > random1.txt
int main(int argc, char *argv[]) {
    srand((unsigned)time(NULL) * getpid());  
    for (int i = 0; i < 500; i++) {
        cout << " , "   << '\\"' << gen_random(10) << '\\"';       
    }  
    for (int i = 500; i < 1000; i++) {
        //cout << " , "   << '\\"' << i << '\\"';   
    }
    return 0;
}

char A[][500] = { "RwKpfFGiqKvo1" , "CGpjs34vhZcZy" ......};
char B[][500] = { "WSmiWTqHyY" , "z6VzyjLdaE" ,     ......};

2. 準備 100 個 hash function，並放到 function pointer 陣列 func_arr

• hash function 會回傳一個小於 MAX_M 的數值，MAX_M 是 bloom filter 的位元串的最大值，數字根據 傳入字串的 ascii code 總合來計算，計算規則都是將字串乘以一個數字再加上一個數字，中間都是我亂打的。( e.g. 傳入字串若為 ”0” ，則 sumOfString(str) 回傳 48，如果是 fun0 就會回傳 ( $48 \times 113223212 + 1024349999)\ \%\ MAX\_M$ )

int (*func_arr[MAX_H])(char*);  // function pointer array

int fun0(char* str) { return (sumOfString(str) * 113223212 + 1024349999) % MAX_M; }
int fun1(char* str) { return (sumOfString(str) * 23244112 + 102451111) % MAX_M; }
int fun2(char* str) { return (sumOfString(str) * 2078395245101 + 102653765) % MAX_M; }
.
.
.
int fun98(char* str) { return (sumOfString(str) * 5654431209810 + 734595323458) % MAX_M ;}
int fun99(char* str) { return (sumOfString(str) * 5654431222155 + 765439535659) % MAX_M ;}

• 放入 func_arr ，使用 putFuncIntoArr 一個一個放 ( 因為都是按照順序所以可以用另一個程式來印出結果，複製貼上 )

void putFuncIntoArr() {
    func_arr[0] = fun0;
    func_arr[1] = fun1;
    func_arr[2] = fun2;
.
.
.
		func_arr[99] = fun99;
}

3. 全域變數代表的值、main function 中的變數

• 全域變數

#define MAX_M 2000 // bloom filter 的位元串的最大值，隨時可以更動
#define MAX_H 100  // hash function 的最大數量，可以觀察從 1 ~ 100 的變化
#define TRUE 1     // boolean
#define FALSE 0    // boolean

int F[MAX_M] = {0};// bloom filter 的位元串