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)存空間的浪費（至于為什么會這樣請自行搜索）。

為什么要用哈希表

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

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

遍歷

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

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

查找

查找某個元素是否在哈希表中，可以使用hash.find(x) != hash.end(),或者hash.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)鍵碼的值而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。

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

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

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

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

哈希函數(shù)

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

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

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

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

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

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

接下來哈希碰撞登場！

哈希碰撞

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

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

拉鏈法

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

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

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

線性探測法

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

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

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

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

當我們想使用哈希法來解決問題的時候，我們一般會選擇如下三種數(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值會導致整棵樹的錯亂，所以只能刪除和增加。

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

當我們要使用集合來解決哈希問題的時候，優(yōu)先使用unordered_set，因為它的查詢和增刪效率是最優(yōu)的，如果需要集合是有序的，那么就用set，如果要求不僅有序還要有重復數(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的時候被引入標準庫了，而hash_set并沒有，所以建議還是使用unordered_set比較好，這就好比一個是官方認證的，hash_set、hash_map 是C++11標準之前民間高手自發(fā)造的輪子。

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

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

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

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

最新評論