C++ 哈希表構造及解決哈希沖突的代碼實作

聲明：本人所有測試代碼環境都為vs2017

本文目錄

- 一.哈希的引入及概念
- 二.哈希表的構造
- 三.哈希沖突的産生
- 四.解決哈希沖突的方法及代碼實作

一.哈希的引入及概念

引入：當在順序結構(如數組)或者平衡樹(平衡二叉樹)中查找一個元素時，必須要經過多次與内部元素進行比較的過程，順序結構的查找時間複雜度為O（N），平衡樹的查找時間為Olog(N)，其查找的效率都取決于查找過程中元素的比較次數。

概念：那麼相比之下，最為理想的查找方法是：不經過任何比較，一次直接從表中得到要搜尋的元素。是以，通過構造一種存儲結構，該結構内用某函數可以使得元素的存儲位置與自身值之間的一種一一對應的映射關系，在查找時，通過該函數就可以很快找到元素，這種對應關系就稱之為哈希，元素所存放的空間就稱之為哈希表。

二.哈希表的構造

由于後面解決哈希沖突的方法不同，哈希表的底層構造都不同。比如開放位址法底層借助vector，鍊位址法底層借助單連結清單，是以在這裡分别給出兩種方法的哈希表構造代碼。

開放位址法哈希表的構造代碼：

/*為了簡單，我規定哈希表中不能插入相同的元素。并且，哈希表中删除後的元素位置不能再插入
元素，也就是沒有元素，但是位置還是被占有。是以我在實作代碼時加入了三種狀态：存在，空，
删除。隻有狀态為空的位置才可以插入元素。*/
enum STATE{EMPTY,EXIST,DELETE};//對應狀态

/*封裝元素結構體*/
template <class T>
struct Elem
{
	Elem(const T& data=T())
		:_data(data)
		,_state(EMPTY)
	{}
	T _data;
	STATE _state;
};

/*封裝哈希表*/
//T：元素的類型
//isLine：非模闆類型參數，代表是否選擇線性探測來解決哈希沖突，是--線性探測，否--二次探測
template<class T, bool isLine = true>
class HashTable
{
public:
	HashTable(size_t capacity=10)
		: _size(0)
	{
		_vtable.resize(10);
	}
private:
    //哈希函數
    size_t HashFunc(const T& data)
	{
		return data% _vtable.capacity();
	}
private:
	vector<Elem<T>> _vtable; 
	size_t _size;//哈希表中存儲的有效元素的個數
};

鍊位址法哈希表構造方法

//節點結構體
template <class T>
struct HashNode
{
public:
	HashNode(const T& data = T())
		:_pNext(nullptr)
		,_data(data)
	{}
	HashNode<T>* _pNext;
	T _data;
};
//封裝哈希表
template<class T>
class HashBucket
{
	typedef HashNode<T> Node;
public:
	HashBucket(size_t capacity = 10)
		:_size(0)
	{
		_vtable.resize(10);	
	}
private:
	size_t HashFunc(const T& data)const
	{
		return data % _vtable.capacity();
	}
private:
	vector<Node*> _vtable;//哈希表的每個哈希桶中存儲的是節點的位址
	size_t _size;//有效元素個數
};

三.哈希沖突的産生

概念：不同元素通過哈希函數計算出相同的哈希位址，導緻多個元素要插同一位置引起沖突。

舉一個例子：

假設現在有一組資料集合{1，7，6，4，5，9}，哈希函數使用除留餘數法（哈希函數可以有很多種，常見的有直接定址法，除留餘數法等，具體每種方法的原理參考文章：https://wenku.baidu.com/view/61b121c06137ee06eff918c1.html），設哈為hash（value）=value%10，那麼現在可以通過哈希函數将元素依次存放進哈希表

C++ 哈希表構造及解決哈希沖突的代碼實作

如果此時再插入一個元素55，則hash（55）=55%10=5，是以它和元素5的哈希位址相同，這就是哈希沖突。

四.解決哈希沖突的方法及代碼實作

設計一個合理的哈希函數，但是還是不能從根本上解決
開放定址法（閉散列）：從發生哈希沖突的位置開始，找下一個空位置，找空位置又分為兩種方法：線性探測和非線性探測。

（1）線性探測：從目前位置依次往後找空位置，找到末尾時，位址下标置0，從頭開始查找。

