hash_map的特性

hash_map基于hash_table（哈希表）。哈希表最大的優(yōu)點(diǎn)，就是把數(shù)據(jù)的存儲(chǔ)和查找消耗的時(shí)間大大降低，幾乎可以看成是常數(shù)時(shí)間；而代價(jià)僅僅是消耗比較多的內(nèi)存。

hash_table基本原理是：使用一個(gè)下標(biāo)范圍比較大的數(shù)組來存儲(chǔ)元素，使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)，hash值）相對應(yīng)，于是用這個(gè)數(shù)組單元來存儲(chǔ)這個(gè)元素；但是，不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對應(yīng)的，因此極有可能出現(xiàn)對于不同的元素，卻計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了哈希碰撞，需要使用特殊方法解決。

Hashmap的相關(guān)問題

Q：hash_map和map的區(qū)別在哪里？
A：
1.構(gòu)造函數(shù)。hash_map需要hash函數(shù)和比較函數(shù)；map只需要比較函數(shù)。
2.存儲(chǔ)結(jié)構(gòu)。hash_map采用哈希表(Hash Table)存儲(chǔ)，map一般采用紅黑樹(RB Tree)實(shí)現(xiàn)。

Q：什么時(shí)候需要用hash_map，什么時(shí)候需要用map?
A：
1.從查找速度來說，hash_map 查找速度會(huì)比map快，而且查找速度基本屬于常數(shù)級別，而map的查找速度是log(n)級別。并不一定常數(shù)就比log(n)小，hash還有hash函數(shù)的耗時(shí)。當(dāng)數(shù)據(jù)量達(dá)到一定數(shù)量級時(shí)，優(yōu)先考慮hash_map。
2.從內(nèi)存占用來說，希望程序盡可能少消耗內(nèi)存，hash_map會(huì)消耗更多的內(nèi)存，而且hash_map的構(gòu)造速度較慢。

總結(jié)

以上是生活随笔為你收集整理的C++ STL中的Hashmap的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。