目录

前言一，哈希表的改造1. 哈希表的基本框架2. 对哈希桶节点结构的改造3. 哈希表的迭代器3.1 迭代器类3.2 Begin() 和 End()

四，哈希表相关接口的改造4.1 Find 函数的改造4.2 Insert 函数的改造

五，哈希表改造的完整代码六，unordered_set 的封装实现七，unordered_map 的封装实现

点击跳转至文章：

【C++/STL】：哈希 – 线性探测&哈希桶

前言

与map/set的封装类似，unordered系列的底层本质上也是复用，通过对哈希表的改造，再分别套上一层 unordered_map 和 unordered_set 的 “壳子”，以达到 “一表二用” 的目的。

各个结构的改造不再详细说明，细节可参考文章：map和set的封装

unordered系列的底层哈希表是用哈希桶结构实现的。

一，哈希表的改造

1. 哈希表的基本框架

(1) K：关键码类型；

(2) V:：不同容器V的类型不同，如果unordered_map，V代表一个键值对，如果是unordered_set，V 为 K；

(3) KeyOfValue：因为V的类型不同，通过value取key的方式就不同，详细见unordered_map/set的实现；

(4) Hash：哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模。

<code>template <class K, class T, class KeyOfT,class Hash = HashFunc<K>>

class HashBucket

{ -- -->

//友元

template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >

friend struct HTIterator;

typedef BucketNode<T> Node;

public:

typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;

typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;

//其他核心操作……

private:

vector<Node*> _tables; //指针数组

size_t _n = 0; //表中数据的个数

};

}

2. 对哈希桶节点结构的改造

template <class T>

struct BucketNode

{

BucketNode<T>* _next;

T _data;

BucketNode(const T& data)

:_data(data)

, _next(nullptr)

{ }

};

3. 哈希表的迭代器

3.1 迭代器类

(1) 这里的迭代器需要：构造节点指针和哈希表对象指针。

(2) 这里的迭代器类需要用到哈希表类的结构，相互依存，要用前置声明。

//前置声明

template <class K, class T, class KeyOfT, class Hash >

class HashBucket;

template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >

struct HTIterator

{

//需要节点指针，哈希表对象指针

typedef BucketNode<T> Node;

typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

const HashBucket<K, T, KeyOfT, Hash>* _pht;

Node* _node;

HTIterator(Node* node, const HashBucket<K, T, KeyOfT, Hash>* pht)

:_node(node)

,_pht(pht)

{ }

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const Self& s)

{

return _node != s._node;

}

Self& operator++()

{

if (_node->_next)

{

_node = _node->_next;

}

else

{

KeyOfT kot;

Hash hs;

size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();

hashi++;

while (hashi < _pht->_tables.size())

{

if (_pht->_tables[hashi])

break;

hashi++;

}

if (hashi == _pht->_tables.size()) //走完了

_node = nullptr; //End()

else

_node = _pht->_tables[hashi];

}

return *this;

}

};

3.2 Begin() 和 End()

Iterator Begin()

{

if (_n == 0)

return End();

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

if (cur)

return Iterator(cur, this);

}

return End();

}

Iterator End()

{

return Iterator(nullptr, this);

}

ConstIterator Begin()const

{

if (_n == 0)

return End();

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

if (cur)

return ConstIterator(cur, this);

}

return End();

}

ConstIterator End()const

{

return ConstIterator(nullptr, this);

}

四，哈希表相关接口的改造

4.1 Find 函数的改造

Iterator Find(const K& key)

{

Hash hs;

KeyOfT kot;

size_t hashi = hs(key) % _tables.size();

Node* cur = _tables[hashi];

while (cur)

{

if (kot(cur->_data) == key)

return Iterator(cur, this);

else

cur = cur->_next;

}

return End();

}

4.2 Insert 函数的改造

pair<Iterator, bool> Insert(const T& data)

{

Hash hs;

KeyOfT kot;

Iterator it = Find(kot(data));

if (it != End())

return make_pair(it, false);

//扩容

if (_n == _tables.size())

{

vector<Node*> newTables;

newTables.resize(_tables.size() * 2, nullptr);

//把旧表的节点挪到新表

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

while (cur)

{

size_t hashi = hs(kot(cur->_data)) % newTables.size();

Node* newnode = new Node(cur->_data);

//头插

newnode->_next = newTables[hashi];

newTables[hashi] = newnode;

cur = cur->_next;

}

_tables[i] = nullptr;

}

_tables.swap(newTables);

}

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);

}

五，哈希表改造的完整代码

HashTable.h

template<class K>

struct HashFunc

{

size_t operator()(const K& key)

{

return (size_t)key;

}

};

//对string类型的特化

template<>

struct HashFunc<string>

{

size_t operator()(const string& s)

{

size_t n = 0;

for (auto ch : s)

{

n += ch;

n *= 31;

}

return n;

}

};

template <class T>

struct BucketNode

{

BucketNode<T>* _next;

T _data;

BucketNode(const T& data)

:_data(data)

, _next(nullptr)

{ }

};

//前置声明

template <class K, class T, class KeyOfT, class Hash >

class HashBucket;

template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >

struct HTIterator

{

//需要节点指针，哈希表对象指针

typedef BucketNode<T> Node;

//typedef HTIterator<K, T, KeyOfT, Hash> Self;

typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

const HashBucket<K, T, KeyOfT, Hash>* _pht;

Node* _node;

HTIterator(Node* node, const HashBucket<K, T, KeyOfT, Hash>* pht)

:_node(node)

,_pht(pht)

{ }

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const Self& s)

{

return _node != s._node;

}

Self& operator++()

