關(guān)于hash_map和map，知道的不知道的都進(jìn)來看看

wells-xu

大家都知道，map和hash_map用來處理key_value對的高效查找。

遇到這么一個(gè)問題，當(dāng)系統(tǒng)需要存儲(chǔ)一個(gè)key-value對達(dá)到一個(gè)很高的數(shù)量級的時(shí)候，比如千萬級別，插入的時(shí)候hash-map會(huì)因?yàn)閮?nèi)存膨脹達(dá)到某一個(gè)2的n次方的分配點(diǎn)的時(shí)候話費(fèi)很長時(shí)間，如果系統(tǒng)要求高效能的反應(yīng)速度就有矛盾了。但是因?yàn)閙ap的特殊存儲(chǔ)方式，導(dǎo)致不能直接提供和vector類似的reserve事先初始化的方法，所以相當(dāng)遺憾。map雖然和list一樣插入不會(huì)有這樣的重新分配過程，但是查找速度又比hash-map差了大概5倍，敢問有沒有兄弟能幫忙一把，google爛了，都沒有找到好的解決方法。

doofy

你嫌stl的map差，就自己實(shí)現(xiàn)hash表吧  長度選擇你業(yè)務(wù)總量的1/0.6 倍 或者 1/0.8倍  網(wǎng)上不少現(xiàn)成的hash算法，直接拿就成

nicolas.shen

如果實(shí)在有困難，就直接初始化的時(shí)候把內(nèi)存分配好，自己事先分配，避免動(dòng)態(tài)分配

redor

原帖由 wells-xu 于 2009-9-24 15:58 發(fā)表
大家都知道，map和hash_map用來處理key_value對的高效查找。

遇到這么一個(gè)問題，當(dāng)系統(tǒng)需要存儲(chǔ)一個(gè)key-value對達(dá)到一個(gè)很高的數(shù)量級的時(shí)候，比如千萬級別，插入的時(shí)候hash-map會(huì)因?yàn)閮?nèi)存膨脹達(dá)到某一個(gè)2的n ...

謹(jǐn)慎懷疑你插入的key／val為字符類型， 其實(shí)map不適合用來村字符串類型， 因?yàn)楸容^很耗時(shí)， 有個(gè)簡單辦法就是先把字符轉(zhuǎn)換成數(shù)字。。。 然后再放到map里查找排序
字符串和數(shù)字的轉(zhuǎn)換可以使用trie實(shí)現(xiàn)， 這個(gè)效率很高 比hash好用.
我寫過一個(gè)trie實(shí)現(xiàn)，http://hispider.googlecode.com/s ... sk/src/utils/trie.c
http://hispider.googlecode.com/s ... sk/src/utils/trie.h
要多線程需要加一個(gè)
http://hispider.googlecode.com/s ... k/src/utils/mutex.h
編譯的時(shí)候添加-DHAVE_PTHREAD
不然會(huì)不安全

map就是一個(gè)紅黑樹 平均查找效率就是log(N）

wells-xu

謝謝樓上的回復(fù)，將string轉(zhuǎn)換成整形作為key存儲(chǔ)的確是一個(gè)非常不錯(cuò)的創(chuàng)意，高見。

我后來發(fā)現(xiàn)，hashmap在release上面的表現(xiàn)堪稱完美，因?yàn)槲议_始測試都是在debug下面，發(fā)現(xiàn)debug下面每到2^16的時(shí)候出現(xiàn)非常嚴(yán)重的時(shí)間消耗，但是release下面卻快如閃電。所以基本上不用考慮這個(gè)開銷，如果key替換成int的話，效率大概可以提高一倍。