場(chǎng)景
一直用著 map畔规，unordered_map局扶，但是 map 在 malloc_default_zone 分配內(nèi)存，無(wú)法指定一個(gè)內(nèi)存緩沖池給他，同時(shí)還有很多代碼在 malloc_default_zone 內(nèi)分配內(nèi)存三妈，有個(gè)內(nèi)存泄漏檢測(cè)的業(yè)務(wù)要避免這種干擾畜埋，map 得工作在獨(dú)立的zone內(nèi)，排除這個(gè)zone的泄漏檢測(cè)畴蒲。所以得重新寫(xiě)了悠鞍。
實(shí)現(xiàn)
業(yè)務(wù)上主要的4個(gè)操作有，插入模燥，刪除咖祭，查找，遍歷
插入蔫骂，刪除么翰，查找都好辦，用鄰接表實(shí)現(xiàn)即可辽旋，發(fā)生哈希沖突的時(shí)候浩嫌，用鏈表解決沖突，或者開(kāi)放定址法补胚，或者鏈接+紅黑樹(shù)優(yōu)化码耐。如下
元素x：1, 2, 3, 4, 5, 哈希函數(shù)：x % 3，形成的鄰接表如下
[0] -> 3
[1] -> 1 -> 4
[2] -> 2 -> 5
負(fù)載因子：元素個(gè)數(shù) 5 除以 桶數(shù)量 3 = 1.666溶其，一般是控制在 0.75伐坏，超過(guò)了要擴(kuò)容。
- 重點(diǎn)在于怎么遍歷握联？
假設(shè)有 n 個(gè)桶桦沉，每個(gè)桶的元素個(gè)數(shù)為 f(n)。
簡(jiǎn)單的方法：先遍歷桶金闽，再遍歷桶中的鏈表纯露，那么可以遍歷完，復(fù)雜度 n * f(n)代芜。
極端的情況埠褪，中間有很多空的桶，只有 [0] 上有個(gè) 1挤庇，[100001] 上有個(gè) 2钞速，像這樣：
[0] -> 1
[1] -> NULL
...
[1000000] -> NULL
[1000001] -> 2
那么仍然要遍歷 1000001 個(gè)桶，中間大部分遍歷是浪費(fèi)的嫡秕。
- 怎么解決這種浪費(fèi)渴语？
引入一個(gè)鏈表，因?yàn)殒湵矸奖悴迦雱h除和遍歷昆咽，不方便隨機(jī)讀取驾凶。
一個(gè)元素在加入哈希表的時(shí)候牙甫，也把這個(gè)元素的指針加入到這個(gè)鏈表中。
同理调违，在哈希表中刪除的時(shí)候窟哺，也要通過(guò)元素的一個(gè)指針，把鏈表中對(duì)應(yīng)的節(jié)點(diǎn)刪除技肩。
簡(jiǎn)單來(lái)說(shuō)就是且轨，哈希表，鏈表同步增 / 刪就行虚婿。
那么需要遍歷的時(shí)候旋奢，直接遍歷鏈表就行，其他操作插入和刪除還是在哈希表中操作雳锋。
那么剛剛的 1000001 次遍歷，就可以優(yōu)化到 2 次羡洁。速度加快玷过，同時(shí)內(nèi)存也增加，增加了一個(gè)鏈表所需的內(nèi)存筑煮⌒廖茫空間換時(shí)間。
最后速度測(cè)試：
6s上真仲，100w次調(diào)用袋马，耗時(shí)單位 ms，MyHashMap 是手動(dòng)實(shí)現(xiàn)的秸应，其他是系統(tǒng)庫(kù)的
| Name | 插入 | 查找 | 遍歷 | 清空 |
|---|---|---|---|---|
| MyHashMap | 235 | 18 | 14 | 158 |
| unordered_map | 1508 | 60 | 10 | 106 |
| map | 2276 | 312 | 29 | 120 |
| NSDictionary | 486 | 230 | 14 | 11 |
可以看出 MyHashMap 插入和查找是比較快的虑凛，清空較慢。
