紹興網(wǎng)站建設(shè)淘寶指數(shù)查詢官網(wǎng)
哈希表
一般哈希表都是用來快速判斷一個元素是否出現(xiàn)在集合里。
哈希函數(shù)
哈希碰撞--解決方法：拉鏈法和線性探測法。
拉鏈法：沖突的元素都被存儲在鏈表中
線性探測法：一定要保證tableSize大于dataSize，利用哈希表中的空位解決碰撞問題。
三種哈希結(jié)構(gòu)
數(shù)組、set（集合）、map（映射）
set與map的共同點：
set、map都是C++的關(guān)聯(lián)容器，只是通過它提供的接口對里面的元素進行訪問，底層都是采用紅黑樹實現(xiàn)。
set與map的不同點：
set：用來判斷一個元素是否在一個組里。
map：映射，相當(dāng)于字典，把一個值映射成另一個值，可以創(chuàng)建字典。
set
map
小結(jié)
當(dāng)要用集合來解決哈希問題時，優(yōu)先使用unordered_set，因為它的查詢和增刪效率是最優(yōu)的，如果需要集合有序，就用set，要有重復(fù)數(shù)據(jù)，就用multiset。
1.為什么要成倍的擴容，而不是一次增加一個固定大小的容量？
保證常數(shù)的時間復(fù)雜度。
2.為什么以兩倍方式擴容？
考慮可能產(chǎn)生的堆空間浪費，所以增長倍數(shù)不能太大。
3.為什么insert后，以前保存的iterator不會失效？
因為map和set儲存的是節(jié)點，不需要內(nèi)存拷貝和內(nèi)存移動。但是vector在插入數(shù)據(jù)時如果內(nèi)存不夠，會重新開辟一塊內(nèi)存。map和set的iterator指向的是節(jié)點的指針，vector指向的是內(nèi)存的某個位置。
4.為什么map和set的插入刪除效率比其他序列容器高？
因為map和set底層實現(xiàn)為紅黑樹，插入和刪除的時間復(fù)雜度為O(logn)。
例題：
有效的字母異位詞（小寫字母，用數(shù)組！）
贖金信（與有效的字母異位詞類似）
兩個數(shù)組的交集(輸出結(jié)果是去重的，無序的，用unordered_set)
兩個數(shù)組的交集II（哈希映射，有重復(fù)元素）
字母異位詞分組（字符串排序的效果、通過設(shè)計哈希表中的鍵值進行歸類）
快樂數(shù)（各個位上數(shù)的提取、判斷是否有重復(fù)的數(shù)字出現(xiàn)，是否出現(xiàn)了死循環(huán)或者出現(xiàn)了1）
兩數(shù)之和（經(jīng)典，利用哈希查詢效率高）
四數(shù)相加II(四個數(shù)組，兩兩分組)
//9、10使用雙指針
三數(shù)之和(雙指針法，對三個元素的去重)
四數(shù)之和（與三數(shù)之和類似，在一級剪枝時，判斷條件要注意，nums[i]>0且target>0，對各個元素進行去重）