文章目录

1. 哈希表的改造2. unordered_map3. unordered_set

C++ STL 库中，unordered_map 和 unordered_set 容器的底层为哈希表，本文将简单模拟哈希表（哈希桶），unordered_map 和 unordered_set 只需封装哈希表的接口即可实现。

1. 哈希表的改造

模板参数列表的改造

K：关键码类型T：不同容器 T 的类型不同，如果是 unordered_map，T 代表一个键值对，如果是 unordered_set，T 为 KKeyOfT：从 T 中获取 KeyHash：哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将 Key 转换为整型数字才能取模

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

class HashTable;

增加迭代器操作

// 为了实现简单，在哈希桶的迭代器类中需要用到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;

}

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;

}

};

增加通过 T 获取 key 操作

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

class HashTable

{

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

friend struct __HTIterator;

typedef HashNode<T> Node;

public:

typedef __HTIterator<K, T, KeyOfT, Hash> iterator;

iterator begin()

{

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

{

// 找到第一个桶的第一个节点

if (_tables[i])

{

return iterator(_tables[i], this);

}

}

return end();

}

iterator end()

{

return iterator(nullptr, this);

}

HashTable()

{

_tables.resize(10, 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 T& data)

{

KeyOfT kot;

if (Find(kot(data)))

return false;

Hash hs;

// 负载因子到1就扩容

if (_n == _tables.size())

{

vector<Node*> newTables(_tables.size() * 2, nullptr);

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

{

// 取出旧表中节点，重新计算挂到新表桶中

Node* cur = _tables[i];

while (cur)

{

Node* next = cur->_next;

// 头插到新表

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

cur->_next = newTables[hashi];

newTables[hashi] = 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 true;

}

Node* Find(const K& key)

{

KeyOfT kot;

Hash hs;

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

Node* cur = _tables[hashi];

while (cur)

{

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

{

return cur;

}

cur = cur->_next;

}

return nullptr;

}

bool Erase(const K& key)

{

KeyOfT kot;

Hash hs;

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

Node* prev = nullptr;

Node* cur = _tables[hashi];

while (cur)

{

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

{

// 删除

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;

};

2. unordered_map

unordered_map 中存储的是 pair<K, V> 的键值对，K 为 key 的类型，V 为 value 的类型，Hash 为哈希函数类型unordered_map 在实现时，只需将 HashTable 中的接口重新封装即可

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

class unordered_map

{

// 通过T获取key的操作

struct MapKeyOfT

{

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

{

return kv.first;

}

};

public:

typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;

iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}

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

{

return _ht.Insert(kv);

}

private:

hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;

};

3. unordered_set

unordered_set 的实现类似于 unordered_map

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

class unordered_set

{

struct SetKeyOfT

{

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

{

return key;

}

};

public:

typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;

iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}

bool insert(const K& key)

{

return _ht.Insert(key);

}

private:

hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;

};