優點：處理哈希沖突方式比較簡單

缺點：一旦發生沖突，容易造成資料的堆積

解決：不挨着往後找空位置，避免産生資料堆積。解決方法：非線性探測裡的二次探測

（2）非線性探測：二次探測：從目前位置，不采用依次往後查找，而通過公式來尋找下一個空位置。公式擷取：H(i+1)=H(i)+2*i+1；i=1,2,3,4…代表查找次數。

找到末尾時，位址下标%表容量，保證每次是不同的位置；不能置0，會引起無休止的探測。

優點：可以解決線性探測中資料堆積的問題

缺點：如果表格中的空位置比較少，容易錯過空位置，可能就需要探測多次

鍊位址法（開散列）：将發生哈希沖突的元素放在同一個連結清單中

具體實作：采用哈希桶

(1)計算目前元素所在桶号

(2)在桶号對應連結清單檢視看桶号位置是否有元素，無則直接插入，有則往下周遊該桶号對應連結清單，直到找到空位置

(3)插入元素

具體的相關函數實作代碼：

開放定址法

//1.插入：
   a.通過哈希函數計算元素在哈希表中的位置
   b.如果目前位置狀态不為empty：
	  (1)如果狀态為exist，且目前位置數值與插入元素數值相同，直接傳回
	  (2)如果狀态為delete或為exist且data不同，則線性探測或者二次探測，直到找到empty的位置為止
   c.插入元素
bool Insert(const T& data)
	{
		//a.通過哈希函數計算元素在哈希表中的位置
		size_t hashAddr = HashFunc(data);
		size_t i = 0;//代表二次探測的探測次數
		
		//b.如果目前位置狀态不為empty：
		while (_vtable[hashAddr]._state != EMPTY)
		{
			//(1)狀态為exist，且目前位置數值與插入元素數值相同，即元素已經存在，直接退出
			if (_vtable[hashAddr]._state == EXIST && _vtable[hashAddr]._data == data)
			{
				return false;
			}
			//(2)狀态為delete或為exist，且元素不存在，則繼續探測

			//線性探測，依次往後周遊查找
			if (isLine)
			{
				hashAddr++;
				if (hashAddr == _vtable.capacity())//位址下标走到末尾
				{
					hashAddr = 0;
				}
			}
			//二次探測
			else
			{
				i++;
				hashAddr = hashAddr + 2 * i + 1;
				hashAddr %= _vtable.capacity();//保證每次是不同的位置
			}

		}
		//c.(循環結束，肯定已經找到空位置)插入元素
		_vtable[hashAddr]._data = data;
		_vtable[hashAddr]._state = EXIST;
		_size++;
		return true;
	}

 //2.查找：
   a.通過哈希函數計算元素在哈希表中的位置
   b.如果目前狀态不為empty：
	   (1)如果狀态為exist且元素相同，傳回目前下标
	   (2)如果狀态為delete或者為exist且data不同，則線性探測或者二次探測，直到找到empty的位置為止
int Find(const T& data)
	{
		//a.通過哈希函數計算元素在哈希表中的位置
		size_t hashAddr = HashFunc(data);

		size_t i = 0;//代表二次探測的探測次數

		//b.如果目前狀态不為empty：
		while (_vtable[hashAddr]._state != EMPTY)
		{
			//(1)如果狀态為EXIST且元素相同，傳回目前下标
			if (_vtable[hashAddr]._state == EXIST && _vtable[hashAddr]._data == data)
			{
				return hashAddr;
			}
			//(2)如果狀态為EXIST且data不同 或者 狀态為DELETE，繼續往後探測
			
			//線性探測
			if (isLine)
			{
				hashAddr++;
				if (hashAddr == _vtable.capacity())//位址下标走到末尾
				{
					hashAddr = 0;
				}
			}
			//二次探測
			else
			{
				i++;
				hashAddr = hashAddr + 2 * i + 1;
				hashAddr %= _vtable.capacity();//保證每次是不同的位置
			}
		}
		return -1;//未找到
	}

//3.删除：
  a.通過哈希函數計算元素在哈希表中的位置
  b.判斷目前位置是否=被删除元素
	   是---删除
	   不是---繼續向後探測
