해싱 기법 소스 코드(No STL)

2중 해싱을 한다.

즉, 하나의 string에 대해 두가지 해시 함수를 각각 써서 서로 다른 두개의 해시값을 만들어낸다.

이렇게 되면 충돌률이 훨씬 낮아지게 된다.

/*
    체이닝, 이중 해싱을 한다.
    충돌률은 1 / (MOD * MOD2)가 된다.
*/
#include <iostream>
 
#define MAX_SIZE 50002
#define MOD 50000
#define MOD2 100000
typedef long long ll;
 
class vector {
public: // 안하면 엑세스 불가(문제 풀이용이라면 그냥 public)
    int capacity;
    int sz;
    int *vc;
    vector() {
        capacity = 8;
        sz = 0;
        vc = new int[capacity];
    }
    ~vector() {
        delete[] vc;
    }
 
    void push_back(int val) {
        if (capacity == sz) {
            int *tmp = new int[capacity];
            for (int i = 0; i < capacity; i++)
                tmp[i] = vc[i];
 
            capacity *= 2;
            delete[] vc;
            vc = new int[capacity];
            for (int i = 0; i < sz; i++)
                vc[i] = tmp[i];
        }
        vc[sz++] = val;
    }
 
    bool empty() {
        return !sz;
    }
    int size() {
        return sz;
    }
    int &operator[] (int i) {
        return vc[i];
    }
    void clear() {
        capacity = 8;
        sz = 0;
        delete[] vc;
        vc = new int[capacity];
    }
};
 
vector hash[MAX_SIZE];
int _strlen(char *str) {
    int len = 0;
    for(;str[len];len++){}
    return len;
}
int makeHash1(char *str) {
    ll ret = 0;
    int len = _strlen(str);
    for (int i = 0; i < len; i++)
        ret = (ret * 13 + str[i]) % MOD + MOD;
 
    return (int)(ret % MOD);
}
int makeHash2(char *str) {
    ll ret = 0;
    int len = _strlen(str);
    for (int i = 0; i < len; i++)
        ret = (ret * 177 + str[i]) % MOD + MOD;
 
    return (int)(ret % MOD);
}
bool findHash(char *str) {
    int hash1 = makeHash1(str);
    int hash2 = makeHash2(str);
    for (int i = 0; i < hash[hash1].size(); i++) {
        if (hash[hash1][i] == hash2) {
            printf("Find Hash! str :: %s hash1 :: %d hash2 :: %d\n", str, hash1, hash2);
            return true;
        }
    }
    return false;
}
int main() {
    int n;
    scanf("%d", &n);
 
    while (n--) {
        int num;
        scanf("%d", &num);
 
        // 해쉬 넣기
        if (num == 1) {
            char str[20];
            scanf("%s", str);
            hash[makeHash1(str)].push_back(makeHash2(str));
        }
 
        // 해쉬 찾기
        else if (num == 2) {
            char str[20];
            scanf("%s", str);
            if (!findHash(str))
                printf("There is no hash value\n");
        }
        
        // 종료
        else
            break;
    }
 
    return 0;
}