【数据结构】c++实现HashTable(开链法)
程序员文章站
2022-04-02 07:53:13
#include
#include
using namespace std;
template
struct HashTableNode
{
K _key;
V _va...
#include #include using namespace std; template struct HashTableNode { K _key; V _value; HashTableNode* _next; HashTableNode(const K&key, const V&value) :_key(key) , _value(value) , _next(NULL) {} }; template struct DefaultHashFunc { size_t operator()(const K&key) { return key; } }; template > class HashTableBucket { typedef HashTableNode Node; public: HashTableBucket() :_size(0) {} HashTableBucket(size_t size) :_size(0) { _tables.resize(size); } bool Insert(const K&key, const V&value) { _CheckExpand(); size_t index = HashFunc(key, _tables.size()); Node* begin = _tables[index]; while (begin) { if (begin->_key == key) return false; begin = begin->_next; } Node* tmp = new Node(key, value); tmp->_next = _tables[index]; _tables[index] = tmp; ++_size; return true; } size_t HashFunc(const K&key, size_t capacity) { HashFun hf; return hf(key) % capacity; } void PrintTables() { for (size_t i = 0; i ",i); Node* cur = _tables[i]; while (cur) { cout _key _value "; cur = cur->_next; } cout size) { return _PrimeList[i]; } } return _PrimeList[_PrimeSize - 1]; } void _CheckExpand() { // 载荷因子到1时进行增容,保证效率 if (_size == _tables.size()) { size_t newSize = _GetNextPrime(_size); if (_size == newSize) return; vector newTables; newTables.resize(newSize); for (size_t i = 0; i _next; // 头插 size_t newIndex = HashFunc(tmp->_key, newTables.size()); tmp->_next = newTables[newIndex]; newTables[newIndex] = tmp; } _tables[i] = NULL; } _tables.swap(newTables); } } protected: vector*> _tables; size_t _size; };
上一篇: 广州火车站-那些垄断下的恐慌销售(一)
下一篇: 关于稳增长的一些不成熟的建议(二)