C++ 哈希表基本用法

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

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

為什么要用哈希表

如果現(xiàn)在做哈希表的題目，是因為按專題刷的哈希表的題目，所以會直接用哈希表。但是遇到一道新的題目，沒有標(biāo)簽，怎么想到使用哈希表呢？

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

遍歷

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

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

查找

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

注意：hash.count(x) 的數(shù)值只有 0 和 1。所以不能通過hash.count(x)來表示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中，然后通過hash[key] -- 使得hash[key] == 0，hash 中還會存在key ，也就是說此時hash.count(key) == 1。

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

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

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

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

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

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

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

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

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

哈希函數(shù)

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

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

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

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

此時問題又來了，哈希表我們剛剛說過，就是一個數(shù)組。

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

接下來哈希碰撞登場！

哈希碰撞

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

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

拉鏈法

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

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

其實拉鏈法就是要選擇適當(dāng)?shù)墓１淼拇笮?，這樣既不會因為數(shù)組空值而浪費(fèi)大量內(nèi)存，也不會因為鏈表太長而在查找上浪費(fèi)太多時間。

線性探測法

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

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

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

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

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

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

這里數(shù)組就沒啥可說的了，我們來看一下set。

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

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

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

當(dāng)我們要使用集合來解決哈希問題的時候，優(yōu)先使用unordered_set，因為它的查詢和增刪效率是最優(yōu)的，如果需要集合是有序的，那么就用set，如果要求不僅有序還要有重復(fù)數(shù)據(jù)的話，那么就用multiset。

那么再來看一下map ，map是一個key value的數(shù)據(jù)結(jié)構(gòu)，在map中，對key是有限制，對value沒有限制的，因為key的存儲方式使用紅黑樹實現(xiàn)。

其他語言例如：java里的HashMap ，TreeMap 都是一樣的原理?？梢造`活貫通。

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

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

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

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

但是哈希法也是犧牲了空間換取了時間，因為我們要使用額外的數(shù)組，set或者是map來存放數(shù)據(jù)，才能實現(xiàn)快速的查找。

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

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

最新評論