學(xué)習(xí)內(nèi)容來自C++ STL中哈希表 hash_map
未學(xué)C++之哈希表的使用
map
使用count焰轻，返回的是被查找元素的個(gè)數(shù)。如果有昆雀，返回1辱志；否則，返回0狞膘。注意揩懒，map中不存在相同元素，所以返回值只能是1或0挽封。
使用find已球，返回的是被查找元素的位置，沒有則返回map.end()辅愿。
hash_map基本原理:
使用一個(gè)下標(biāo)范圍比較大的數(shù)組來存儲(chǔ)元素智亮。可以設(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)点待，也叫做散列函數(shù)）阔蛉，使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)，hash值）相對(duì)應(yīng)癞埠，于是用這個(gè)數(shù)組單元來存儲(chǔ)這個(gè)元素状原；也可以簡(jiǎn)單的理解為，按照關(guān)鍵字為每一個(gè)元素“分類”苗踪，然后將這個(gè)元素存儲(chǔ)在相應(yīng)“類”所對(duì)應(yīng)的地方颠区，稱為桶。
但是通铲，不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的毕莱，因此極有可能出現(xiàn)對(duì)于不同的元素，卻計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了“沖突”央串，換句話說磨澡，就是把不同的元素分在了相同的“類”之中。 總的來說质和，“直接定址”與“解決沖突”是哈希表的兩大特點(diǎn)
hash_map基于hash table（哈希表）稳摄。 哈希表最大的優(yōu)點(diǎn)，就是把數(shù)據(jù)的存儲(chǔ)和查找消耗的時(shí)間大大降低饲宿，幾乎可以看成是常數(shù)時(shí)間厦酬；而代價(jià)僅僅是消耗比較多的內(nèi)存。然而在當(dāng)前可利用內(nèi)存越來越多的情況下瘫想，用空間換時(shí)間的做法是值得的仗阅。另外，編碼比較容易也是它的特點(diǎn)之一国夜。
hash_map减噪，首先分配一大片內(nèi)存，形成許多桶车吹。是利用hash函數(shù)筹裕，對(duì)key進(jìn)行映射到不同區(qū)域（桶）進(jìn)行保存。其插入過程是：
- 得到key
- 通過hash函數(shù)得到hash值
- 得到桶號(hào)(一般都為hash值對(duì)桶數(shù)求模)
- 存放key和value在桶內(nèi)窄驹。
其取值過程是: - 得到key
- 通過hash函數(shù)得到hash值
- 得到桶號(hào)(一般都為hash值對(duì)桶數(shù)求模)
- 比較桶的內(nèi)部元素是否與key相等朝卒，若都不相等，則沒有找到乐埠。
- 取出相等的記錄的value抗斤。
hash_map中直接地址用hash函數(shù)生成，解決沖突丈咐，用比較函數(shù)解決瑞眼。這里可以看出，如果每個(gè)桶內(nèi)部只有一個(gè)元素扯罐，那么查找的時(shí)候只有一次比較负拟。當(dāng)許多桶內(nèi)沒有值時(shí)，許多查詢就會(huì)更快了(指查不到的時(shí)候).
由此可見歹河，要實(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一般采用紅黑樹(RB Tree)實(shí)現(xiàn)。因此其memory數(shù)據(jù)結(jié)構(gòu)是不一樣的拭抬。
