C++ 哈希表基本用法

哈希表是一種很常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，我現(xiàn)在平時(shí)刷算法題一般使用C++刷（不要問(wèn)我為什么，懂的都懂）。C++關(guān)于哈希表有很多數(shù)據(jù)結(jié)構(gòu)，平時(shí)使用的比較多的有unordered_set 跟 unordered_map。其中unordered_map 存儲(chǔ)的是鍵值對(duì)。

其實(shí)我們?cè)谀承┣闆r下可以使用數(shù)組構(gòu)建哈希表（具體是哪些情況的呢，自行搜索）。但是數(shù)組的大小是受限制的，而且如果元素很少卻哈希值很大的話會(huì)造成內(nèi)存空間的浪費(fèi)（至于為什么會(huì)這樣請(qǐng)自行搜索）。

為什么要用哈希表

如果現(xiàn)在做哈希表的題目，是因?yàn)榘磳ｎ}刷的哈希表的題目，所以會(huì)直接用哈希表。但是遇到一道新的題目，沒(méi)有標(biāo)簽，怎么想到使用哈希表呢？

咱們要清楚一點(diǎn)的就是，一般哈希表都是用來(lái)快速判斷一個(gè)元素是否出現(xiàn)在集合里。

遍歷

for (auto i = hash.begin(); i != hash.end(); i++)

如果是unordered_map，遍歷的時(shí)候，可以訪鍵值i ->first或者是i->second;

查找

查找某個(gè)元素是否在哈希表中，可以使用hash.find(x) != hash.end(),或者h(yuǎn)ash.count(x) > 0

注意：hash.count(x) 的數(shù)值只有 0 和 1。所以不能通過(guò)hash.count(x)來(lái)表示x在hash 中出現(xiàn)的次數(shù)。

插入

在unordered_set 中插入元素，可以用hash.insert(key)。

在unordered_map中插入元素，可以使用hash[key = value。

刪除

在unordered_set 跟unordered_map 中刪除元素，都用hash.erase(key)。

注意，在unordered_map 中，即使hash[key] == 0，如果之前已經(jīng)將key存入到hash中，然后通過(guò)hash[key] -- 使得hash[key] == 0，hash 中還會(huì)存在key ，也就是說(shuō)此時(shí)hash.count(key) == 1。

在個(gè)別場(chǎng)景下，可能需要一次性刪除 unordered_map 容器中存儲(chǔ)的所有鍵值對(duì)，可以使用clear()方法，其語(yǔ)法格式如下：

void clear()
{
hash.clear();
}

我覺(jué)的刷題會(huì)這些基本的操作足夠了，想深層次的了解哈希表的話自行查閱資料吧。

C++ 哈希表基礎(chǔ)知識(shí)

首先什么是 哈希表，哈希表（英文名字為Hash table，國(guó)內(nèi)也有一些算法書(shū)籍翻譯為散列表）是根據(jù)關(guān)鍵碼的值而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。

直白來(lái)講其實(shí)數(shù)組就是一張哈希表。

哈希表中關(guān)鍵碼就是數(shù)組的索引下標(biāo)，然后通過(guò)下標(biāo)直接訪問(wèn)數(shù)組中的元素，如下圖所示：

那么哈希表能解決什么問(wèn)題呢？一般哈希表都是用來(lái)快速判斷一個(gè)元素是否出現(xiàn)集合里。

例如：要查詢一個(gè)名字是否在這所學(xué)校里。要枚舉的話時(shí)間復(fù)雜度是O(n)，但如果使用哈希表的話， 只需要O(1)就可以做到。我們只需要初始化時(shí)把這所學(xué)校里學(xué)生的名字都存在哈希表里，在查詢的時(shí)候通過(guò)索引直接就可以知道這位同學(xué)在不在這所學(xué)校里了。將學(xué)生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函數(shù)。

哈希函數(shù)

哈希函數(shù)，把學(xué)生的姓名直接映射為哈希表上的索引，然后就可以通過(guò)查詢索引下標(biāo)快速知道這位同學(xué)是否在這所學(xué)校里了。

哈希函數(shù)如下圖所示，通過(guò)hashCode把名字轉(zhuǎn)化為數(shù)值，一般hashcode是通過(guò)特定編碼方式，可以將其他數(shù)據(jù)格式轉(zhuǎn)化為不同的數(shù)值，這樣就把學(xué)生名字映射為哈希表上的索引數(shù)字了。

如果hashCode得到的數(shù)值大于哈希表的大小了，也就是大于tableSize了，怎么辦呢？

此時(shí)為了保證映射出來(lái)的索引數(shù)值都落在哈希表上，我們會(huì)再次對(duì)數(shù)值做一個(gè)取模的操作，就要我們保證學(xué)生姓名一定可以映射到哈希表上了。

此時(shí)問(wèn)題又來(lái)了，哈希表我們剛剛說(shuō)過(guò)，就是一個(gè)數(shù)組。

如果學(xué)生的數(shù)量大于哈希表的大小怎么辦，此時(shí)就算哈希函數(shù)計(jì)算的再均勻，也避免不了會(huì)有幾位學(xué)生的名字同時(shí)映射到哈希表同一個(gè)索引下標(biāo)的位置。

接下來(lái)哈希碰撞登場(chǎng)！

哈希碰撞

如圖所示，小李和小王都映射到了索引下標(biāo) 1 的位置，這一現(xiàn)象叫做哈希碰撞。

一般哈希碰撞有兩種解決方法， 拉鏈法和線性探測(cè)法。

拉鏈法

剛剛小李和小王在索引1的位置發(fā)生了沖突，發(fā)生沖突的元素都被存儲(chǔ)在鏈表中， 這樣我們就可以通過(guò)索引找到小李和小王了：

（數(shù)據(jù)規(guī)模是dataSize， 哈希表的大小為tableSize）

其實(shí)拉鏈法就是要選擇適當(dāng)?shù)墓１淼拇笮?，這樣既不會(huì)因?yàn)閿?shù)組空值而浪費(fèi)大量?jī)?nèi)存，也不會(huì)因?yàn)殒湵硖L(zhǎng)而在查找上浪費(fèi)太多時(shí)間。

