【C++從青銅到王者】第二十六篇:哈希

系列文章目錄

文章目錄

• 系列文章目錄
• 前言
• 一、unordered系列關聯式容器
• 二、unordered_map
• • • 1.unordered_map的文檔介紹
    • 2unordered_map的接口介紹
• 三、unordered_set
• 四、底層結構
• • • 1.哈希概念
    • 2.哈希沖突
    • 3.哈希函數
    • 4.哈希沖突的解決之閉散列-線性探測和二次探測
    • 5.哈希沖突的解決之開散列
• 總結

前言

一、unordered系列關聯式容器

在C++98中，STL提供了底層為紅黑樹結構的一系列關聯式容器，在查詢時效率可達到 ，即最差情況下需要比較紅黑樹的高度次，當樹中的節點非常多時，查詢效率也不理想。最好的查詢是，進行很少的比較次數就能夠将元素找到，是以在C++11中，STL又提供了4個unordered系列的關聯式容器，這四個容器與紅黑樹結構的關聯式容器使用方式基本類似，隻是其底層結構不同。本部落格中隻對unordered_map和unordered_set進行介紹，unordered_multimap和unordered_multiset可檢視文檔介紹。

二、unordered_map

1.unordered_map的文檔介紹

unordered_map文檔介紹

1. unordered_map是存儲<key, value>鍵值對的關聯式容器，其允許通過keys快速的索引到與其對應的

   value。

2. 在unordered_map中，鍵值通常用于惟一地辨別元素，而映射值是一個對象，其内容與此鍵關聯。鍵

   和映射值的類型可能不同。

3. 在内部,unordered_map沒有對<kye, value>按照任何特定的順序排序, 為了能在常數範圍内找到key所對應的value，unordered_map将相同哈希值的鍵值對放在相同的桶中。
4. unordered_map容器通過key通路單個元素要比map快，但它通常在周遊元素子集的範圍疊代方面效率較低。
5. unordered_maps實作了直接通路操作符(operator[])，它允許使用key作為參數直接通路value。
6. 它的疊代器至少是前向疊代器。

2unordered_map的接口介紹

注意：該函數中實際調用哈希桶的插入操作，用參數key與V()構造一個預設值往底層哈希桶中插入，如果key不在哈希桶中，插入成功，傳回V()，插入失敗，說明key已經在哈希桶中，将key對應的value傳回。

注意：unordered_map中key是不能重複的，是以count函數的傳回值最大為1。

三、unordered_set

unordered_set文檔介紹

四、底層結構

unordered系列的關聯式容器之是以效率比較高，是因為其底層使用了哈希結構。

1.哈希概念

順序結構以及平衡樹中，元素關鍵碼與其存儲位置之間沒有對應的關系，是以在查找一個元素時，必須要經過關鍵碼的多次比較。順序查找時間複雜度為O(N)，平衡樹中為樹的高度，即O( )，搜尋的效率取決于搜尋過程中元素的比較次數。

理想的搜尋方法：可以不經過任何比較，一次直接從表中得到要搜尋的元素。 如果構造一種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那麼在查找時通過該函數可以很快找到該元素。

2.哈希沖突

用該方法進行搜尋不必進行多次關鍵碼的比較，是以搜尋的速度比較快 問題：按照上述哈希方式，向集合中插入元素44，會出現什麼問題。

對于兩個資料元素的關鍵字 和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同關鍵字通過相同哈希哈數計算出相同的哈希位址，該種現象稱為哈希沖突或哈希碰撞。

把具有不同關鍵碼而具有相同哈希位址的資料元素稱為“同義詞”。發生哈希沖突該如何處理呢？

3.哈希函數

1. <直接定制法–(常用)

   取關鍵字的某個線性函數為散列位址：Hash（Key）= A*Key + B 優點：簡單、均勻 缺點：需要事先知道關鍵字的分布情況 使用場景：适合查找比較小且連續的情況 面試題：字元串中第一個隻出現一次字元

2. 除留餘數法–(常用)

   設散清單中允許的位址數為m，取一個不大于m，但最接近或者等于m的質數p作為除數，按照哈希函數：Hash(key) = key% p(p<=m),将關鍵碼轉換成哈希位址

3. 平方取中法–(了解)

   假設關鍵字為1234，對它平方就是1522756，抽取中間的3位227作為哈希位址； 再比如關鍵字為4321，對它平方就是18671041，抽取中間的3位671(或710)作為哈希位址 平方取中法比較适合：不知道關鍵字的分布，而位數又不是很大的情況