//删除
	bool Erase(const T& data)
	{
		size_t pos = HashFunc(data);
		if (pos != -1)
		{
			_vtable[pos]._state = DELETE;
			_size--;
			return true;
		}
		return false;
	}

鍊位址法

//1.插入：
  (1)通過哈希函數計算目前桶号
  (2)檢測值為data的元素是否存在
    a.如果有，傳回
    b.如果沒有，插入新節點,頭插
bool Insert(const T& data)
	{
		//1.計算桶号
		size_t bucketNum = HashFunc(data);
		//2.檢測目前元素是否存在
		Node* pcur = _vtable[bucketNum];
		while (pcur)
		{
			if (pcur->_data == data)
			{
				return false;
			}
			pcur = pcur->_pNext;
		}
		//3.說明已有空位置，插入元素--頭插
		pcur = new Node(data);
		pcur->_pNext = _vtable[bucketNum];
		_vtable[bucketNum] = pcur;
		_size++;
		return true;
	}
//2.删除（删除值為data的第一個元素）
(1)通過哈希函數計算目前桶号
(2)在桶号所在連結清單中尋找值為data的節點
    a.如果找到，删除
	b.找不到，繼續往後找，直到末尾
bool Erase(const T& data)
	{
		//1.計算桶号
		size_t bucketNum = HashFunc(data);
		//2.尋找節點
		Node* pcur = _vtable[bucketNum];
		Node* pre = nullptr;
		while (pcur)
		{
			if (pcur->_data == data)
			{
				//删除節點
				//if (pre == nullptr)//删除的是第一個節點
				if (_vtable[bucketNum] == pcur)//删除的是第一個節點

				{
					_vtable[bucketNum] = pcur->_pNext;
				}
				else
				{
					//删除非第一個節點
					pre->_pNext = pcur->_pNext;
				}
				delete pcur;
				_size--;
				return true;
			}
			else
			{
				pre = pcur;
				pcur = pcur->_pNext;
			}
		}
		return false;
	}
//3.查找
(1)通過哈希函數計算目前桶号
(2)在桶号所在連結清單中尋找值為data的節點
    a.如果找到，傳回
	b.找不到，繼續往後找，直到末尾
Node* Find(const T& data)const
	{
		//1.計算桶号
		size_t bucketNum = HashFunc(data);
		//2.尋找節點
		Node* pcur = _vtable[bucketNum];
		while (pcur)
		{
			if (pcur->_data == data)
			{
				return pcur;
			}
			else
			{
				pcur = pcur->_pNext;
			}
		}
		return nullptr;
	}

代碼還存在一些需要完善的地方

1.當哈希表的負載因子(哈希表元素個數/表容量)過大時，哈希表需要擴容，怎麼擴容？

2.當哈希表中元素的data部分是非整型時，就無法進行哈希函數計算，需要封裝一個轉換方法，使得哈希函數可以适用于不同的資料類型。

3.為了簡單，我設計的哈希函數時，除留餘數法的除數直接寫了10，但其實這個除數應該是一個素數，并且需要比目前表容量大，那麼怎麼來擷取這個素數？

4.由于STL中的unordered系列關聯式容器底層是通過鍊式定制法的哈希表來實作的，是以需要對該哈希表進行增加一些疊代器的封裝等，适用于實作一些與hash相關的容器。

那麼關于這些問題的解決，詳情可以參考我的後期代碼解決：https://github.com/Zhaotiedan/Code-Practice/tree/master/C%2B%2B/13-unordered%E7%B3%BB%E5%88%97%E5%85%B3%E8%81%94%E5%BC%8F%E5%AE%B9%E5%99%A8/%E5%93%88%E5%B8%8C

C++ 哈希表構造及解決哈希沖突的代碼實作

本文目錄

一.哈希的引入及概念

二.哈希表的構造

三.哈希沖突的産生

四.解決哈希沖突的方法及代碼實作

繼續閱讀

c++ 比對相鄰元素相等的元素（adjacent_find）

DateTimePicker 控件的格式設定

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++數組引用C++數組引用

C++實作簡單順序表

[C++學習曆程]基礎部分 C++中的函數學習

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

使用遞減運算符在循環中按遞減順序列印10到0之間的整數

指針，常量和類型别名

VS C++常見問題集錦1.在Vs中編C出現這兩個錯誤是什麼原因？錯誤1：error LNK2005: _main 已經在 *** 中定義

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述