{

if (_node->_next)

{

_node = _node->_next;

}

else

{

KeyOfT kot;

Hash hs;

size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();

hashi++;

while (hashi < _pht->_tables.size())

{

if (_pht->_tables[hashi])

break;

hashi++;

}

if (hashi == _pht->_tables.size()) //走完了

_node = nullptr; //End()

else

_node = _pht->_tables[hashi];

}

return *this;

}

};

template <class K, class T, class KeyOfT,class Hash = HashFunc<K>>

class HashBucket

{

//友元

template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >

friend struct HTIterator;

typedef BucketNode<T> Node;

public:

typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;

typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;

Iterator Begin()

{

if (_n == 0)

return End();

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

if (cur)

return Iterator(cur, this);

}

return End();

}

Iterator End()

{

return Iterator(nullptr, this);

}

ConstIterator Begin()const

{

if (_n == 0)

return End();

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

if (cur)

return ConstIterator(cur, this);

}

return End();

}

ConstIterator End()const

{

return ConstIterator(nullptr, this);

}

HashBucket()

{

_tables.resize(10, nullptr);

}

//依次把每个桶释放

~HashBucket()

{

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;

}

}

pair<Iterator, bool> Insert(const T& data)

{

Hash hs;

KeyOfT kot;

Iterator it = Find(kot(data));

if (it != End())

return make_pair(it, false);

//扩容

if (_n == _tables.size())

{

vector<Node*> newTables;

newTables.resize(_tables.size() * 2, nullptr);

//把旧表的节点挪到新表

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

while (cur)

{

size_t hashi = hs(kot(cur->_data)) % newTables.size();

Node* newnode = new Node(cur->_data);

//头插

newnode->_next = newTables[hashi];

newTables[hashi] = newnode;

cur = cur->_next;

}

_tables[i] = nullptr;

}

_tables.swap(newTables);

}

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 K& key)

{

Hash hs;

KeyOfT kot;

size_t hashi = hs(key) % _tables.size();

Node* cur = _tables[hashi];

while (cur)

{

if (kot(cur->_data) == key)

return Iterator(cur, this);

else

cur = cur->_next;

}

return End();

}

bool Erase(const T& data)

{

Hash hs;

KeyOfT kot;

size_t hashi = hs(kot(data)) % _tables.size();

Node* cur = _tables[hashi];

Node* prev = nullptr;

while (cur)

{

if (cur->_data == data)

{

//第一个节点

if (prev == nullptr)

{

_tables[hashi] = nullptr;

}

else

{

//在节点中间

prev->_next = cur->_next;

}

delete cur;

_n--;

return true;

}

prev = cur;

cur = cur->_next;

}

return false;

}

private:

vector<Node*> _tables; //指针数组

size_t _n = 0; //表中数据的个数

};

六，unordered_set 的封装实现

unordered_set 的底层为哈希表，因此只需在unordered_set 内部封装哈希表，即可将该容器实现出来。

unordered_set .h

#include "HashTable.h"

namespace bit

{

template <class K, class Hash = HashFunc<K>>

class unordered_set

{

struct SetOfT

{

const K& operator()(const K& key)

{

return key;

}

};

public:

typedef typename HashBucket<K, const K, SetOfT, Hash>::Iterator iterator;

typedef typename HashBucket<K, const K, SetOfT, Hash>::ConstIterator const_iterator;

iterator begin()

{

return ht.Begin();

}

iterator end()

{

return ht.End();

}

const_iterator begin()const

{

return ht.Begin();

}

const_iterator end()const

{

return ht.End();

}

pair<iterator, bool> insert(const K& key)

{

return ht.Insert(key);

}

private:

bit::HashBucket<K,const K, SetOfT, Hash> ht;

};

void Print(const unordered_set<int>& s)

{

unordered_set<int>::const_iterator it = s.begin();

while (it != s.end())

{

// *it += 1;

cout << *it << " ";

++it;

}

cout << endl;

}

void Test_set()

{

//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

int a[] = { 16,3,7,11,9,26,18,14,15 };

unordered_set<int> s;

for (auto e : a)

s.insert(e);

for (auto e : s)

cout << e << " ";

cout << endl;

Print(s);

}

}

七，unordered_map 的封装实现

unordered_map 的底层结构就是哈希表，因此在map中直接封装一个哈希表，然后将其接口包装下即可。

unordered_map.h

#include "HashTable.h"

namespace bit

{

template <class K, class V, class Hash = HashFunc<K>>

class unordered_map

{

struct MapOfT

{

const K& operator()(const pair<K, V>& kv)

{

return kv.first;

}

};

public:

typedef typename HashBucket<K, pair<const K, V>, MapOfT, Hash>::Iterator iterator;

typedef typename HashBucket<K, pair<const K, V>, MapOfT, Hash>::ConstIterator const_iterator;

iterator begin()

{

return ht.Begin();

}

iterator end()

{

return ht.End();

}

const_iterator begin()const

{

return ht.Begin();

}

const_iterator end()const

{

return ht.End();

}

pair<iterator, bool> insert(const pair<K,V>& kv)

{

return ht.Insert(kv);

}

V& operator[](const K& key)

{

pair<iterator, bool> ret = ht.Insert(make_pair(key, V()));

return ret.first->second;

}

private:

bit::HashBucket<K, pair<const K, V>, MapOfT, Hash> ht;

};

void Test_map()

{

unordered_map<string, string> dict;

dict.insert({ "left","左边" });

dict.insert({ "right","右边" });

dict.insert({ "insert","插入" });

dict["left"] = "剩余，左边";

bit::unordered_map<string, string>::iterator it = dict.begin();

while (it != dict.end())

{

//it->first += 'x'; //err

it->second += 'y'; //ok

cout << it->first << ":" << it->second << endl;

++it;

}

cout << endl;

}

}