C++ 哈希表构造及解决哈希冲突的代码实现

一.哈希的引入及概念

引入：当在顺序结构(如数组)或者平衡树(平衡二叉树)中查找一个元素时，必须要经过多次与内部元素进行比较的过程，顺序结构的查找时间复杂度为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，那么现在可以通过哈希函数将元素依次存放进哈希表

如果此时再插入一个元素55，则hash（55）=55%10=5，所以它和元素5的哈希地址相同，这就是哈希冲突。

四.解决哈希冲突的方法及代码实现

1. 设计一个合理的哈希函数，但是还是不能从根本上解决
2. 开放定址法（闭散列）：从发生哈希冲突的位置开始，找下一个空位置，找空位置又分为两种方法：线性探测和非线性探测。

（1）线性探测：从当前位置依次往后找空位置，找到末尾时，地址下标置0， 从头开始查找。
优点：处理哈希冲突方式比较简单
缺点：一旦发生冲突，容易造成数据的堆积
解决：不挨着往后找空位置，避免产生数据堆积。解决方法：非线性探测里的二次探测

（2）非线性探测：二次探测：从当前位置，不采用依次往后查找，而通过公式来寻找下一个空位置。公式获取：H(i+1)=H(i)+2*i+1；i=1,2,3,4…代表查找次数。
找到末尾时，地址下标%表容量，保证每次是不同的位置；不能置0，会引起无休止的探测。
优点：可以解决线性探测中数据堆积的问题
缺点：如果表格中的空位置比较少，容易错过空位置，可能就需要探测多次

3. 链地址法（开散列）：将发生哈希冲突的元素放在同一个链表中

具体实现：采用哈希桶
(1)计算当前元素所在桶号
(2)在桶号对应链表查看看桶号位置是否有元素，无则直接插入，有则往下遍历该桶号对应链表，直到找到空位置
(3)插入元素

具体的相关函数实现代码：

1. 开放定址法

//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;
	}

2. 链地址法

//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