代碼如下:

#include <iostream> #include <vector> using namespace std;enum STATE {EXIST,DELETE,EMPTY };template<typename K,typename V> struct HashNode {pair<K, V> _kv;STATE _state = EMPTY; };template<typename K,typename V> class HashTable { public:typedef HashNode<K, V> Node;HashTable(size_t n = 10):_hTable(n),_size(0){}bool insert(const pair<K, V> & kv){checkCapacity();int idx = kv.first % _hTable.size();while (_hTable[idx]._state != EMPTY){if (_hTable[idx]._state == EXIST && _hTable[idx]._kv.first == kv.first){return false;}++idx;if (idx == _hTable.size()) idx = 0;}_hTable[idx]._kv = kv;_hTable[idx]._state = EXIST;++_size;}void checkCapacity(){if (_hTable.size() == 0 || _size * 10 / _hTable.size() >= 7){int newC = _hTable.size() == 0 ? 10 : 2 * _hTable.size();HashTable<K, V> newHt(newC);for (size_t i = 0; i < _hTable.size(); i++){if (_hTable[i]._state == EXIST){newHt.insert(_hTable[i]._kv);}}Swap(newHt);}}void Swap(HashTable<K, V> & Ht){swap(_hTable, Ht._hTable);swap(_size, Ht._size);}Node * find(const K & key){int idx = key % _hTable.size();while (_hTable[idx]._state != EMPTY){if (_hTable[idx]._state == EXIST && key == _hTable[idx]._kv.first){return &_hTable[idx];}++idx;if (idx == _hTable.size()) idx = 0;}return nullptr;}bool erase(const K & key){Node *node = find(key);if (node){--_size;node->_state = DELETE;return true;}return false;}private:vector<Node> _hTable;size_t _size; };int main() {HashTable<int,int> h;h.insert(make_pair(1, 232));h.insert(make_pair(3, 2432));h.insert(make_pair(11, 56));cout<<h.find(3)->_kv.second<<endl;cout << h.find(11)->_kv.second << endl;return 0; }

測試結果:

總結

以上是生活随笔為你收集整理的C++泛型编程实现哈希表(闭散列---线性探测)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。