【干货】C++哈希桶(开链法解决哈希冲突)类的实现
开链法(哈希桶)是解决哈希冲突的常用手法,结构如下:
创新互联是一家集成都网站建设、做网站、网站页面设计、网站优化SEO优化为一体的专业网站设计公司,已为成都等多地近百家企业提供网站建设服务。追求良好的浏览体验,以探求精品塑造与理念升华,设计最适合用户的网站页面。 合作只是第一步,服务才是根本,我们始终坚持讲诚信,负责任的原则,为您进行细心、贴心、认真的服务,与众多客户在蓬勃发展的市场环境中,互促共生。
数据结构的设计思路是这样的,定义一个K—V的链式节点(Node),以数组方式存储节点指针
实现代码如下:
#include#include"HashTable.h" size_t GetSize() { static size_t index = 0; 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 }; return _PrimeList[index++]; } template struct HashBucketNode { HashBucketNode(const K& key, const V& value) :_key(key) , _value(value) , _next(NULL) {} K _key; V _value; HashBucketNode* _next; }; template > class HashBucket { public: typedef HashBucketNode Node; HashBucket() :_size(0) { _tables.resize(0); } bool Push(const K& key, const V& value) { _CheckCapacity(); size_t index = HashFunc()(key) % _tables.size(); Node*cur = _tables[index]; while (cur) { if (cur->_key == key&&cur->_value == value) return false; cur = cur->_next; } Node*tmp = new Node(key, value); if (_tables[index]) { _tables[index]->_next = tmp->_next; } _tables[index] = tmp; ++_size; return true; } void Swap(HashBucket & h) { swap(_size, h._size); _tables.swap(h._tables); } Node* find(const K& key, const V& value) { size_t index = HashFunc()(key) % _tables.size(); Node*cur = _tables[index]; while (cur) { if (cur->_key == key&&cur->_value == value) return cur; cur = cur->_next; } return NULL; } bool Remove(const K& key) { size_t index = HashFunc()(key) % _tables.size(); if (_tables[index]) { if (_tables[index]->key == key) { Node*tmp = _tables[index]; _tables[index] = tmp->_next; delete tmp; return true; } else { Node*cur = _tables[index]; while (cur->_next) { if (cur->_next->_key == key) { Node*tmp = cur->_next; cur->_next = cur->_next->_next; delete tmp; return true; } cur = cur->_next; } } } return false; } protected: void _CheckCapacity() { if (_size >= _tables.size()) { HashBucket tmp; tmp._tables.resize(GetSize()); for (size_t i = 0; i < tmp._tables.size(); ++i) { Node*cur = tmp._tables[i]; while (cur) { tmp.Push(cur->_key, cur->_value); cur = cur->_next; } } Swap(tmp); } } protected: vector _tables; size_t _size; };
如有不足希望指正,有疑问希望提出
分享标题:【干货】C++哈希桶(开链法解决哈希冲突)类的实现
转载注明:http://scyanting.com/article/jehiep.html