4. 折疊法–(了解)

   折疊法是将關鍵字從左到右分割成位數相等的幾部分(最後一部分位數可以短些)，然後将這幾部分疊加求和，并按散清單表長，取後幾位作為散列位址。

   折疊法适合事先不需要知道關鍵字的分布，适合關鍵字位數比較多的情況

5. 随機數法–(了解)

   選擇一個随機函數，取關鍵字的随機函數值為它的哈希位址，即H(key) = random(key),其中random為随機數函數。通常應用于關鍵字長度不等時采用此法。

6. 數學分析法–(了解)

   設有n個d位數，每一位可能有r種不同的符号，這r種不同的符号在各位上出現的頻率不一定相同，可能在某些位上分布比較均勻，每種符号出現的機會均等，在某些位上分布不均勻隻有某幾種符号經常出現。可根據散清單的大小，選擇其中各種符号分布均勻的若幹位作為散列位址。

4.哈希沖突的解決之閉散列-線性探測和二次探測

閉散列：也叫開放定址法，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那麼可以把key存放到沖突位置中的“下一個” 空位置中去。那如何尋找下一個空位置呢？

1. 線性探測

   比如2.1中的場景，現在需要插入元素44，先通過哈希函數計算哈希位址，hashAddr為4，是以44理論上應該插在該位置，但是該位置已經放了值為4的元素，即發生哈希沖突。

   線性探測：從發生沖突的位置開始，依次向後探測，直到尋找到下一個空位置為止。

插入

• 通過哈希函數擷取待插入元素在哈希表中的位置
• 如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發生哈希沖突，使用線性探測找到下一個空位置，插入新元素

  

  

線性探測優點：實作非常簡單，線性探測缺點：一旦發生哈希沖突，所有的沖突連在一起，容易産生資料“堆積”，即：不同關鍵碼占據了可利用的空位置，使得尋找某關鍵碼的位置需要許多次比較，導緻搜尋效率降低。如何緩解呢？

線性探測的缺陷是産生沖突的資料堆積在一塊，這與其找下一個空位置有關系，因為找空位置的方式就是挨着往後逐個去找，是以二次探測為了避免該問題，找下一個空位置的方法為： = ( + )% m,或者： = ( - )% m。其中：i = 1,2,3…， 是通過散列函數Hash(x)對元素的關鍵碼 key 進行計算得到的位置，m是表的大小。 對于2.1中如果要插入44，産生沖突，使用解決後的情況為：

是以：閉散列最大的缺陷就是空間使用率比較低，這也是哈希的缺陷。

5.哈希沖突的解決之開散列

#pragma once

#include <iostream>
using namespace std;

#include <vector>
#include "Common.h"

// 哈希桶：數組+連結清單(無頭單連結清單)

template<class T>
struct HashBucketNode
{
	HashBucketNode<T>* next;
	T data;

	HashBucketNode(const T& x = T())
		: next(nullptr)
		, data(x)
	{}
};


// T 如果是整形家族
template<class T>
class T2IntDef
{
public:
	const T& operator()(const T& data)
	{
		return data;
	}
};


class Str2Int
{
public:
	size_t operator()(const string& s)
	{
		const char* str = s.c_str();
		unsigned int seed = 131; // 31 131 1313 13131 131313
		unsigned int hash = 0;
		while (*str)
		{
			hash = hash * seed + (*str++);
		}
		return (hash & 0x7FFFFFFF);
	}
};


// 假設：目前實作的哈希表中元素唯一
// T：哈希表中存儲的元素的類型
// T2Int: 将T轉換為整形的結果

template<class T, class T2Int = T2IntDef<T>>
class HashBucket
{
	typedef HashBucketNode<T> Node;
public:
	HashBucket(size_t capacity = 53)
		: table(GetNextPrime(capacity))    // n個值為data的構造方法在構造哈希桶
		, size(0)
	{}

	~HashBucket()
	{
		Destroy();
	}

	/*
	雖然從代碼層面來看，Insert當中存在一個循環，即：周遊連結清單，檢測data是否存在---->表面上Insert的時間複雜度O(N)
	但是實際認為Insert的時間複雜度仍舊為O(1)---->因為：在哈希桶中，每個桶對應的連結清單當中的節點的格式都不是非常多
	*/
	bool Insert(const T& data)
	{
		// 0. 檢測是否需要擴容
		CheckCapacity();

		// 1. 通過哈希函數計算元素所在桶号
		size_t bucketNo = HashFunc(data);

		// 2. 檢測元素是否存在
		Node* cur = table[bucketNo];
		while (cur)
		{
			if (data == cur->data)
				return false;

			cur = cur->next;
		}

		// 3. 插入元素
		cur = new Node(data);
		cur->next = table[bucketNo];
		table[bucketNo] = cur;
		++size;
		return true;
	}

