在上篇博客中，已經(jīng)提出了兩種解決哈希沖突的辦法：線性探測(cè)，二次探測(cè)。

創(chuàng)新互聯(lián)主要從事網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)平遠(yuǎn),十載網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):13518219792

下面呢，在介紹一種解決沖突的辦法---開鏈法（哈希桶）

哈希桶的實(shí)現(xiàn)：主要是將哈希沖突的那些值存到鏈表中。

代碼實(shí)現(xiàn)：（支持字典查詢）

#pragma once
#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

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

template <>
struct __HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for(size_t i=0;i<key.size();++i)
		{
			hash += key[i];
		}
		return hash;
	}
};


template <class T,class V,class HashFunc = __HashFunc<T>>
class HashTableBucket   //哈希桶
{
	typedef HashTableNode<T,V> Node;
	typedef HashTableBucket<T,V,HashFunc> Table;
public:
	//構(gòu)造
	HashTableBucket()
		:_table(NULL)
		,_size(0)
	{}
	HashTableBucket(size_t capacity)
		:_size(0)
	{
		_table.resize(_CheckCapacity(capacity));
	}
	//析構(gòu)
	~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<ht._table.size();++i)
		{
			Node* cur = ht._table[i];
			while(cur)
			{
				Insert(cur->_key,cur->_value);
				cur = cur->_next;
			}
		}
	}
	//賦值
	/*HashTableBucket<T,V>& operator=(HashTableBucket<T,V> 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<<"["<<cur->_key<<","<<cur->_value<<"]"<<"->";
				cur = cur->_next;
			}
			cout<<"NULL"<<endl;
		}	
	}
protected:
	size_t _HashFunc(const T& key,size_t capacity) //哈希函數(shù)
	{
		//return key%capacity;
		HashFunc hash;
		return hash(key)%capacity;
	}
	size_t _GetNextPrime(const size_t size)  //獲取下一個(gè)素?cái)?shù)
	{
		// 使用素?cái)?shù)表對(duì)齊做哈希表的容量，降低哈希沖突
		const int _PrimeSize = 28;
		static const unsigned long _PrimeList [_PrimeSize] =
		{
			53ul,         97ul,         193ul,       389ul,       769ul,

			1543ul,       3079ul,       6151ul,      12289ul,     24593ul,

			49157ul,      98317ul,      196613ul,    393241ul,    786433ul,

			1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,

			50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,

			1610612741ul, 3221225473ul, 4294967291ul
		};
		for(size_t i=0;i<_PrimeSize;++i)
		{
			if(_PrimeList[i] > size)
			{
				return _PrimeList[i];
			}
		}
		return _PrimeList[_PrimeSize-1];
	}

	void _CheckCapacity()
	{
		if(_size == _table.size())
		{
			size_t nextPrime = _GetNextPrime(_size);
			vector<Node*> newtable;
			newtable.resize(nextPrime);
			for(size_t i=0;i<_table.size();++i)
			{
				Node* cur = _table[i];
				while(cur)
				{
					//摘節(jié)點(diǎn)
					Node* tmp = cur;
					cur = cur->_next;

					//計(jì)算在新表中的位置，頭插
					size_t index = _HashFunc(tmp->_key,nextPrime);
					newtable[index] = tmp;
				}
				_table[i] = NULL;
			}
			_table.swap(newtable); //size，capacity，內(nèi)容
		}
	}
private:
	vector<Node*> _table;  //哈希表
	size_t _size;          //數(shù)據(jù)的個(gè)數(shù)
};

測(cè)試代碼：

#include "HashTableBucket.h"


void HashTableListTest()
{
	HashTableBucket<int,int> 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<int,int>* ret = ht.Find(1);
	if(ret)
	{
		cout<<"["<<ret->_key<<","<<ret->_value<<"]"<<endl;
	}*/
	//ht.Remove(54);
	ht.Remove(1);
	//ht.Print();
}

void HashTableTest()
{
	HashTableBucket<int,int> 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<int,int> ht1(ht);
	//ht1.Print();

	HashTableBucket<int,int> ht2;
	ht2 = ht1;
	ht2.Print();

}


void DircFindTest()
{
	HashTableBucket<string,string> 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();
}

網(wǎng)站標(biāo)題：解決哈希沖突---開鏈法
網(wǎng)站網(wǎng)址：http://jinyejixie.com/article2/pppdic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、網(wǎng)站設(shè)計(jì)、網(wǎng)站排名、靜態(tài)網(wǎng)站、電子商務(wù)、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)