大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
在上篇博客中,已经提出了两种解决哈希冲突的办法:线性探测,二次探测。
创新互联主要从事网站建设、网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务平远,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务: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() { HashTableBucketht; 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(); }