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

C/C++进阶（8）哈希表（STL）

news 来源：原创 2024/9/19 14:46:49

个人主页：仍有未知等待探索-CSDN博客

专题分栏：C++

本文着重于模拟实现哈希表，并非是哈希表的使用。

实现的哈希表的底层用的是线性探测法，并非是哈希桶。

一、标准库中的哈希表

1、unordered_map

2、unordered_set

二、模拟实现哈希表

1、结构

2、注解hashtable的模板参数：

3、重难点

1、二元“!=” 没有找到接收类型的右操作数的运算符编辑

2、迭代器的本质、const和非const的区别

3、类A在类B的上面，想要在类A中使用以类B为类型的变量，怎么办？

4、类A在类B的上面，想要在类A中使用类B的私有成员，怎么办？

三、代码

一、标准库中的哈希表

这两个是两种不同映射关系的哈希表。

unordered_map：是 Key - Value 的映射关系（也就是关键字和键值之间的映射）

unordered_set：是 Value 的映射关系（也就是只有键值的映射）

这两种不同的映射关系从各自的模板参数就能看出来。

1、unordered_map

unordered_map又分为两种，一种是unordered_map，另一种是unordered_multimap。

这两种有什么区别呢？

以unordered_map为例：

这里面的模板参数 Key - T 就是这个容器存储的键值关系。

2、unordered_set

同样：unordered_set又分为两种，一种是unordered_set，另一种是unordered_multiset。

这两个的区别和unordered_map中两个的区别一样。

二、模拟实现哈希表

1、结构

在模拟实现哈希表前，我们要知道整个实现的结构，要有完整性的认识。

这个就是哈希表的大致底层结构。

2、注解hashtable的模板参数：

Key：是上层结构（也就是unordered_set、unordered_map）的关键字。
T：是存的关键字和键值的映射。

（也就是unordered_set：pair<Key, Key>；unordered_map:pair<Key, Vaule>）

Ptr是T*。
Ref是T&。
KeyofT是一个仿函数，用来取T的Key。因为在这一层也不知道上一层是unordered_set、unordered_map，所以还需要传一个仿函数来进行取值。
hashfunc是一个仿函数，用来计算hash映射值。

对于一个整数，怎么存储到哈希表里？需要对其进行hash计算，将这个整数取模于表的大小得到。

对于一个字符串，怎么存储到哈希表里？需要对其进行hash计算，将这个字符串转换成整数，然后将这个整数取模于表的大小得到下标。

如果得到的下标冲突了，就用哈希线性探测法解决冲突。

3、重难点

写完不算难，难的是找bug。

1、二元“!=” 没有找到接收类型的右操作数的运算符

类型不匹配，你可以去你出错的位置看看该类型的模板参数的类型匹不匹配。

2、迭代器的本质、const和非const的区别

迭代器就是模拟的指针的行为。

const迭代器和非const迭代器的区别就是限制其*和->运算符的返回值。

3、类A在类B的上面，想要在类A中使用以类B为类型的变量，怎么办？

在类A的前面加上类B的前置声明即可。

4、类A在类B的上面，想要在类A中使用类B的私有成员，怎么办？

在类B中加上类A的友元。

三、代码

hash.h

