ServerFrame::HashMap VS stl::unordered_map-性能探究之旅

作者：池育龍 2017-09-13 10:04:41

突然就對項目中的HashMap有了強烈的好奇心，這個HashMap的實現夠高效嗎，和 std::unordered_map 的效率比較性能如何?

[[203360]]

1. 引言

突然就對項目中的HashMap有了強烈的好奇心，這個HashMap的實現夠高效嗎，和 std::unordered_map 的效率比較性能如何? 他們的插入效率、查找效率、空間使用率對比起來是分別是什么樣的?也沒有找到相關的測評，于是就自己動手，測試了一下，并對一些影響性能的地方修改、驗證自己的猜想，最終得到一個比較好的hashmap的實踐。整個過程還是比較有意思的，現記錄并分享出來。

1.1 好了別的不說了給我結論就好

好吧，大家都很忙，先給一下簡要結論，時間緊迫的同學也可以直接跳到文尾查看結論小節.

ServerFrame::HashMap 的哈希算法算出來的哈希值散列度不夠，key的長度越長，散列能力越差，性能越差。
因為沖突處理的緣故，本文所做的幾個用例中，極端情況下 ServerFrame::HashMap 的表現比 stl::unordered_map 差100倍;
哈希算法散列程度足夠的時候，ServerFrame::HashMap 的表現比 stl::unordered_map 好。前者的插入效率是后者的10倍，查找效率3倍;
存儲同樣的數據,HashMap 耗內存多于 unordered_map;

1.2 show me the code

本文用到的測試代碼和測試結果全部在 git.oa.com中，有興趣的同學可以下載查看。

倉庫路徑:http://git.code.oa.com/lawrencechi/hashmap-benchmark.git 
成文時倉庫版本 tag:v2.0 
內存: 12G 
cpu 2核:   i7-6700 CPU 3.40GHz 
ServerFrame::HashMap: 編譯時預設的容量是 8000萬 
 
測試用例: 
lawrencechi@lawrencechi-VirtualBox /data/hashmap-benchmark/hashmap-benchmark/build ±master:zap: » ./bm_hashmap.O2 
Usage: bm_hashmap.O2 [-n count] -hijklmop 
   -h: hashmap-int 
   -i: hashmap-string(32 byte) 
   -j: unordered-map-int 
   -k: unordered-map-string 
   -l: hashmap(32 byte)) idx 
   -m: hash<string> idx 
   -o: hashmapplus(32 byte)) idx 
   -p: hashmapplus-string(32 byte))

2.int類型key

2.1用例結果

執行./bm_hashmap.O2 -n 700 -hj,獲得數據，并繪制圖表如下(畫圖數據經過省略，但關鍵信息還在,下同)

[圖: 2.1插入耗時 ]

[ 圖:2.1查找耗時 ]

總體來看，兩個實現的效率都很高，穩定(斜率不變，意味著單位時間內插入條數沒有變化)，插入8000萬條數據最多只需要4.5s，在使用 ServerFrame::HashMap插入數據的時候，HashMap甚至能夠達到 stl::unordered_map的10倍;當key不存在的時候，HashMap 查找速度也比 unordered_map 快4倍， key 存在的時候，容量少于5000萬條時，HashMap 比 unordered_map 快，只有大于5000萬時，兩者查找的速度才相差不大。

這次測試看起來 HashMap 實現得非常完美，很好地解決了預設需求，插入效率高、查找效率高。雖然耗費的內存多，僅存8000萬個int的 HashMap 需要 3.5G 的內存，但現代服務器內存充足，這個缺點似乎是可以忍受的。

除了內存之外，ServerFrame::HashMap 的實現就沒有其他的缺點了嗎? 很快，我就想到了他的 Hash 函數和沖突處理，決定從這里入手繼續分析。

2.2 隱憂:hash算法

ServerFrame::HashMap 的 hash 算法實現是將 key 的 buffer(sizeof(key))，按照 int 字節累加，并將其結果和哈希表容量進行取余，簡單粗暴，而且似乎也符合大道至簡的理論。但是仔細想想,這個地方的實現違背了哈希算法的原則:均衡性。一個不夠均衡性的算法會導致大量沖突，最終使得HashMap在反復的沖突處理中疲于奔命。

很簡單，按照這個算法下面的這些數據算得到的哈希值都是一樣的,而且這樣的數據可以輕易地構造:

0xFFFFFFFF, 
0xFFFFFFFF 00000000 
0xFFFFFFFF 00000000 00000000 
0xFFFFFFFF 00000000 00000000 00000000

最為對比，我們都知道構造兩個擁有同樣MD5值的數據是何等的困難。

而且仔細分析一下可以知道 2.1 用例剛好繞過了這個算法的缺陷，取到的key都不會相互沖突! 這時候的測試結果恰恰是最優結果!

