您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
#pragma once #include <vector> #include <string> template<class K, class V> struct HashTableNode { K _key; V _value; HashTableNode<K, V>* _next; HashTableNode(const K& key, const V& value) :_key(key) ,_value(value) ,_next(NULL) {} }; template<class K> struct __HashFunc { size_t operator()(const K& key) { return key; } }; template<> struct __HashFunc<string> { 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 K, class V, class HashFunc = __HashFunc<K>> class HashTable { typedef HashTableNode<K, V> Node; public: HashTable(size_t capacity) :_size(0) { _tables.resize(_GetNextPrime(capacity)); } HashTable(const HashTable<K, V>& ht); HashTable<K, V>& operator=(const HashTable<K, V>& 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<<cur->_key<<":"<<cur->_value<<"->"; cur = cur->_next; } cout<<"NULL"<<endl; } cout<<endl; } void Swap(HashTable<K, V>& 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<Node*> 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<K, V> 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<Node*> _tables; size_t _size; }; void TestDic() { HashTable<string, string> dict(10); dict.Insert("he", "他"); dict.Insert("she", "她"); dict.Insert("hash", "哈希"); dict.Insert("hello", "你好"); dict.Print(); HashTableNode<string, string>* ret = dict.Find("hash"); if (ret) { cout<<ret->_value<<endl; } } void Test() { HashTable<string, vector<string>> ht(10); vector<string> vec; vec.push_back("男"); vec.push_back("20"); vec.push_back("123456"); ht.Insert("张三", vec); HashTableNode<string, vector<string>>* ret = ht.Find("张三"); if (ret) { cout<<"姓名:"<<ret->_key<<endl; cout<<"性别:"<<ret->_value[0]<<endl; cout<<"年龄:"<<ret->_value[1]<<endl; cout<<"电话号码:"<<ret->_value[2]<<endl; } }
#include <iostream> using namespace std; #include "HashTablesBucket.h" int main() { //TestDic(); Test(); return 0; }
TestDic:
Test:
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。