學(xué)習(xí)內(nèi)容來(lái)自C++ STL中哈希表 hash_map

未學(xué)C++之哈希表的使用

map

使用count，返回的是被查找元素的個(gè)數(shù)。如果有，返回1；否則，返回0。注意，map中不存在相同元素，所以返回值只能是1或0。

使用find，返回的是被查找元素的位置，沒(méi)有則返回map.end()。

hash_map基本原理:

使用一個(gè)下標(biāo)范圍比較大的數(shù)組來(lái)存儲(chǔ)元素?？梢栽O(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)，也叫做散列函數(shù)），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)，hash值）相對(duì)應(yīng)，于是用這個(gè)數(shù)組單元來(lái)存儲(chǔ)這個(gè)元素；也可以簡(jiǎn)單的理解為，按照關(guān)鍵字為每一個(gè)元素“分類(lèi)”，然后將這個(gè)元素存儲(chǔ)在相應(yīng)“類(lèi)”所對(duì)應(yīng)的地方，稱(chēng)為桶。

但是，不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的，因此極有可能出現(xiàn)對(duì)于不同的元素，卻計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了“沖突”，換句話說(shuō)，就是把不同的元素分在了相同的“類(lèi)”之中。 總的來(lái)說(shuō)，“直接定址”與“解決沖突”是哈希表的兩大特點(diǎn)

hash_map基于hash table（哈希表）。 哈希表最大的優(yōu)點(diǎn)，就是把數(shù)據(jù)的存儲(chǔ)和查找消耗的時(shí)間大大降低，幾乎可以看成是常數(shù)時(shí)間；而代價(jià)僅僅是消耗比較多的內(nèi)存。然而在當(dāng)前可利用內(nèi)存越來(lái)越多的情況下，用空間換時(shí)間的做法是值得的。另外，編碼比較容易也是它的特點(diǎn)之一。

hash_map，首先分配一大片內(nèi)存，形成許多桶。是利用hash函數(shù)，對(duì)key進(jìn)行映射到不同區(qū)域（桶）進(jìn)行保存。其插入過(guò)程是：

• 得到key
• 通過(guò)hash函數(shù)得到hash值
• 得到桶號(hào)(一般都為hash值對(duì)桶數(shù)求模)
• 存放key和value在桶內(nèi)。
  其取值過(guò)程是:
• 得到key
• 通過(guò)hash函數(shù)得到hash值
• 得到桶號(hào)(一般都為hash值對(duì)桶數(shù)求模)
• 比較桶的內(nèi)部元素是否與key相等，若都不相等，則沒(méi)有找到。
• 取出相等的記錄的value。

hash_map中直接地址用hash函數(shù)生成，解決沖突，用比較函數(shù)解決。這里可以看出，如果每個(gè)桶內(nèi)部只有一個(gè)元素，那么查找的時(shí)候只有一次比較。當(dāng)許多桶內(nèi)沒(méi)有值時(shí)，許多查詢就會(huì)更快了(指查不到的時(shí)候).

由此可見(jiàn)，要實(shí)現(xiàn)哈希表, 和用戶相關(guān)的是：hash函數(shù)和比較函數(shù)。這兩個(gè)參數(shù)剛好是我們?cè)谑褂胔ash_map時(shí)需要指定的參數(shù)。

hash_map和map的區(qū)別在哪里？

• 構(gòu)造函數(shù)。hash_map需要hash函數(shù)，等于函數(shù)；map只需要比較函數(shù)(小于函數(shù)).
• 存儲(chǔ)結(jié)構(gòu)。hash_map采用hash表存儲(chǔ)，map一般采用紅黑樹(shù)(RB Tree)實(shí)現(xiàn)。因此其memory數(shù)據(jù)結(jié)構(gòu)是不一樣的。