解决哈希冲突---开链法

在上篇博客中，已经提出了两种解决哈希冲突的办法：线性探测，二次探测。

创新互联主要从事网站建设、网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务平远,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792

下面呢，在介绍一种解决冲突的办法---开链法（哈希桶）

哈希桶的实现：主要是将哈希冲突的那些值存到链表中。

代码实现：（支持字典查询）

#pragma once
#include 
#include 
#include 

using namespace std;

template 
struct HashTableNode
{
	HashTableNode(const T& key,const V& value)
		:_key(key)
		,_value(value)
		,_next(NULL)
	{}
	T _key;
	V _value;
	HashTableNode* _next;
};

template 
struct __HashFunc
{
	size_t operator()(const T& key)
	{
		return key;
	}
};

template <>
struct __HashFunc
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for(size_t i=0;i>
class HashTableBucket   //哈希桶
{
	typedef HashTableNode Node;
	typedef HashTableBucket Table;
public:
	//构造
	HashTableBucket()
		:_table(NULL)
		,_size(0)
	{}
	HashTableBucket(size_t capacity)
		:_size(0)
	{
		_table.resize(_CheckCapacity(capacity));
	}
	//析构
	~HashTableBucket()
	{
		for(size_t i=0;i<_table.size();++i)
		{
			Node* cur = _table[i];
			while(cur)
			{
				Node* del = cur;
				cur = cur->_next;
				delete del;
			}
			_table[i] = NULL;
		}
	}
	//拷贝
	HashTableBucket(const Table& ht)
		:_size(0)
	{
		_table.resize(ht._table.size()); //开辟空间
		for(size_t i=0;i_key,cur->_value);
				cur = cur->_next;
			}
		}
	}
	//赋值
	/*HashTableBucket& operator=(HashTableBucket ht)
	{
		_table.swap(ht._table);
		swap(_size,ht._size);
		return *this;
	}*/

	Table& operator=(Table& ht)
	{
		if(this != &ht)
		{
			Table tmp(ht);
			_table.swap(tmp._table);
			swap(_size,tmp._size);
		}
		return *this;
	}
public:
	bool Insert(const T& key,const V& value)
	{
		_CheckCapacity();//检查容量
		size_t index = _HashFunc(key,_table.size());
		Node* cur = _table[index];
		while(cur)
		{
			if(cur->_key == key)  //防冗余
			{
				return false;
			}
			cur = cur->_next;
		}
		//头插
		Node* newNode =new Node(key,value);
		newNode->_next = _table[index];
		_table[index] = newNode;
		++_size;
		return true;
	}
	Node* Find(const T& key)
	{
		size_t index = _HashFunc(key,_table.size());
		Node* cur = _table[index];
		while(cur)
		{
			if(cur->_key == key)
			{
				return cur;
			}
			cur = cur->_next;
		}
		return NULL;
	}
	bool Remove(const T& key)
	{
		size_t index = _HashFunc(key,_table.size());
		Node* cur = _table[index];
		Node* prev = NULL;
		Node* del = NULL;
		if(cur->_key == key)
		{
			del = cur;
			_table[index] = cur->_next;
			delete del;
			return true;
		}	
		prev = cur;
		cur = cur->_next;
		while(cur)
		{
			if(cur->_key == key)
			{
				del = cur;
				prev->_next = cur->_next;
				delete del;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}
	void Print()
	{
		for(size_t i=0;i<_table.size();++i)
		{
			printf("_table[%d]:",i);
			Node* cur = _table[i];
			while(cur)
			{
				cout<<"["<_key<<","<_value<<"]"<<"->";
				cur = cur->_next;
			}
			cout<<"NULL"< size)
			{
				return _PrimeList[i];
			}
		}
		return _PrimeList[_PrimeSize-1];
	}

	void _CheckCapacity()
	{
		if(_size == _table.size())
		{
			size_t nextPrime = _GetNextPrime(_size);
			vector newtable;
			newtable.resize(nextPrime);
			for(size_t i=0;i<_table.size();++i)
			{
				Node* cur = _table[i];
				while(cur)
				{
					//摘节点
					Node* tmp = cur;
					cur = cur->_next;

					//计算在新表中的位置，头插
					size_t index = _HashFunc(tmp->_key,nextPrime);
					newtable[index] = tmp;
				}
				_table[i] = NULL;
			}
			_table.swap(newtable); //size，capacity，内容
		}
	}
private:
	vector _table;  //哈希表
	size_t _size;          //数据的个数
};

测试代码：

#include "HashTableBucket.h"


void HashTableListTest()
{
	HashTableBucket ht;
	for(size_t i=0;i<50;++i)
	{
		ht.Insert(i,i);
	}
	ht.Insert(107,32);
	ht.Insert(54,45);
	//ht.Insert(65,32);
	/*HashTableNode* ret = ht.Find(1);
	if(ret)
	{
		cout<<"["<_key<<","<_value<<"]"< ht;
	ht.Insert(1,1);
	ht.Insert(11,11);
	ht.Insert(21,21);
	ht.Insert(12,12);
	ht.Insert(23,23);
	ht.Insert(54,57);
	ht.Insert(42,12);
	//ht.Print();
	HashTableBucket ht1(ht);
	//ht1.Print();

	HashTableBucket ht2;
	ht2 = ht1;
	ht2.Print();

}


void DircFindTest()
{
	HashTableBucket ht;
	/*ht.Insert("zhang","张");
	ht.Insert("xiao","小");
	ht.Insert("yu","雨");*/
	//ht.Insert("angzh","田");

	ht.Insert("字典","dirc");
	ht.Insert("钱","money");
	ht.Insert("吃","eat");
	ht.Insert("玩","happy");
	ht.Print();
}