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

🕗 发布于 2024-07-26 10:47 散列表 c++ 哈希算法

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

专题分栏：C++

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

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

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");
//}

谢谢大家！

原文地址：https://blog.csdn.net/qq_73435980/article/details/140649467

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：力扣224【基本计算器】
下一篇：力扣141环形链表问题|快慢指针算法详细推理，判断链表是否有环|龟兔赛跑算法

excel如何快速选中某个数字或者某串数字
鼠标光标放在某个数字或者某串数字的末尾，进行双击鼠标左键即可（就会选中当前鼠标光标前相邻的所有数字）：
阅读更多2024-09-17
面试官问：请描述一次你成功解决问题的经历？
面试官为什么要这么问？面试官问你描述一次成功解决问题的经历，主要是为了评估你的几个关键方面：问题解决能力：了解你在面对挑战时的思维方式和应对策略。决策能力：考察你在压力下做出明智决定的能力。沟通技巧：
阅读更多2024-09-17
VLMEvalKit 评测实践:InternVL2 VS Qwen2VL
多模态技术的突破，正在改变我们理解和交互世界的方式。无论是强大的感知能力、复杂的推理分析，还是图文融合的创新应用，InternVL2 与 Qwen2-VL 展现了大模型的无限可能。
阅读更多2024-09-17
mybatis开启日志
步骤很详细，直接上教程……
阅读更多2024-09-17
MySQL——数据库的高级操作（一）数据备份与还原（1）数据的备份
MySQL——数据库的高级操作（一）数据备份与还原（1）数据的备份
阅读更多2024-09-17
Blender渲染太慢怎么办？blender云渲染已开启
此次，渲染101云渲染农场正式加入了对Blender的全面支持，涵盖Blender的所有版本，不论是较新的Blender 4.0还是早期版本，都可轻松对接渲染101平台服务。不论是小型独立项目还是大型
阅读更多2024-09-17
ubuntu安装mysql 8.0忘记root初始密码，如何重新修改密码
修改my.cnf文件，在文件新增 skip-grant-tables，在启动mysql时不启动grant-tables，授权表。5.注释掉skip-grant-tables后重启mysql。2、修改m
阅读更多2024-09-17
JVM面试真题总结（十一）
总的来说，Java内存模型主要解决了多线程环境下共享数据的一致性、可见性等问题，是Java并发编程的基础。这种模型的好处是，由于启动类加载器是最顶部的加载器，因此它加载的都是最可信任的类库（Java的
阅读更多2024-09-17
Ubuntu 软件仓库镜像使用帮助
选择镜像。
阅读更多2024-09-17
用于稀疏自适应深度细化的掩码空间传播网络 CVPR2024
图像引导的深度补全是一项通过利用稀疏深度测量和RGB图像来估计密集深度图的任务；它通过估算深度来填充未测量的区域。由于许多深度传感器（如LiDAR和飞行时间相机（ToF））只能提供稀疏的深度图，这项任
阅读更多2024-09-17

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

一、标准库中的哈希表

1、unordered_map

2、unordered_set

二、模拟实现哈希表

1、结构

2、注解hashtable的模板参数：

3、重难点

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

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

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

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

三、代码

hash.h

unordered_map.h

unordered_set.h

相关文章

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