💯 博客內(nèi)容：從零帶你實(shí)現(xiàn)unordered_map

😀 作??者：陳大大陳

🚀 個(gè)人簡(jiǎn)介：一個(gè)正在努力學(xué)技術(shù)的準(zhǔn)C++后端工程師，專注基礎(chǔ)和實(shí)戰(zhàn)分享 ，歡迎私信！

💖 歡迎大家：這里是CSDN，我總結(jié)知識(shí)和寫筆記的地方，喜歡的話請(qǐng)三連，有問題請(qǐng)私信 😘 😘 😘

目錄

超級(jí)容易踩坑的地方

unordered_map怎么實(shí)現(xiàn)

哈希沖突

開放尋址法

代碼

---

?

?unordered_map也就是哈希表，今天就來講解它的用法。

unordered的意思是“無序”,這里強(qiáng)調(diào)了和map功能上的不同，因?yàn)閙ap里面的東西是排好序的。

超級(jí)容易踩坑的地方

它是一個(gè)單向的迭代器。

為什么專門提到這個(gè)呢？因?yàn)檫@是我踩過坑的地方！！

單向迭代器壓根就不能使用sort函數(shù)來排序！

std::unordered_map的迭代器類型是ForwardIterator，而不是sort函數(shù)要求的RandomAccessIterator，這里不符合。

我們要排序的話，還是將unordered_map里存的值，轉(zhuǎn)存到vector<pair>里面。

然后我們?cè)僮远x一個(gè)排序方法，對(duì)vector<pair>進(jìn)行排序。

可參考下面的代碼:

class Solution {
public:struct comp{bool operator()(const pair<string,int>&p1,const pair<string,int>&p2){return p1.second>p2.second||(p1.second==p2.second&&p1.first<p2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> hash;for(auto &str:words) hash[str]++;vector<pair<string,int>> sortV(hash.begin(),hash.end());sort(sortV.begin(),sortV.end(),comp());vector<string> v;for(int i=0;i<k;i++){v.push_back(sortV[i].first);}return v;}
};

692. 前K個(gè)高頻單詞 - 力扣（LeetCode）?

也可以使用std::set結(jié)構(gòu)對(duì)鍵進(jìn)行排序，如下所示：

std::unordered_map<int, int> unordered;
std::set<int> keys;
for (auto& it : unordered) keys.insert(it.first);
for (auto& it : keys) {std::cout << unordered[it] << ' ';
}

unordered_map怎么實(shí)現(xiàn)

哈希沖突

hash也叫散列。

舉一個(gè)例子，學(xué)校圖書館提供借書義務(wù)，怎么快速找到某個(gè)同學(xué)借的書？

我們可以引入一個(gè)關(guān)鍵值（日期），借書記錄存的位置。

哈希和散列就是這樣。

關(guān)鍵值和存儲(chǔ)位置，建立一個(gè)關(guān)聯(lián)關(guān)系。

如果值的跳躍很大，那空間就會(huì)很浪費(fèi)。

有一個(gè)方法可以減少空間浪費(fèi)，就是讓數(shù)值統(tǒng)一對(duì)一個(gè)數(shù)取模。

但是這樣就又會(huì)衍生出一個(gè)問題，就是哈希碰撞，也叫做哈希沖突。

例如，3對(duì)10取模是3,33對(duì)10取模也是3

這樣一來，本來不同位置的兩個(gè)值，現(xiàn)在映射到了相同的位置。

對(duì)于閉散列，我們有一個(gè)方法來解決這種情況。

開放尋址法

當(dāng)前空間已經(jīng)被占用，在開放空間里按照某種規(guī)則，再尋找一個(gè)未被占用的位置存儲(chǔ)。

開放尋址法有兩種方法。

1.線性探測(cè)? hashi+i (i>=0)

2.二次探測(cè)? hashi+i^2 (i>=0)

不需要擔(dān)心后面找不到位置，因?yàn)橛胸?fù)載因子在控制。

負(fù)載因子是當(dāng)前值的個(gè)數(shù)和空間的比率，它會(huì)保持在一個(gè)值一下。

到一定程度，就會(huì)引發(fā)擴(kuò)容。

負(fù)載因子太大，沖突可能會(huì)增加,效率降低。

負(fù)載因子太小，沖突會(huì)變少，但是空間消耗會(huì)增大，空間利用率降低。

要底層實(shí)現(xiàn)哈希表，有一個(gè)很尷尬的問題。

我們不知道如何判斷一個(gè)位置有沒有存值。

因?yàn)閒ind是碰到空就停止，假設(shè)我們刪除了20，那20的位置變?yōu)榭铡?/p>

我們?cè)傧雽ふ?1,22，就找不到了，因?yàn)閒ind在20的位置就停止了。

所以，我們需要區(qū)分開兩種情況，一個(gè)位置是被刪除了而導(dǎo)致空，還是本來就是空。

假設(shè)是本來就是空，那我們到這個(gè)位置就可以停止查找，假設(shè)是被刪除才導(dǎo)致的空，我們就繼續(xù)查找下去。

知道查找到這個(gè)值，或者查找到空為止。

不能直接擴(kuò)容，因?yàn)橛成潢P(guān)系會(huì)改變。

要擴(kuò)容的話，要直接新開一段空間，重新映射，再釋放舊空間。

代價(jià)很大，但是沒有別的方式。

最難想到的就是擴(kuò)容，咱們就新開一段空間，復(fù)用一下插入函數(shù)。

最后用swap交換一下新舊空間的內(nèi)容。

這樣寫的好處是，函數(shù)調(diào)用完成后會(huì)自動(dòng)釋放空間。

下面是第一版的代碼，之后的補(bǔ)全版本代碼會(huì)在接下來幾個(gè)博客中發(fā)出來。

代碼

#pragma once
#include<vector>
namespace bit
{enum Status{EMPTY,EXIST,DELETE};template<class T, class V>struct HashData{pair<K, V> _kv;Status _s;//狀態(tài)};template<class T,class V>class HashTable{public:HashTable(){_tables.resize(10);}bool insert(const pair<K, V>& kv){if (_n*10 / _tables.size() == 0.7) //因?yàn)檎蜗喑豢赡苁?.7,所以乘10,也可以轉(zhuǎn)換成double{size_t NewSize = _tables.size() * 2;HashTable<K, V> newHT;newHT._tables.resize(NewSize);for (int i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){newHT.insert(_tables[i].kv);}}_tables.swap(newHT._tables);}size_t hashi = kv.first % _tables.size();while (_tables[hashi]._s == EXIST){++hashi;//當(dāng)?shù)扔诖嬖跁r(shí)，往后查找hashi %= _tables.size();//防止越界訪問}_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}private:vector<HashData> _tables;size_t _n = 0;//存儲(chǔ)的關(guān)鍵字的個(gè)數(shù)};
}