在上篇博客中，已经提出了两种解决哈希冲突的办法：线性探测，二次探测。
创新互联主要从事网站建设、网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务平远,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务: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();
}
当前文章：解决哈希冲突---开链法
文章URL：
http://bjjierui.cn/article/pppdic.html
