C++でハッシュのマップを実装する

C++のset/mapは、二分木で実装されている。要素数が大きくなると重くなってしまうので（平衡木の回転の処理が重たい？）、ハッシュを使ってmapみたいなものを実装してみた（挿入、参照のみ）。

view plainprint?

1. template <class K, class V>  
2. class hashMap {  
3.     static const unsigned int DEFAULT_SIZE = 1000000;  
4.     vector<pair<K, V> > *contents;  
5.     unsigned int _size;  
6.     unsigned int (*_hashValue) (K, unsigned int);  
7.   
8. public:  
9.     hashMap(unsigned int (*func) (K, unsigned int) , unsigned int size = DEFAULT_SIZE) {  
10.         _hashValue = func;  
11.         _size = size;  
12.         contents = new vector<pair<K, V> > [_size];  
13.     }  
14.   
15.     ~hashMap() {  
16.         delete [] contents;  
17.     }  
18.   
19.     bool hashElement(K s) {  
20.         unsigned int h = _hashValue(s, _size);  
21.   
22.         for (int i = 0; i < (int)contents[h].size(); i++) {  
23.             if (contents[h][i].first == s)  
24.                 return true;  
25.         }  
26.   
27.         return false;  
28.     }  
29.   
30.     void insert(K x, V n) {  
31.         if (hashElement(x))  
32.             return;  
33.   
34.         unsigned int h = _hashValue(x, _size);  
35.         contents[h].push_back(make_pair(x, n));  
36.     }  
37.   
38.     pair<K, V> *getElement(K x) {  
39.         unsigned int h = _hashValue(x, _size);  
40.         for (int i = 0; i < (int)contents[h].size(); i++)  
41.             if (contents[h][i].first == x)  
42.                 return &contents[h][i];  
43.   
44.         return NULL;  
45.     }  
46.   
47.     void printHashBalance() {  
48.         int cnt = 0;  
49.         double ret = 0.0;  
50.         int worst = 0;  
51.   
52.         for (int i = 0; i < (int)_size; i++) {  
53.             if (contents[i].size()) {  
54.                 ++cnt;  
55.                 ret += contents[i].size();  
56.                 worst = max<int>(worst, contents[i].size());  
57.             }  
58.         }  
59.   
60.         if (!cnt)  
61.             cerr << "Hash is empty" << endl;  
62.         else {  
63.             cerr << "collisions occurred(average): " << (ret/cnt) << endl;  
64.             cerr << "collisions occurred(worst): " << worst << endl;  
65.         }  
66.     }  
67. };  

template <class K, class V>
class hashMap {
    static const unsigned int DEFAULT_SIZE = 1000000;
    vector<pair<K, V> > *contents;
    unsigned int _size;
    unsigned int (*_hashValue) (K, unsigned int);

public:
    hashMap(unsigned int (*func) (K, unsigned int) , unsigned int size = DEFAULT_SIZE) {
        _hashValue = func;
        _size = size;
        contents = new vector<pair<K, V> > [_size];
    }

    ~hashMap() {
        delete [] contents;
    }

    bool hashElement(K s) {
        unsigned int h = _hashValue(s, _size);

        for (int i = 0; i < (int)contents[h].size(); i++) {
            if (contents[h][i].first == s)
                return true;
        }

        return false;
    }

    void insert(K x, V n) {
        if (hashElement(x))
            return;

        unsigned int h = _hashValue(x, _size);
        contents[h].push_back(make_pair(x, n));
    }

    pair<K, V> *getElement(K x) {
        unsigned int h = _hashValue(x, _size);
        for (int i = 0; i < (int)contents[h].size(); i++)
            if (contents[h][i].first == x)
                return &contents[h][i];

        return NULL;
    }

    void printHashBalance() {
        int cnt = 0;
        double ret = 0.0;
        int worst = 0;

        for (int i = 0; i < (int)_size; i++) {
            if (contents[i].size()) {
                ++cnt;
                ret += contents[i].size();
                worst = max<int>(worst, contents[i].size());
            }
        }

        if (!cnt)
            cerr << "Hash is empty" << endl;
        else {
            cerr << "collisions occurred(average): " << (ret/cnt) << endl;
            cerr << "collisions occurred(worst): " << worst << endl;
        }
    }
};

これで、参照/挿入はO(1)でできるはず。衝突がどれくらい起きているかを調べるためにprintHashBalance()という関数を定義した。コンストラクタには、使用するハッシュ関数のポインタと、ハッシュ値のサイズを渡す。

適当にテストコードを書いて、標準関数のmapと比較する。WORDS_NUM個のランダムな文字列を、それぞれのコンテナにぶちこんで、最頻出の文字列を求める。

view plainprint?