線性探測(cè)法

使用線性探測(cè)法，一定要保證tableSize大于dataSize。 我們需要依靠哈希表中的空位來(lái)解決碰撞問(wèn)題。

例如沖突的位置，放了小李，那么就向下找一個(gè)空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就沒(méi)有空置的位置來(lái)存放沖突的數(shù)據(jù)了。如圖所示：

其實(shí)關(guān)于哈希碰撞還有非常多的細(xì)節(jié)，感興趣的同學(xué)可以再好好研究一下，這里我就不再贅述了。

常見(jiàn)的三種哈希結(jié)構(gòu)

當(dāng)我們想使用哈希法來(lái)解決問(wèn)題的時(shí)候，我們一般會(huì)選擇如下三種數(shù)據(jù)結(jié)構(gòu)：

• 數(shù)組
• set（集合）
• map (映射)

這里數(shù)組就沒(méi)啥可說(shuō)的了，我們來(lái)看一下set。

在C++中，set 和 map 分別提供以下三種數(shù)據(jù)結(jié)構(gòu)，其底層實(shí)現(xiàn)以及優(yōu)劣如下表所示：

std::unordered_set底層實(shí)現(xiàn)為哈希表，std::set 和std::multiset的底層實(shí)現(xiàn)是紅黑樹(shù)，紅黑樹(shù)是一種平衡二叉搜索樹(shù)，所以key值是有序的，但key不可以修改，改動(dòng)key值會(huì)導(dǎo)致整棵樹(shù)的錯(cuò)亂，所以只能刪除和增加。

std::unordered_map底層實(shí)現(xiàn)為哈希表，std::map 和std::multimap 的底層實(shí)現(xiàn)是紅黑樹(shù)。同理，std::map 和std::multimap 的key也是有序的（這個(gè)問(wèn)題也經(jīng)常作為面試題，考察對(duì)語(yǔ)言容器底層的理解）。

當(dāng)我們要使用集合來(lái)解決哈希問(wèn)題的時(shí)候，優(yōu)先使用unordered_set，因?yàn)樗牟樵兒驮鰟h效率是最優(yōu)的，如果需要集合是有序的，那么就用set，如果要求不僅有序還要有重復(fù)數(shù)據(jù)的話，那么就用multiset。

那么再來(lái)看一下map ，map是一個(gè)key value的數(shù)據(jù)結(jié)構(gòu)，在map中，對(duì)key是有限制，對(duì)value沒(méi)有限制的，因?yàn)閗ey的存儲(chǔ)方式使用紅黑樹(shù)實(shí)現(xiàn)。

其他語(yǔ)言例如：java里的HashMap ，TreeMap 都是一樣的原理。可以靈活貫通。

雖然std::set、std::multiset的底層實(shí)現(xiàn)是紅黑樹(shù)，不是哈希表，但是std::set、std::multiset依然使用哈希函數(shù)來(lái)做映射，只不過(guò)底層的符號(hào)表使用了紅黑樹(shù)來(lái)存儲(chǔ)數(shù)據(jù)，所以使用這些數(shù)據(jù)結(jié)構(gòu)來(lái)解決映射問(wèn)題的方法，我們依然稱之為哈希法。 map也是一樣的道理。

這里在說(shuō)一下，一些C++的經(jīng)典書(shū)籍上，例如STL源碼剖析，說(shuō)到了hash_set、hash_map，這個(gè)與unordered_set，unordered_map又有什么關(guān)系呢？

實(shí)際上功能都是一樣一樣的， 但是unordered_set在C++11的時(shí)候被引入標(biāo)準(zhǔn)庫(kù)了，而hash_set并沒(méi)有，所以建議還是使用unordered_set比較好，這就好比一個(gè)是官方認(rèn)證的，hash_set、hash_map 是C++11標(biāo)準(zhǔn)之前民間高手自發(fā)造的輪子。

總結(jié)一下，當(dāng)我們遇到了要快速判斷一個(gè)元素是否出現(xiàn)集合里的時(shí)候，就要考慮哈希法。

但是哈希法也是犧牲了空間換取了時(shí)間，因?yàn)槲覀円褂妙~外的數(shù)組，set或者是map來(lái)存放數(shù)據(jù)，才能實(shí)現(xiàn)快速的查找。

如果在做面試題目的時(shí)候遇到需要判斷一個(gè)元素是否出現(xiàn)過(guò)的場(chǎng)景也應(yīng)該第一時(shí)間想到哈希法！

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論