#pragma once #include#include template struct HashTableNode { K _key; V _value; HashTableNode * _next; HashTableNode(const K& key, const V& value) :_key(key) ,_value(value) ,_next(NULL) {} }; template struct __HashFunc { size_t operator()(const K& key) { return key; } }; template<> struct __HashFunc { static size_t BKDRHash(const char * str) { unsigned int seed = 131; // 31 131 1313 13131 131313 unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); } size_t operator() (const string& key) { return BKDRHash(key.c_str()); } }; template > class HashTable { typedef HashTableNode Node; public: HashTable(size_t capacity) :_size(0) { _tables.resize(_GetNextPrime(capacity)); } HashTable(const HashTable & ht); HashTable & operator=(const HashTable & ht); ~HashTable() { for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* del = cur; cur = cur->_next; delete del; } } } bool Insert(const K& key, const V& value) { _CheckCapacity(); size_t index = _HashFunc(key, _tables.size()); Node* cur = _tables[index]; while (cur) { if (cur->_key == key) return false; cur = cur->_next; } Node* tmp = new Node(key, value); tmp->_next = _tables[index]; _tables[index] = tmp; ++_size; return true; } Node* Find(const K& key) { size_t index = _HashFunc(key, _tables.size()); Node* cur = _tables[index]; while (cur) { if (cur->_key == key) return cur; cur = cur->_next; } return NULL; } bool Remove(const K& key) { size_t index = _HashFunc(key, _tables.size()); if (_tables[index] == NULL) return false; if (_tables[index]->_key == key) { Node* del = _tables[index]; _tables[index] = _tables[index]->_next; delete del; return true; } Node* prev = _tables[index]; Node* cur = prev->_next; while (cur) { if (cur->_key == key) { prev->_next = cur->_next; delete cur; return true; } prev = cur; cur = cur->_next; } return false; } void Print() { for (size_t i = 0; i < _tables.size(); ++i) { printf("[%d]->", i); Node* cur = _tables[i]; while (cur) { cout< _key<<":"< _value<<"->"; cur = cur->_next; } cout<<"NULL"< & ht) { swap(_tables, ht._tables); swap(_size, ht._size); } protected: void _CheckCapacity() { if (_size == _tables.size()) { size_t newCapacity = _GetNextPrime(_tables.size()); if (newCapacity == _tables.size()) return; /* vector newTables; newTables.resize(newCapacity); for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* tmp = cur; cur = cur->_next; size_t index = _HashFunc(tmp->_key, newCapacity);//??? tmp->_next = newTables[index]; newTables[index] = tmp; } _tables[i] = NULL; } _tables.swap(newTables); */ HashTable tmp(_tables.size()); for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { tmp.Insert(cur->_key, cur->_value); cur = cur->_next; } } this->Swap(tmp); } } // 使用素数表对齐做哈希表的容量,降低哈希冲突 size_t _GetNextPrime(size_t size) { 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]; } size_t _HashFunc(const K& key, const size_t capacity) { return HashFunc()(key) % capacity; } protected: vector _tables; size_t _size; }; void TestDic() { HashTable dict(10); dict.Insert("he", "他"); dict.Insert("she", "她"); dict.Insert("hash", "哈希"); dict.Insert("hello", "你好"); dict.Print(); HashTableNode * ret = dict.Find("hash"); if (ret) { cout< _value< > ht(10); vector vec; vec.push_back("男"); vec.push_back("20"); vec.push_back("123456"); ht.Insert("张三", vec); HashTableNode >* ret = ht.Find("张三"); if (ret) { cout<<"姓名:"< _key< _value[0]< _value[1]< _value[2]< 让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:申请域名、虚拟空间、营销软件、网站建设、兴县网站维护、网站推广。
#includeusing namespace std; #include "HashTablesBucket.h" int main() { //TestDic(); Test(); return 0; } TestDic:
Test:
当前文章:C++实现哈希桶
标题来源:http://bjjierui.cn/article/jppeis.html