	bool Erase(const T& data)
	{
		// 1. 先通過哈希函數計算元素所在的桶号
		size_t bucketNo = HashFunc(data);

		// 2. 找元素在bucketNo桶中是否處在，存在則删除
		// 核心操作--->删除連結清單當中隻為data的節點
		//  該節點可能是連結清單中的第一個節點
		//  該節點可能是連結清單中的非第一個節點

		Node* cur = table[bucketNo];
		Node* prev = nullptr;   // 标記cur的前一個節點
		while (cur)
		{
			if (data == cur->data)
			{
				// 删除cur節點
				// 删除的節點如果是第一個節點
				if (nullptr == prev)
					table[bucketNo] = cur->next;
				else
					prev->next = cur->next;

				delete cur;
				--size;
				return true;
			}
			else
			{
				// 目前節點不是要找的data，則兩個指針同時往後移動
				prev = cur;
				cur = cur->next;
			}
		}

		// 哈希桶中不存在值為data的元素，無法删除即删除失敗
		return false;
	}

	Node* Find(const T& data)
	{
		// 1. 先通過哈希函數計算元素所在的桶号
		size_t bucketNo = HashFunc(data);

		// 2. 在檢測該元素是否存在對應的連結清單中
		Node* cur = table[bucketNo];
		while (cur)
		{
			if (data == cur->data)
				return cur;

			cur = cur->next;
		}

		return nullptr;
	}

	size_t Size()const
	{
		return size;
	}

	bool Empty()const
	{
		return 0 == size;
	}

	/
	// 為了友善對哈希桶的了解，實作列印哈希桶的方法
	void Print()
	{
		for (size_t i = 0; i < table.capacity(); ++i)
		{
			Node* cur = table[i];

			cout << "table[" << i << "]:";

			while (cur)
			{
				cout << cur->data << "--->";
				cur = cur->next;
			}

			cout << "NULL" << endl;
		}
		cout << "=========================================" << endl;
	}

	void Swap(HashBucket<T, T2Int>& ht)
	{
		table.swap(ht.table);
		std::swap(size, ht.size);
	}

private:
	// 哈希函數---除留餘數法
	size_t HashFunc(const T& data)
	{
		T2Int t2Int;
		return t2Int(data) % table.capacity();
	}

	void Destroy()
	{
		// 循環去銷毀：table中的每個連結清單
		for (size_t i = 0; i < table.capacity(); ++i)
		{
			Node* cur = table[i];

			// 采用：頭删法删除連結清單中的每個節點
			while (cur)
			{
				table[i] = cur->next;
				delete cur;
				cur = table[i];
			}
		}

		size = 0;
	}

	void CheckCapacity()
	{
		if (size == table.capacity())
		{
			// 擴容---将表格放大----然後将桶中的元素往新桶中插入
			HashBucket<T, T2Int> newHT(GetNextPrime(table.capacity()));

			// 将就哈希桶中的節點拆下來，移動到新哈希桶中
			for (size_t i = 0; i < table.capacity(); ++i)
			{
				Node* cur = table[i];
				while (cur)
				{
					// 1. 将cur節點拆下來
					table[i] = cur->next;

					// 2. 将cur節點往newHT中插入
					// 找位置
					size_t bucketNo = newHT.HashFunc(cur->data);

					// 頭插法
					cur->next = newHT.table[bucketNo];
					newHT.table[bucketNo] = cur;
					newHT.size++;

					cur = table[i];
				}
			}

			// 已經将舊哈希桶中的元素全部移動到新哈希桶當中了
			this->Swap(newHT);
		}
	}
private:
	// table當中将來存放所有的連結清單--->實際隻需要存放連結清單首節點的位址
	std::vector<Node*> table;
	size_t size;   // 有效元素的個數
};

           

開散列與閉散列比較:

應用鍊位址法處理溢出，需要增設連結指針，似乎增加了存儲開銷。事實上： 由于開位址法必須保持大量的空閑空間以確定搜尋效率，如二次探查法要求裝載因子a <= 0.7，而表項所占空間又比指針大的多，是以使用鍊位址法反而比開位址法節省存儲空間。

總結

以上就是今天要講的内容，本文介紹了哈希沖突和哈希沖突的解決方法之開散列和閉散列，哈希很好的解決了查找效率問題，哈希提供了大量能使我們快速便捷地了解錯誤的發生，我們務必掌握。另外如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了。