哈希表（开链法）

时间：2016-04-19 19:09:44 阅读：180 评论：0 收藏：0 [点我收藏+]

#include #include #include using namespace std; template struct Node { K _key; V _value; Node*_next; Node(const K& key, const V& value) :_key(key) , _value(value) , _next(NULL) {} }; template struct Hasher { size_t operator() (const T& key) { return key; } }; template<> struct Hasher { size_t operator() (const string& s) { const char* str = s.c_str(); unsigned int seed = 131; unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); } }; 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 }; template> class HashTable { public: HashTable(size_t capacity) { _size = 0; _table.reserve(capacity); _table.assign(capacity, NULL); } void Insert(const K& key, const V& value) { _CheckCapacity(); int pos = _HashFunc(key, _table.size()); Node*begin = _table[pos]; while (begin != NULL) { if (begin->_key == key) { return; } begin = begin->_next; } Node*tmp = new Node(key, value); tmp->_next = _table[pos]; _table[pos] = tmp; ++_size; } void Delete(const int&key) { size_t pos = (size_t)key % (size_t)_table.capacity(); Node*begin = _table[pos]; Node*prev = NULL; while (begin) { if (begin->_key == key) { if (begin == _table[pos]) { _table[pos] = _table[pos]->_next; } else { prev->_next = begin->_next; } delete begin; return; } prev = begin; begin = begin->_next; } } Node* Find(const K&key) { int pos = _HashFunc(key, _table.size()); Node*begin = _table[pos]; while (begin) { if (begin->_key == key) { return begin; } begin = begin->_next; } return NULL; } void Print() { for (int i = 0; i <(int)_table.capacity(); i++) { Node*begin = _table[i]; while (begin != NULL) { printf("pos[%d]:", i); cout << "(" << begin->_key << "," << begin->_value << ")"; cout << "->"; begin = begin->_next; } cout << "NULL" << endl; } } protected: void _CheckCapacity() { if (_size >= (size_t)_table.capacity()) { int NewCapacity = CapacityNum(_size); vector *>tmp; tmp.reserve(NewCapacity); tmp.assign(NewCapacity, NULL); for (size_t i = 0; i < (size_t)_table.capacity(); i++) { while (_table[i] != NULL) { Node* head = _table[i]; _table[i] = _table[i]->_next; int pos = _HashFunc((head->_key), NewCapacity); head->_next = tmp[pos]; tmp[pos] = head; } } _table.swap(tmp); } } size_t CapacityNum(size_t num) { for (int i = 0; i < _PrimeSize; i++) { if (_PrimeList[i]>num) { return _PrimeList[i]; } } return _PrimeList[_PrimeSize - 1]; } int _HashFunc(const K& key, size_t capacity) { HashFunc hashFunc; return hashFunc(key) % _table.capacity(); } private: vector*>_table; size_t _size; }; int main() { HashTable ht1(5); ht1.Insert(27,3); ht1.Insert(57,9); ht1.Insert(83,18); ht1.Insert(120,43); ht1.Insert(227,83); ht1.Print(); cout << endl; ht1.Delete(27); ht1.Delete(227); ht1.Print(); cout << ht1.Find(130) << endl; system("pause"); return 0; }

哈希表（开链法）

原文：http://www.cnblogs.com/yuanshuang/p/5409248.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)