如果沖突了會怎么樣,測試結果變成怎么樣? 在好奇心驅使下，我馬上進行 3.1 用例的測試。

3. buffer(32byte)類型

3.1用例結果

執行./bm_hashmap.O2 -n 700 -ik,獲得數據，并繪制圖表如下

[圖： 3.1插入耗時 ]

從上圖可以看到，對于buffer類型的key,性能表現差異很大.

從HashMap的圖來看，越到后面斜率越大，說明到后面的時候，插入單位條數的耗時已經急劇增長。這是符合我們的設想的，此時程序在拼命進行沖突處理!

從圖中還可以得到一個信息，插入7000萬條數據，HashMap的耗時是接近2500秒,也就是41分鐘!

至于unordered_map,上圖已經分析不出什么東西來，和HashMap比起來，它的變化太緩慢了。我只能抽出來單獨分析，圖如下:

[ [圖：3.1插入耗時-unordered_map ]

unordered_map 斜率幾乎不變，可以知道每次插入的耗時是相同的,穩定，插入7000萬條數據，耗時25s，HashMap差不多是他的100倍。

從上面的測試結果可知 HashMap 的效率的確是急劇下降，但是這個急劇下降是 Hash 算法引起的嗎? 還是需要定量分析!

4. hash 算法比較

4.1 unordered_map

stl::unordered_map 是C++11引進的,老版本也有，只是沒有提供接口出來供外部使用。

恰好手頭上有 gcc 4.9.3 的代碼，于是一探究竟

//代碼片段 ================== 
    //file:/data/study/gcc/gcc.4.9.3/gcc-4.9.3/libstdc++-v3/libsupc++/hash_bytes.cc +73 
    size_t _Hash_bytes(const void* ptr, size_t len, size_t seed) 
    { 
        const size_t m = 0x5bd1e995; 
        size_t hash = seed ^ len; 
        const char* buf = static_cast<const char*>(ptr); 
 
        // Mix 4 bytes at a time into the hash. 
        while(len >= 4) 
        { 
            size_t k = unaligned_load(buf); 
            k *= m; 
            k ^= k >> 24; 
            k *= m; 
            hash *= m; 
            hash ^= k; 
            buf += 4; 
            len -= 4; 
        } 
 
        // Handle the last few bytes of the input array. 
        switch(len) 
        { 
            case 3: 
                hash ^= static_cast<unsigned char>(buf[2]) << 16; 
            case 2: 
                hash ^= static_cast<unsigned char>(buf[1]) << 8; 
            case 1: 
                hash ^= static_cast<unsigned char>(buf[0]); 
                hash *= m; 
        }; 
 
        // Do a few final mixes of the hash. 
        hash ^= hash >> 13; 
        hash *= m; 
        hash ^= hash >> 15; 
        return hash; 
    }

對于可以轉換成 size_t 類型的key，hash提供了幾個特化哈希函數，直接返回((size_t)key)，上面的哈希函數是buffer類型的哈希函數，傳入起始地址，得到哈希值。這個hash算法用了幾個魔數，各種位運算得到一個 int32 的值，好吧，此時我已經不知道怎么才能構造兩個碰撞數據了。

最為對比，HashMap的hash函數如下:

template <typename KEY_TYPE, typename DATA_TYPE, int NODE_SIZE, typename CMP_FUNC, int HASH_SIZE> 
int CHashMap<KEY_TYPE, DATA_TYPE, NODE_SIZE, CMP_FUNC, HASH_SIZE>::HashKeyToIndex(const KEY_TYPE& rstKey, int& riIndex) const 
{ 
    size_t uiKeyLength = sizeof(rstKey); 
    unsigned int uiHashSum = 0; 
 
    //目前Hash算法實現比較簡單只是將Key值的每個字節的值加起來并對SIZE取模 
    unsigned int i; 
    for( i = 0; i < uiKeyLength / sizeof(unsigned int); ++i) 
    { 
        unsigned int uiTmp = 0; 
        memcpy(&uiTmp, ((char*)(&rstKey))+sizeof(uiTmp)*i, sizeof(uiTmp)); 
        uiHashSum += uiTmp; 
    } 
 
    if(uiKeyLength % sizeof(unsigned int) > 0) 
    { 
        unsigned char* pByte = (unsigned char*)&rstKey; 
        pByte += (uiKeyLength - (uiKeyLength % sizeof(unsigned int))); 
        unsigned int uiTemp = 0; 
        memcpy((void *)&uiTemp, (const void *)pByte, uiKeyLength%sizeof(unsigned int)); 
        uiHashSum += uiTemp; 
    } 
 
    uiHashSum = (uiHashSum & ((unsigned int)0x7fffffff)); 
    riIndex = (int)(uiHashSum % HASH_SIZE); 
    return 0; 
}