#pragma once#include <iostream>
#include <vector>
#include <string>
using namespace std;
enum  State
{Empty,Exist,Delete
};
// hash_func ---> 用来对任意类型进行编码
template<class T>
struct hash_func
{size_t operator()(const T& _val){return (size_t)_val;}
};
// 对string类型进行特化
template<>
struct hash_func<string>
{size_t operator()(const string& val){size_t hash = 0;for (auto e : val){hash *= 131;hash += e;}return hash;}
};// 闭散列 --- 线性探测
// 这里的 T 是 K or pair<K, V>
template <class T>
struct HashNode
{HashNode() {}HashNode(const HashNode&) = default;HashNode(const T& data, const State& state):_data(data),_state(state){}T _data;State _state = Empty;};template <class K, class V, class Ptr, class Ref, class KeyofT, class HashFunc>
class HashTable;template<class K, class T, class Ptr, class Ref, class KeyofT>
struct HashTable_iterator
{typedef HashNode<T> HashNode;typedef HashTable_iterator<K, T, Ptr, Ref, KeyofT> iterator;typedef HashTable<K, T, Ptr, Ref, KeyofT, hash_func<K>> hashtable;HashNode* _node;hashtable* _pht;KeyofT kot;hash_func<K> hs;HashTable_iterator(HashNode* node, hashtable* pht):_node(node), _pht(pht){}bool operator!=(const iterator s){return _node != s._node;}Ref operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}iterator& operator++(){int hashindex = 0;for (int i = 0; i < _pht->_tables.size(); i++){// 找到当前节点的位置，寻找下一个节点的位置if (_pht->_tables[i] == _node){hashindex = i;break;}}for (int i = hashindex + 1; i < _pht->_tables.size(); i++){if (_pht->_tables[i] && _pht->_tables[i]->_state == Exist){_node = _pht->_tables[i];return *this;}}_node = nullptr;return *this;}
};template <class K, class V, class Ptr, class Ref, class KeyofT, class HashFunc = hash_func<K>>
class HashTable
{typedef HashNode<V> hashnode;typedef HashTable<K, V, Ptr, Ref, KeyofT, hash_func<K>> hashtable;template<class K, class T, class Ptr, class Ref, class KeyofT>friend struct HashTable_iterator;typedef HashTable_iterator<K, V, Ptr, Ref, KeyofT> iterator;public:hash_func<K> hf;KeyofT kot;HashTable(size_t n = 10):_size(0){_tables.resize(n);}iterator begin(){for (int i = 0; i < _tables.size(); i++){hashnode* cur = _tables[i];if (cur && cur->_state == Exist){// this -> HashTable*return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}// V : V or pair<K, V>pair<iterator, bool> insert(const V& e){iterator it = find(kot(e));if (it != end()){return make_pair(it, false);}if (_size * 10 / _tables.size() >= 7){hashtable newt(_tables.size() * 2);for (int i = 0; i < _tables.size(); i ++ ){if (_tables[i]->_state == Exist){newt.insert(_tables[i]->_data);}}_tables.swap(newt._tables);}size_t hashindex = hf(kot(e)) % _tables.size();while (_tables[hashindex] && _tables[hashindex]->_state == Exist){hashindex++;hashindex %= _tables.size();}hashnode* newnode = new hashnode(e, Exist);swap(_tables[hashindex], newnode);delete newnode;_size++;return make_pair(iterator(_tables[hashindex], this), true);}iterator find(const K& key){size_t hashindex = hf(key)% _tables.size();while (_tables[hashindex] && _tables[hashindex]->_state != Empty){if (_tables[hashindex]->_state == Exist&& kot(_tables[hashindex]->_data) == key){return iterator(_tables[hashindex], this);}++hashindex;hashindex %= _tables.size();}return iterator(nullptr, this);}bool erase(const K& key){iterator t = find(key);if (t._node == nullptr) return false;else{t._node->_state = Delete;--_size;}return true;}
private:vector<hashnode*> _tables;size_t _size;
};

unordered_map.h

#pragma once#include "hash.h"template<class K, class V>
class unordered_map
{struct MapKeyofT{const K& operator()(const pair<const K, V>& key){return key.first;}};
public:typedef HashTable<K, pair<const K, V>, pair<const K, V>*, pair<const K, V>&, MapKeyofT, hash_func<K>> HashTable;typedef HashNode<pair<const K, V>> HashNode;typedef HashTable_iterator<K, pair<const K, V>, pair<const K, V>*, pair<const K, V>&, MapKeyofT> iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const pair<const K, V>& kv){return _ht.insert(kv);}iterator find(const K& key){return _ht.find(key);}bool erase(const K& key){return _ht.erase(key);}V& operator[](const K& key){pair<K, V> pkv = make_pair(key, V());pair<iterator, bool> ret = insert(pkv);return ret.first->second;}
private:HashTable _ht;
};//void map01()
//{
//	unordered_map<int, int> s1;
//	vector<int> v = { 1, 8, 34, 5, 3, 4, 8, 1111, 111, 11 };
//
//	for (auto e : v)
//	{
//		s1.insert({e, e});
//	}
//
//	s1.erase(1111);
//	s1.erase(8);
//}
//
//void map02()
//{
//	unordered_map<string, int> s1;
//	vector<string> v = { "1234", "233", "a", "b", "1234", "233", "a", "b" };
//
//	for (auto e : v)
//	{
//		s1.insert({e, 1});
//	}
//
//	s1.erase("1234");
//	s1.erase("8");
//}

unordered_set.h

#pragma once#include "hash.h"template<class K>
class unordered_set
{struct SetKeyofT{const K& operator()(const K& key){return key;}};
public:typedef HashTable<K, K, const K*, const K&, SetKeyofT, hash_func<K>> HashTable;typedef HashNode<K> HashNode;typedef HashTable_iterator<K, K, const K*, const K&, SetKeyofT> iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const K& val){return _ht.insert(val);}iterator find(const K& key){return _ht.find(key);}bool erase(const K& key){return _ht.erase(key);}
private:HashTable _ht;
};//void set01()
//{
//	unordered_set<int> s1;
//	vector<int> v = { 1, 8, 34, 5, 3, 4, 8, 1111, 11, 11};
//
//	for (auto e : v)
//	{
//		s1.insert(e);
//	}
//
//	s1.erase(1111);
//}
//void set02()
//{
//	unordered_set<string> s;
//	vector<string> v = { "1234", "233", "a", "b" };
//
//	for (auto e : v)
//	{
//		s.insert(e);
//	}
//
//	s.erase("1111");
//	s.erase("1234");
//}

谢谢大家！