当前位置：首页 > news >正文

初识C++ · 哈希表封装unordered_map/set

news 来源：原创 2024/9/19 10:58:42

1 正确认识关系

2 哈希表封装

2.1 查找

2.2 插入

2.3 删除

2.4 析构函数

2.5 Begin部分

1 正确认识关系

有了哈希表的基础已经红黑树封装map + set的经验，我们现在就可以较为顺畅的捋清楚每个类之间的关系。

第一个：

节点类-> 节点类的同红黑树一样，在unordered_map一层传一个参数用来确定节点类的数据类型，我们实现的是哈希桶来封装，所以成员变量有顺序表，顺序表里面是节点指针，加上数据变量：

template<class T>
struct HashNode
{HashNode(const T& data):_next(nullptr), _data(data){}HashNode<T>* _next;T _data;
};

第二个：
仿函数部分-> 我们在哈希桶部分就知道了如果是自定义类型的话，那么没有办法取模，就需要转为整型，同理，其他自定义类型的话也需要不同的方式转为整型，这样可以映射到每个桶里面去，那么第一个仿函数就是转为整型的，其中有模板特例化语法的出现，第二个仿函数就是老生常谈的了，是KeyOfT，是在unordered_map这一层调用的，和红黑树封装map + set是一样的：

template<class K>
struct SHAlgorithm
{size_t operator()(const K& key){return size_t(key);}
};template<>
struct SHAlgorithm<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto e : s){hash *= 131;hash += e;}return hash;}
};

struct MapKeyOfT
{const K& operator()(const pair<K, V>& kv){return kv.first;}
};

第三个：
迭代器，迭代器用来实现的功能依旧是解引用 ++ 判断是否相等，那么迭代器的成员变量有哪些呢？因为要实现遍历，节点指针是肯定的吧？但是节点指针只能实现在某个桶里面++，这里顺带提一下，对于unordered_map unordered_set来说，迭代器是单向迭代器，所以我们不用实现--，那么有了节点指针，我们就可以实现某个桶的遍历，整个顺序表的遍历我们应该如何实现呢？

我们遍历链表，需要节点指针，遍历顺序表自然就是需要顺序表指针了，所以迭代器的成员遍历有两个，那么现在问题又来了：

迭代器如果写在哈希桶的外面，成员变量有哈希表的指针，可是编译器是向上查找的，上面没有，那怎么办？如果写在外面，模板参数该有多少个，哈希桶的模板参数有 K V 两个仿函数，加上迭代器的参数，一共六个模板参数，是不是太冗余了？

解决方法是，如果写在外面，需要一个前置声明，告诉编译器我们有哈希表的节点指针，对于模板参数方面，要解决只能写成内部类：

template< class Ref, class Ptr>
struct HTIterator
{typedef HashNode<V> Node;typedef HTIterator Self;HTIterator(Node* node, const HashTable* pht):_node(node), _pht(pht){}Node* _node;const HashTable* _pht;};typedef HTIterator<V&, V*> iterator;
typedef HTIterator<const V&, const V*> const_iterator;

这是内部的写法，那么有问题了就：

1 为什么typdef 迭代器要写在下面？

2 为什么顺序表指针要写成const？

typedef写在下面是因为编译器同样是向上查找的，如果写在上面了，那么就要加声明。

const顺序表指针是因为，当我有一个const哈希表的时候，this指针指向的是const对象，这时候我用非const对象指针来接受，就存在了权限放大的问题，所以不行，即调用的情况有两种，一是const调用，二是非const调用，因为权限问题所以我们就加上了const。

哈希表本体的话，已经介绍过了，这里就不再多说了。

2 哈希表封装

2.1 查找

查找这里是最简单的，无非就是遍历一下即可，遍历的基本思想是先找下标索引的位置，然后链表++即可：

iterator Find(const K& key)
{Hash hs;KeyOfT kot;size_t hashi = hs(key) % _table.size();Node* cur = _table[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur,this);}cur = cur->_next;}return End();
}

返回的值可能让人有点迷糊，为什么用this指针去构造一个迭代器呢？因为迭代器的成员变量有一个顺序表的对象指针，指向的就是我们要遍历的迭代器，所以这里的用法是很绝的，this指针显式的去使用。

2.2 插入

pair<iterator, bool> Insert(const V& data)
{KeyOfT kot;Hash hs;//去重iterator it = Find(kot(data));// -> 注意这里是!=if (it != End()){return make_pair(it, false);}//扩容 -> load_factor达到1时进行扩容if (_n == _table.size()){vector<Node*> newTables(_table.size() * 2, nullptr);for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[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;}_table[i] = nullptr;}_table.swap(newTables);}//插入方式使用头插size_t hashi = hs(kot(data)) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;_n++;return make_pair(iterator(newnode,this),true);
}

这里返回值保持和红黑树那里一样，返回值是pair<K,V>类型的，也就去重，扩容，插入即可，这是链表的插入，也没有什么要特别注意的。

2.3 删除

删除就是跳跃节点连接即可：

bool Erase(const K& key)
{Hash hs;KeyOfT kot;size_t hashi = hs(key) % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (kot(cur->_kv) == key){//头结点if (prev == nullptr){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;delete cur;return true;}}else{prev = cur;cur = cur->_next;}delete cur;return true;}return false;
}

这里的三个函数都是和红黑树那边一样的，那么现在就差迭代器了，迭代器的* -> != 都是和之前的一样的，++的基本思路就是Begin找到第一个不为空的桶，返回第一个节点姐可以，那么++ 就是从该桶遍历，该桶遍历完了就顺序表指针++，直到找到一个新的桶，如果没有找到新的桶，那么将节点指针置为空即可：

template< class Ref, class Ptr>
struct HTIterator
{typedef HashNode<V> Node;typedef HTIterator Self;//typedef HTIterator<Ref, Ptr> Self;HTIterator(Node* node, const HashTable* pht):_node(node), _pht(pht){}Node* _node;const HashTable* _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->_table.size();hashi++;for (; hashi < _pht->_table.size(); hashi++){if (_pht->_table[hashi])break;}if (hashi == _pht->_table.size()){_node = nullptr;//cout << "遍历结束了已经" << endl;}else{_node = _pht->_table[hashi];}}return *this;}
};

2.4 析构函数

析构每个节点，这里可不能调用默认的析构函数，虽然vector可以调用自己的析构，但是我们new出来的节点是没有办法析构的，就需要我们自己手动的析构，和析构链表的节点是一样的：

~HashTable()
{for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}
}

2.5 Begin部分

iterator Begin()
{for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];if (cur)return iterator(cur, this);}return End();
}
iterator End()
{return iterator(nullptr, this);
}
const_iterator Begin() const
{for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];if (cur)return iterator(cur, this);}return End();
}
const_iterator End() const
{return iterator(nullptr, this);
}

在unordered_map一层的代码几乎和map + set那里的一模一样，就不多介绍了。

感谢阅读！