[[203360]]

1. 引言

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

1.1 好了別的不說了給我結(jié)論就好

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

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

1.2 show me the code

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

倉庫路徑:http://git.code.oa.com/lawrencechi/hashmap-benchmark.git 
成文時倉庫版本 tag:v2.0 
內(nèi)存: 12G 
cpu 2核:   i7-6700 CPU 3.40GHz 
ServerFrame::HashMap: 編譯時預(yù)設(shè)的容量是 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用例結(jié)果

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

[圖: 2.1插入耗時 ]

[ 圖:2.1查找耗時 ]

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

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

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

2.2 隱憂:hash算法

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

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

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

最為對比，我們都知道構(gòu)造兩個擁有同樣MD5值的數(shù)據(jù)是何等的困難。

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

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

3. buffer(32byte)類型

3.1用例結(jié)果

執(zhí)行./bm_hashmap.O2 -n 700 -ik,獲得數(shù)據(jù)，并繪制圖表如下

[圖： 3.1插入耗時 ]

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

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

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

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

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

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

從上面的測試結(jié)果可知 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; 
    } 

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

最為對比，HashMap的hash函數(shù)如下:

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算法實現(xiàn)比較簡單只是將Key值的每個字節(jié)的值加起來并對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; 
} 

4.2 用例設(shè)計

4.3 用例結(jié)果

執(zhí)行./bm_hashmap.O2 -n 700 -lm,獲得數(shù)據(jù)，并繪制圖表如下

碰撞太頻繁了，為了可讀性，這里對原始數(shù)據(jù)做了二次統(tǒng)計。統(tǒng)計每一個沖突鏈表的長度，以及key數(shù)量和占比。key數(shù)量之和是 7000萬，占比之和是100%。

這個表格就一目了然了:

• 我們最期望的結(jié)果是沒有沖突，也就是鏈表長度為1，僅占比0.265%!
• 絕大部分的沖突鏈表長度在100以上, 占了總量的 95%.
• 最長的鏈表達到了 5000以上，而且占比 有 0.705%，比我們期望的不沖突的占比還多了3倍。也就是說最差情況的比最好情況多了3倍。

作為對比，stl::unordered_map 的結(jié)果就好看很多了,甚至都不需要進行二次統(tǒng)計、處理:

那么，猜想一下，如果替換掉 ServerFrame::HashMap 的哈希算法，是不是測試的效果就會好很多呢?

5. 升級HashMap hash算法之后測試

開搞，把gcc4.9.3的哈希算法移植到 ServerFrame::HashMap,并放到一個新命名空間中，另存為文件 HashMapPlush.hpp。 重做3.1的測試用例 ./bm_hashmap.O2 -n 700 -lm,獲得數(shù)據(jù)，并繪制圖表如下

可見升級哈希算法之后,沖突還是存在，但是沖突鏈表過長的現(xiàn)象已經(jīng)不存在了，最長的沖突鏈表長度也只有10。此時可以想象耗時數(shù)據(jù)肯定好了很多。

[ 圖：5.1插入耗時 ]

可見，調(diào)整較小，但是效果比較明顯

ServerFrame::HashMap 的插入耗時是 unordered_map 的 1/2;

ServerFrame::HashMap 斜率很穩(wěn)，可見插入耗時比較穩(wěn)定

6. 結(jié)論

從上面的實驗可以看出，影響 HashMap 效率的主要是 哈希算法 和 內(nèi)存分配算法,在哈希算法足夠散列的情況下，預(yù)分配方式的效率更高。

空間換時間的策略是對的，兩個影響因素，另個不夠好的時候，靠空間得到的優(yōu)勢反而會損失;

原文鏈接：https://www.qcloud.com/community/article/625434

【本文是51CTO專欄作者“騰訊云技術(shù)社區(qū)”的原創(chuàng)稿件，轉(zhuǎn)載請通過51CTO聯(lián)系原作者獲取授權(quán)】

戳這里，看該作者更多好文