一. 哈希表的改造
咱们这里还是跟Map和Set的封装一样的道理，没有必要为了unordered_map和unordered_set传的参数不同就实例化两份代码，可以直接通过模板参数来解决。那么unordered_map传的是pair<key,value>，unordered_set传的是key。对于哈希表还有不懂的可以去看上一篇博客(http://t.csdnimg.cn/O5Vg5)，对Map和Set封装还有不懂的可以去看博客(http://t.csdnimg.cn/dOSOt)。
所以咱们的代码改造成：
代码语言：javascript复制namespace hash_bucket
{
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_next(nullptr)
, _data(data)
{}
};
template<class K, class T,class KeyOfT,class Hash>
//为了获得传参中的key，用KeyOfT仿函数
//考虑unordered_map和unordered_set里面的元素不只是整型，所以用仿函数Hash对元素进行处理
class HashTable
{
typedef HashNode<T> Node;
public:
int GetNextPrimer(int val)
{
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389,
1543, 3079, 6151, 12289,
49157, 98317, 196613, 393241,
1572869, 3145739, 6291469, 12582917,
50331653, 100663319, 201326611, 402653189,
1610612741, 3221225473, 4294967291
};
for (size_t i = 0; i < __stl_num_primes; i )
{
if (__stl_prime_list[i] > val)
{
return __stl_prime_list[i];
}
}
}
HashTable()
{
_tables.resize(GetNextPrimer(1), nullptr);
_n = 0;
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i )
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
//插入
bool insert(const pair<K, V>& kv) {
if (find(kv.first))
return false;
//调用仿函数的匿名对象来将key转换为整数
size_t hashi = Hash()(kv.first) % _tables.size();
//哈希桶头插
Node* newNode = new Node(kv);
newNode->next = _tables[hashi];
_tables[hashi] = newNode;
_n;
return true;
}
//查找
Node* find(const K& key) {
size_t hashi = Hash()(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->next;
}
return nullptr;
}
//删除
bool erase(const K& key) {
//由于单链表中删除节点需要改变上一个节点的指向，所以这里不能find后直接erase
size_t hashi = Hash()(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
//删除还要分是否为头结点
if (cur->_kv.first == key) {
if (cur == _tables[hashi])
_tables[hashi] = cur->next;
else
prev->next = cur->next;
delete cur;
--_n;
return true;
}
//迭代
prev = cur;
cur = cur->next;
}
return false;
}
private:
vector<Node*> _tables;//指针数组
size_t _n;
};
}到此时我们还没有出现新的东西，一切都是在《Map和Set的封装》和《哈希开散列的实现》两个基础上结合起来的。而对迭代器的封装也是如此。
二. 迭代器的封装
我们还是采用之前的模板参数来实现，需要注意的是，由于迭代器里面要用到自定义类HashTable，而由于HashTable 我把他排版在了迭代器的下面，所以我们要先在迭代器的前面申明这个类存在，因为编译器只会向上兼容，这也是一个可以借鉴的点。而我们自定义类HashTable里面也要用到迭代器，那么反过来迭代器在类的上方，可以向上兼容，所以不用在类的前面申明了。
特别注意的是：
- 如果你把迭代器定义在了类HashTable的下面，就无需在迭代器的上面进行声明，而要在类HashTable的上面声明迭代器的存在。
- 此处迭代器要对类HashTable里面的私有成员进行访问，所以要在类HashTable里面对迭代器设置友元，使迭代器能访问私有成员。
那么类HashTable中设置友元具体是：
代码语言：javascript复制template<class K, class T,class KeyOfT,class Hash>
class HashTable
{
typedef HashNode<T> Node;
//友元让迭代器能访问私有成员
template<class K, class T, class KeyOfT, class Hash>
friend struct __HTIterator;
//...
private:
vector<Node*> _tables;//指针数组
size_t _n;
};此处迭代器里面值得一讲的是 操作(因为哈希表开散列的结构是单链表，所以没有必要实现--操作)，我们得分情况来看，如果这个元素之后在用一个桶中还有元素，那么直接 就行；如果没有，则要依次向后找，找到下一个不为空的桶开始遍历。
//声明有HashTable这个类
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K,class T,class KeyOfT,class Hash>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef __HTIterator<K, T, KeyOfT, Hash> Self;
Node* _node;
HT* _ht;
__HTIterator(Node* node,HT* ht)
:_node(node)
,_ht(ht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator ()
{
if (_node->_next)
{
_node=_node->_next;
}
else
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
//下一个桶
hashi ;
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
hashi;
}
if (hashi == _ht->_tables.size())
{
_node=nullptr;
}
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};三. 哈希表整体代码
那么我们哈希表的整体代码就是：
代码语言：javascript复制namespace hash_bucket
{
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_next(nullptr)
, _data(data)
{}
};
//声明有HashTable这个类
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K,class T,class KeyOfT,class Hash>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef __HTIterator<K, T, KeyOfT, Hash> Self;
Node* _node;
HT* _ht;
__HTIterator(Node* node,HT* ht)
:_node(node)
,_ht(ht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator ()
{
if (_node->_next)
{
_node=_node->_next;
}
else
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
//下一个桶
hashi ;
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
hashi;
}
if (hashi == _ht->_tables.size())
{
_node=nullptr;
}
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class K, class T,class KeyOfT,class Hash>
class HashTable
{
typedef HashNode<T> Node;
//友元让迭代器能访问私有成员
template<class K, class T, class KeyOfT, class Hash>
friend struct __HTIterator;
public:
typedef __HTIterator<K, T, KeyOfT, Hash> iterator;
int GetNextPrimer(int val)
{
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389,
1543, 3079, 6151, 12289,
49157, 98317, 196613, 393241,
1572869, 3145739, 6291469, 12582917,
50331653, 100663319, 201326611, 402653189,
1610612741, 3221225473, 4294967291
};
for (size_t i = 0; i < __stl_num_primes; i )
{
if (__stl_prime_list[i] > val)
{
return __stl_prime_list[i];
}
}
}
HashTable()
{
_tables.resize(GetNextPrimer(1), nullptr);
_n = 0;
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i )
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i )
{
if (_tables[i])
{
//用this将HashTable传过去
return iterator(_tables[i],this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
pair<iterator,bool> Insert(const T& data)
{
KeyOfT kot;
iterator it = Find(data);
if (it!=end())
{
return make_pair(it, false);
}
Hash hs;
//负载因子到1就扩容
if (_n == _tables.size())
{
//法一：采用闭散列的扩容方法--复用insert接口
//优点：实现简单；
//缺点：先开辟节点再释放节点代价大
//HashTable<K, V, Hash> newHT;
//newHT._tables.resize(_tables.size() * 2, nullptr);
//for (size_t i = 0; i < _tables.size(); i) {
// Node* cur = _tables[i];
// while (cur) {
// newHT.insert(cur->_kv);
// cur = cur->next;
// }
//}
//_tables.swap(newHT._tables);
//法二：取原表中的节点链接到当前表中
//缺点：实现比较复杂
//优点：不用再去开辟新节点，也不用释放旧节点，消耗小
//不用跟开放地址法一样重新创一个HashTable对象，因为会造成指针
//节点创建又删除
vector<Node*> newvector(_tables.size()*2,nullptr);
for (size_t i = 0; i < _tables.size(); i )
{
Node* cur1 = _tables[i];
while (cur1)
{
Node* cur2 = cur1->_next;
size_t hashi = hs(kot(cur1->_data)) % newvector.size();
cur1->_next = newvector[i];
newvector[i] = cur1;
cur1 = cur2;
}
//把原来的指针置空
_tables[i] = nullptr;
}
_tables.swap(newvector);
}
size_t hashi = hs(kot(data)) % _tables.size();
//头插不用看该位置是否为空
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
_n ;
return make_pair(iterator(newnode,this), true);
}
iterator Find(const T& data)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(data)) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (hs(kot(cur->_data)) == hs(kot(data)))
{
return iterator(cur,this);
}
cur = cur->_next;
}
return iterator(nullptr,this);
}
bool Erase(const T& data)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(data)) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (cur->_data == kot(data))
{
if (prev)
{
prev->_next = cur->_next;
}
else
{
_tables[hashi] = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;//指针数组
size_t _n;
};
}
注意：由于迭代器的构造要用到HashTable，所以在HashTable类中插入操作的时候，用this返回哈希表。
四. unordered_set和unordered_map具体实现
3.1 unordered_set具体实现
那么到此时，unordered_set的具体实现已经很清楚了。这里我们要知道unordered_set里面的元素key是不能被改变的，所以为其附上const的枷锁。
代码语言：javascript复制//int类型
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
namespace yjy
{
template<class K,class Hash=HashFunc<K>>
class unordered_set
{
struct KeyOfTSet
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K,const K, KeyOfTSet, Hash>::iterator iterator;
iterator begin()
{
return us.begin();
}
iterator end()
{
return us.end();
}
pair<iterator,bool> Insert(const K& key)
{
return us.Insert(key);
}
iterator Find(const K& key)
{
return us.Find(key);
}
bool Erase(const K& key)
{
us.Erase(key);
}
typedef hash_bucket::HashTable<K,const K, KeyOfTSet,Hash> _set;
private:
_set us;
};
}3.2 unordered_map具体实现
同样，unordered_map的具体实现已经很清楚了。这里我们要知道unordered_map的pair<key,value>里的key是不能被改变的，所以也要为其附上const的枷锁。
代码语言：javascript复制//int类型
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
namespace yjy
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct KeyOfTMap
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, KeyOfTMap, Hash>::iterator iterator;
iterator begin()
{
return um.begin();
}
iterator end()
{
return um.end();
}
pair<iterator, bool> Insert(const pair<K, V>& kv)
{
return um.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = Insert(make_pair(key,V()));
return ret.first->second;
}
iterator Find(const K& key)
{
return um.Find(key);
}
bool Erase(const K& key)
{
um.Erase(key);
}
typedef hash_bucket::HashTable<K, pair<const K, V>, KeyOfTMap, Hash> _map;
private:
_map um;
};
}总结
好了，到这里今天的知识就讲完了，大家有错误一点要在评论指出，我怕我一人搁这瞎bb，没人告诉我错误就寄了。
祝大家越来越好，不用关注我（疯狂暗示）