1. #define WORDS_NUM 10000  
2.   
3. /* 
4. * generate random strings of length between 3 and 8 inclusive 
5. */  
6. vector<string> randomGen() {  
7.     vector<string> ret;  
8.   
9.     for (int i = 0; i < WORDS_NUM; i++) {  
10.         int len = 3 + rand() % 6;  
11.   
12.         char str[len+1];  
13.         for (int j = 0; j < len; j++)  
14.             str[j] = 97 + rand() % 26;  
15.         str[len] = '\0';  
16.   
17.         ret.push_back(str);  
18.     }  
19.   
20.     return ret;  
21. }  
22. /* 
23. * timer 
24. */  
25. class Timer {  
26.     double start_t;  
27. public:  
28.     void start() {  
29.         cout << "Timer Start." << endl;  
30.         start_t = gettimeofday_sec();  
31.     }  
32.   
33.     void end() {  
34.         cout << "Timer stopped." << endl;  
35.         cout << "Time Elapsed: " << gettimeofday_sec() - start_t << endl;  
36.     }  
37. };  
38.   
39. //#define _MAP  
40. #define _HASH  
41.   
42. unsigned int stringHash(string str, unsigned int sz) {  
43.     unsigned int ret = 0;  
44.   
45.     for (int i = 0; i < (int)str.size(); i++)  
46.         ret = 26 * ret + str[i] - 97;  
47.   
48.     return ret % sz;  
49. }  
50.   
51. int main() {  
52.     vector<string> words = randomGen();  
53.     Timer timer;  
54.     timer.start();  
55.   
56. #ifdef _MAP  
57.     map<string, int> wc;  
58.     int cnt = 0;  
59.     string best;  
60.   
61.     for (int i = 0; i < (int)words.size(); i++) {  
62.         if (wc.count(words[i])) {  
63.             int n = ++wc[words[i]];  
64.   
65.             if (n > cnt) {  
66.                 cnt = n;  
67.                 best = words[i];  
68.             }  
69.         }  
70.         else  
71.             wc[words[i]] = 1;  
72.     }  
73.     cout << cnt << ": " << best << endl;  
74. #endif  
75.   
76. #ifdef _HASH  
77.     hashMap<string, int> wc(stringHash, WORDS_NUM);  
78.     int cnt = 0;  
79.     string best;  
80.   
81.     for (int i = 0; i < (int)words.size(); i++) {  
82.         if (wc.hashElement(words[i])) {  
83.             int n = ++wc.getElement(words[i])->second;  
84.   
85.             if (n > cnt) {  
86.                 cnt = n;  
87.                 best = words[i];  
88.             }  
89.         }  
90.         else  
91.             wc.insert(words[i], 1);  
92.     }  
93.     cout << cnt << ":" << best << endl;  
94.     wc.printHashBalance();  
95. #endif  
96.   
97.     timer.end();  
98.   
99.     return 0;  
100. }  

#define WORDS_NUM 10000

/*
* generate random strings of length between 3 and 8 inclusive
*/
vector<string> randomGen() {
    vector<string> ret;

    for (int i = 0; i < WORDS_NUM; i++) {
        int len = 3 + rand() % 6;

        char str[len+1];
        for (int j = 0; j < len; j++)
            str[j] = 97 + rand() % 26;
        str[len] = '\0';

        ret.push_back(str);
    }

    return ret;
}
/*
* timer
*/
class Timer {
    double start_t;
public:
    void start() {
        cout << "Timer Start." << endl;
        start_t = gettimeofday_sec();
    }

    void end() {
        cout << "Timer stopped." << endl;
        cout << "Time Elapsed: " << gettimeofday_sec() - start_t << endl;
    }
};

//#define _MAP
#define _HASH

unsigned int stringHash(string str, unsigned int sz) {
    unsigned int ret = 0;

    for (int i = 0; i < (int)str.size(); i++)
        ret = 26 * ret + str[i] - 97;

    return ret % sz;
}

int main() {
    vector<string> words = randomGen();
    Timer timer;
    timer.start();

#ifdef _MAP
    map<string, int> wc;
    int cnt = 0;
    string best;

    for (int i = 0; i < (int)words.size(); i++) {
        if (wc.count(words[i])) {
            int n = ++wc[words[i]];

            if (n > cnt) {
                cnt = n;
                best = words[i];
            }
        }
        else
            wc[words[i]] = 1;
    }
    cout << cnt << ": " << best << endl;
#endif

#ifdef _HASH
    hashMap<string, int> wc(stringHash, WORDS_NUM);
    int cnt = 0;
    string best;

    for (int i = 0; i < (int)words.size(); i++) {
        if (wc.hashElement(words[i])) {
            int n = ++wc.getElement(words[i])->second;

            if (n > cnt) {
                cnt = n;
                best = words[i];
            }
        }
        else
            wc.insert(words[i], 1);
    }
    cout << cnt << ":" << best << endl;
    wc.printHashBalance();
#endif

    timer.end();

    return 0;
}

以下比較結果。HashMapの_sizeは入力文字数と同じサイズにした。一つのハッシュ値に格納される入力値の種類は平均1.45くらいだった。

WORDS_NUM	100,000	1,000,000	10,000,000
Map [s]	0.346	4.999	66.71
HashMap [s]	0.2	2.052	20.274

もっと速くなると思ったが、どこがネックなんだろう。オーダー的にはハッシュ値の計算が重いけど、実際はvectorのメモリ関連処理が遅そうな気がする。プロファイルとってみるかー。