代码如下:
#include <iostream>
#include <vector>
using namespace std;
template<typename K,typename V,typename KeyOfValue>
class HashTable;//声明
template<typename V>
struct HashNode
{
typedef HashNode<V> Node;
V _val;
Node * _next;
HashNode(const V & val):_val(val),_next(nullptr){}
};
template<typename K,typename V,typename KeyOfValue>
struct HashIterator
{
typedef HashNode<V> Node;
typedef HashIterator<K, V, KeyOfValue> Self;
typedef HashTable<K, V, KeyOfValue>HT;
Node *_node;
HT * _hPtr;
HashIterator(Node *node,HT *hPtr):_node(node),_hPtr(hPtr){}
V &operator*()
{
return _node->_val;
}
V *operator->()
{
return &_node->_val;
}
bool operator!=(const Self & it)
{
return _node != it._node;
}
Self & operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
KeyOfValue kov;
size_t idx = kov(_node->_val) % _hPtr->_ht.size();
++idx;
for (; idx < _hPtr->_ht.size(); idx++)
{
if (_hPtr->_ht[idx])
{
_node = _hPtr->_ht[idx];
break;
}
}
if (idx == _hPtr->_ht.size()) _node = nullptr;
}
return *this;
}
};
template<typename K,typename V,typename KeyOfValue>
class HashTable
{
public:
typedef HashIterator<K, V, KeyOfValue> iterator;
typedef HashNode<V> Node;
template<typename K,typename V,typename KeyOfValue>
friend struct HashIterator;
HashTable(int n = 10):_ht(n),_size(0){}
iterator begin()
{
for (size_t i = 0; i < _ht.size(); i++)
{
if (_ht[i])
{
return iterator(_ht[i], this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
pair<iterator, bool> insert(const V & val)
{
//0.检查容量
checkCapacity();
KeyOfValue kov;
//1.计算hash位置
int idx = kov(val) % _ht.size();
//2.查找
Node *cur = _ht[idx];
while (cur)
{
if (kov(cur->_val) == kov(val)) return make_pair(iterator(cur, this), false);
cur = cur->_next;
}
//3.插入--头插
cur = new Node(val);
cur->_next = _ht[idx];
_ht[idx] = cur;
++_size;
return make_pair(iterator(cur, this), true);
}
void checkCapacity()
{
if (_size == _ht.size())
{
int newC = _size == 0 ? 10 : 2 * _size;
vector<Node *>newHt(newC);
KeyOfValue kov;
for (size_t i = 0; i < _ht.size(); i++)
{
Node *cur = _ht[i];
while (cur)
{
Node *next = cur->_next;
int idx = kov(cur->_val) % newHt.size();
cur->_next = newHt[idx];
newHt[idx] = cur;
cur = next;
}
_ht[i] = nullptr;
}
swap(_ht, newHt);
}
}
private:
vector<Node *> _ht;
int _size;
};
template<typename K>
class UnorderedSet
{
struct SetKeyOfValue
{
const K & operator()(const K & key)
{
return key;
}
};
public:
typedef typename HashTable<K, K, SetKeyOfValue>::iterator iterator;
pair<iterator, bool> insert(const K& key)
{
return _ht.insert(key);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
private:
HashTable<K, K, SetKeyOfValue> _ht;
};
template<typename K,typename V>
class UnorderedMap
{
struct MapKeyOfValue
{
const K& operator()(const pair<K, V> & val)
{
return val.first;
}
};
public:
typedef typename HashTable<K, pair<K, V>, MapKeyOfValue>::iterator iterator;
pair<iterator, bool > insert(const pair<K, V> & val)
{
return _ht.insert(val);
}
iterator begin() {
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
V & operator[](const K& key)
{
pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashTable<K, pair<K, V>, MapKeyOfValue> _ht;
};
int main()
{
UnorderedSet<int>s;
s.insert(1);
s.insert(123);
s.insert(123412);
s.insert(12);
s.insert(1132);
s.insert(1131);
s.insert(436);
s.insert(786);
s.insert(13);
s.insert(7965);
s.insert(7653);
s.insert(645);
s.insert(324);
UnorderedSet<int>::iterator it1 = s.begin();
while (it1 != s.end())
{
cout << *it1 << " ";
++it1;
}
cout << endl;
for (const auto & e : s)
{
cout << e << " ";
}
cout << endl;
UnorderedMap<int, int>m;
m.insert(make_pair(1, 1));
m[2] = 2;
m[3] = 3;
UnorderedMap<int, int>::iterator it2 = m.begin();
while (it2 != m.end())
{
cout << it2->first << "--->" << it2->second << endl;
++it2;
}
cout << "--------------------" << endl;
m[2] = 20;
for (auto & p : m)
{
cout << p.first << "--->" << p.second << endl;
}
return 0;
}
测试结果: