哈希表及模拟实现

embedded/2025/1/12 23:06:59/

目录

一、哈希表的概念 

二、模拟实现哈希表

1.开放地址法

(1)哈希表的数据加上状态标志

(2)哈希表扩容：载荷因子

(3)哈希函数：不同数据类型转换为整型

(4)完整代码

2.链地址法（哈希桶）

(1)哈希表扩容：载荷因子

(2)完整代码

一、哈希表的概念 

哈希表本质是一个数组（数组中的每个位置称为槽或桶），数据检索十分高效，它利用哈希函数将键值对映射到哈希表中的特定位置，哈希函数可以计算键的哈希值，从而确定该键值对在哈希表中的存储位置（理想的哈希函数要尽可能均匀地分布键值对）。

冲突：

例如存在键值对<1, 'A'>、<100001, 'B'>、<999, 'C'>、<345, 'D'>，哈希函数为h(key)=key%10，所以<1, 'A'>存储在1位置，<100001, 'B'>存储在1位置，<999, 'C'>存储在9位置，<345, 'D'>存储在5位置，<1, 'A'>和<100001, 'B'>发生冲突。

冲突处理：

冲突处理的方法有两种：开放地址法和链地址法

  • 开放地址法：当发生冲突时，寻找哈希表的下一个空位置，将键值对存储进其中（寻找哈希表下一个空位置的常见方法又有三种：线性探测、二次探测、双哈希）。开放地址法会导致其他键值对原本的位置被占用，又需要重新寻找下一个空位置。
  • 链地址法：哈希表中的每一个位置是一个链表（或者其他动态数据结构），发生冲突的键值对都会被存储到该链表中。如果要查找键值对，先要找到哈希表中链表的位置，再在链表中搜索

二、模拟实现哈希表

1.开放地址法

开放地址法在存储键值对时，首先会根据键值对的键计算哈希值，确定键值对所在槽，如果该槽已被其他数据所占，则向后遍历哈希寻找空槽，再将数据存储到空槽中。

(1)哈希表的数据加上状态标志

假设开放地址法使用的是线性探测解决冲突，当键值对原本的槽被占用时，会向后遍历寻找最近的一个空槽。这就说明当哈希表中未发生数据删除时，两个冲突数据之间一定是没有空槽的。所以开放地址法的查找函数结束条件是查找到空槽。

问题出现：当哈希表中数据被删除时，且恰巧删除的是某两个冲突数据位置之间的数据，那么此时的查找函数就会出问题，因为两个冲突数据之间存在了空槽，就会导致无法查找到后一个数据。

问题解决：哈希表的数据不仅存储的键值对，还要存储一个状态标志，表示该槽为空，还是数据被删除，还是不为空。使用结构体封装键值对和状态标志作为哈希表的存储元素。这样查找函数查找到空槽就分为两种：槽中数据被删除、槽为空，只有当槽为空时才为结束条件

//状态标志
enum State {EMPTY,//槽为空EXIST,//槽不为空DELETE//槽中数据被删除
};
//哈希表数据元素
template<class K,class V>
struct HashData {std::pair<K, V> _kv;//键值对State _state = EMPTY;//状态标志
};
//哈希表
template<class K,class V>
class HashTable {
private:std::vector<HashData<K, V>> _tables;//哈希表size_t _n = 0;//哈希表中已经存储的元素个数
};
(2)哈希表扩容：载荷因子

载荷因子=哈希表已存元素个数/哈希表总容量

哈希表中存储的元素越多，冲突率就越高，哈希表查找效率就越低

即载荷因子越大，冲突率越高，哈希表效率越低，空间利用率越高；

    载荷因子越小，冲突率越小，哈希表效率越高，空间利用率越低。

因此不能使哈希表满，而且必须在哈希表满之前就扩容。为此我们可以根据载荷因子设定一个界限，载荷因子既不能太大，也不能太小。例如当载荷因子大于0.7时就扩容。

扩容方法：

哈希表的扩容不仅要将哈希表长度变大，还要将哈希表中的数据重新映射

创建一个新对象，将新对象中的哈希表扩容为旧哈希表的二倍，再复用insert函数将数据重新映射到新对象的哈希表中，最后将新对象的哈希表赋值给旧对象。

（下述insert函数还未完善，没有防止数据冗余）

//构造函数
HashTable()
{_tables.resize(10);//哈希表容量初始化为10，避免计算载荷因子时除数为0
}
//插入函数
void insert(const std::pair<K, V>& kv)
{//扩容if (_n / (float)_tables.size() >= 0.7){HashTable<K, V> newHT;//新对象newsize = 2 * _tables.size();//新容量（2倍扩容）newHT._tables.resize(newsize);//重新映射for (int i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST)newHT.insert(_tables[i]._kv);}_tables = newHT._tables;}//计算哈希值int hashi = kv.first % _tables.size();//线性探测：寻找空槽while (_tables[hashi]._state == EXIST){++hashi;hashi = hashi % _tables.size();//哈希表的线性探测是循环的，查找到哈希表末尾后会跳转到哈希表头部继续查找}//插入数据_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;
}
(3)哈希函数：不同数据类型转换为整型

哈希函数为key值%哈希表大小，但是如果key是string等其他类型，无法做取模运算，就需要先将key转换为整型再取模。

key的可能类型有许多，因此需要进行泛型编程：设计仿函数，对于可以直接强转为整型的数据使用默认的仿函数，对于其他不能直接强转为整型的数据需要自己提供仿函数将数据转换为整型。

例如string类型，可以采用直接相加法（将所有的字符的ASCII码相加得到整数）、位运算法（将每个字符的ASCII码左移后再相加）。

此处介绍的是BKDRHash算法：遍历字符串，当前哈希值乘131再加上当前字符的ASCII码值。

对比unordered_set和unordered_set发现，这两个容器对于key为string类型时并没有需要自己提供哈希函数，这是因为unordered_set和unordered_set源码中对string类型进行了模板特化。所以我们在模拟实现时也是用模板特化：特化string，当key类型是int、float等可以直接强转为整型的数据就使用默认的哈希函数，如果是string类型就使用特化的哈希函数，如果是其他类型就需要我们自己提供哈希函数将key值转换为整型数据。

//默认哈希函数（仿函数），针对可以直接强转为整型的类型
template<class K>
struct HashFunc {size_t operator()(const K& key){return size_t(key);}
};
//默认哈希函数对string类型进行模板特化
template<>
struct HashFunc<std::string> {size_t operator()(const std::string& key){size_t hashi = 0;for (auto& ch : key){hashi *= 131;hashi += ch;}return hashi;}
};
//哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:std::vector<HashData<K, V>> _tables;//哈希表size_t _n = 0;//哈希表中已经存储的元素个数
......
......
(4)完整代码
#include <iostream>
#include <vector>
#include <string>
//状态标志
enum State {EMPTY,//槽为空EXIST,//槽不为空DELETE//槽中数据被删除
};
//哈希表数据元素
template<class K, class V>
struct HashData {std::pair<K, V> _kv;//键值对State _state = EMPTY;//状态标志
};
//默认哈希函数（仿函数），针对可以直接强转为整型的类型
template<class K>
struct HashFunc {size_t operator()(const K& key){return size_t(key);}
};
//默认哈希函数对string类型进行模板特化
template<>
struct HashFunc<std::string> {size_t operator()(const std::string& key){size_t hashi = 0;for (auto& ch : key){hashi *= 131;hashi += ch;}return hashi;}
};
//哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:std::vector<HashData<K, V>> _tables;//哈希表size_t _n = 0;//哈希表中已经存储的元素个数
public://构造函数HashTable(){_tables.resize(10);//哈希表容量初始化为10，避免计算载荷因子时除数为0}//插入函数bool Insert(const std::pair<K, V>& kv){//防止数据冗余if (Find(kv.first))return false;//扩容if (_n / (float)_tables.size() >= 0.7){HashTable<K, V> newHT;//新对象size_t newsize = 2 * _tables.size();//新容量（2倍扩容）newHT._tables.resize(newsize);//重新映射for (int i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST)newHT.Insert(_tables[i]._kv);}//新表赋值给旧表_tables = newHT._tables;}//计算哈希值Hash hs;size_t hashi = hs(kv.first) % _tables.size();//线性探测：寻找空槽（DELETE和EMPTY都行）while (_tables[hashi]._state == EXIST){++hashi;hashi = hashi % _tables.size();//哈希表的线性探测是循环的，查找到哈希表末尾后会跳转到哈希表头部继续查找}//插入数据_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;}//查找函数HashData<K, V>* Find(const K& key){//计算哈希值Hash hs;size_t hashi = hs(key) % _tables.size();//线性探测：找到空槽结束（只有EMPTY才行）while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state != DELETE){if (_tables[hashi]._kv.first == key)return &_tables[hashi];//查找成功}++hashi;hashi = hashi % _tables.size();}//未查找到return nullptr;}//删除函数bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr)return false;else{ret->_state = DELETE;--_n;return true;}}
};
void test()
{HashTable<std::string, std::string> ht;ht.Insert({ "5","5"}); ht.Insert({"10","10"}); ht.Insert({"8", "8"});std::cout << ht.Find("8") << std::endl;std::cout << ht.Find("5") << std::endl;std::cout << ht.Find("20") << std::endl;ht.Erase("8");std::cout << ht.Find("8") << std::endl;std::cout << ht.Find("5") << std::endl;std::cout << ht.Find("20") << std::endl;
}
int main()
{test();return 0;
}
2.链地址法（哈希桶）

链地址法存储键值对时，哈希表的每一个位置其实是一个链表，当键值对要存储的槽已经被其他数据所占时，会直接头插在该槽的链表中。

(1)哈希表扩容：载荷因子

链地址法中的哈希表也需要扩容，否则哈希表中的链表会很长，效率低。采用链地址法的哈希表也是需要根据载荷因子决定是否扩容，载荷因子的值通常设置为1（源码中就是1）。

和开放地址法一样，扩容时创建新哈希表，复用Insert函数，并且哈希表中的链表的所有元素都要重新映射。但是这个方法效率低下，因为复用Insert函数在遍历旧哈希表时，每次都需要创建新的节点数据插入新哈希表，之后还要再销毁该节点数据。

改进方法：遍历旧哈希表，直接使用旧哈希表中的节点数据存入新哈希表，不再复用Insert函数和创建新节点数据。

//插入函数
bool Insert(const std::pair<K, V>& kv)
{//防止数据冗余if (Find(kv.first))return false;//扩容if (_n / _tables.size() >= 1){//HashTable<K, V> newHT;//创建新哈希表//newHT._tables.resize(2 * _tables.size());//2倍扩容//创建新哈希表std::vector<Node*> newtables(2 * _tables.size());//数据重新映射到新表中（链表中的所有数据都要重新映射）for (int i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//计算哈希值Hash hs;size_t hashi = hs(cur->_kv.first) % newtables.size();//直接将旧哈希表中的数据存入新哈希表（头插）cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;//复用Insert函数方法（舍弃）//Node* cur = _tables[i];//while (cur)//{//	newHT.Insert(cur->_kv);//	cur = cur->_next;//}}_tables = newtables;}//计算哈希值Hash hs;size_t hashi = hs(kv.first) % _tables.size();//插入数据（头插）Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}
(2)完整代码
namespace hash_bucket {//哈希表数据元素template<class K, class V>struct HashNode {std::pair<K, V> _kv;//键值对struct HashNode<K, V>* _next;//链表指针//构造函数HashNode(const std::pair<K, V> kv):_kv(kv),_next(nullptr){}};//默认哈希函数（仿函数），针对可以直接强转为整型的类型template<class K>struct HashFunc {size_t operator()(const K& key){return size_t(key);}};//默认哈希函数对string类型进行模板特化template<>struct HashFunc<std::string> {size_t operator()(const std::string& key){size_t hashi = 0;for (auto& ch : key){hashi *= 131;hashi += ch;}return hashi;}};//哈希表template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;private:std::vector<Node*> _tables;//哈希表size_t _n;//哈希表中已存元素个数public://构造函数HashTable(){_tables.resize(10);_n = 0;}//拷贝构造函数HashTable(const HashTable& ht){_tables = new std::vector<Node*>(ht._tables.size());_n = ht._n;}//析构函数（释放哈希表中每个槽中的链表）~HashTable(){for (int 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 std::pair<K, V>& kv){//防止数据冗余if (Find(kv.first))return false;//扩容if (_n / _tables.size() >= 1){//HashTable<K, V> newHT;//创建新哈希表//newHT._tables.resize(2 * _tables.size());//2倍扩容//创建新哈希表std::vector<Node*> newtables(2 * _tables.size());//数据重新映射到新表中（链表中的所有数据都要重新映射）for (int i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//计算哈希值Hash hs;size_t hashi = hs(cur->_kv.first) % newtables.size();//直接将旧哈希表中的数据存入新哈希表（头插）cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;//复用Insert函数方法（舍弃）//Node* cur = _tables[i];//while (cur)//{//	newHT.Insert(cur->_kv);//	cur = cur->_next;//}}_tables = newtables;}//计算哈希值Hash hs;size_t hashi = hs(kv.first) % _tables.size();//插入数据（头插）Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}//查找函数Node* Find(const K& key){//计算哈希值Hash hs;size_t hashi = hs(key) % _tables.size();//查找数据Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr;}//删除函数bool Erase(const K& key){Node* ret = Find(key);if (ret == nullptr)return false;else{//计算哈希值，确认数据所在槽Hash hs;size_t hashi = hs(key) % _tables.size();if (_tables[hashi]->_kv.first == key)//key是所在槽中链表的的头节点{Node* cur = _tables[hashi];_tables[hashi] = cur->_next;delete(cur);}else//key是所在槽中链表的的中间节点{Node* cur = _tables[hashi];Node* prev = cur;while (cur->_kv.first != key){prev = cur;cur = cur->_next;}//删除数据Node* temp = cur;prev->_next = cur->_next;delete(temp);}--_n;return true;}}};
}
void test2()
{hash_bucket::HashTable<std::string, int> ht;ht.Insert({ "10",10 }); ht.Insert({ "8",8 }); ht.Insert({ "2",2 }); ht.Insert({ "9",9 }); ht.Insert({ "1",1 });ht.Insert({ "3",3 }); ht.Insert({ "4",4 }); ht.Insert({ "6",6 }); ht.Insert({ "7",7 }); ht.Insert({ "5",5 });ht.Insert({ "888",888 });std::cout << ht.Find("10") << std::endl;std::cout << ht.Find("8") << std::endl;std::cout << ht.Find("999") << std::endl;ht.Erase("10");std::cout << ht.Find("10") << std::endl;std::cout << ht.Find("8") << std::endl;std::cout << ht.Find("999") << std::endl;
}
int main()
{//test1();test2();return 0;
}

http://www.ppmy.cn/embedded/153400.html

相关文章

分布式ID—雪花算法

分布式ID—雪花算法

背景 现在的服务基本是分布式、微服务形式的&#xff0c;而且大数据量也导致分库分表的产生&#xff0c;对于水平分表就需要保证表中 id 的全局唯一性。 对于 MySQL 而言&#xff0c;一个表中的主键 id 一般使用自增的方式&#xff0c;但是如果进行水平分表之后&#xff0c;多…
阅读更多...
Java 的单例模式详解及优化

Java 的单例模式详解及优化

&#x1f496; 欢迎来到我的博客&#xff01; 非常高兴能在这里与您相遇。在这里&#xff0c;您不仅能获得有趣的技术分享&#xff0c;还能感受到轻松愉快的氛围。无论您是编程新手&#xff0c;还是资深开发者&#xff0c;都能在这里找到属于您的知识宝藏&#xff0c;学习和成长…
阅读更多...
蓝桥杯算法|练习记录

蓝桥杯算法|练习记录

位运算 按位与运算符&#xff08;&&#xff09; 运算规则&#xff1a;两位同时为1&#xff0c;结果才为1&#xff0c;否则结果为0。例如&#xff0c; -3&#xff08;在计算机中表示为1101&#xff09;&5&#xff08;0101&#xff09; 0101&#xff08;即十进制的1&…
阅读更多...
Spring Boot 支持哪些日志框架

Spring Boot 支持哪些日志框架

Spring Boot 支持多种日志框架&#xff0c;主要包括以下几种&#xff1a; SLF4J (Simple Logging Facade for Java) Logback&#xff08;默认&#xff09;Log4j 2Java Util Logging (JUL) 其中&#xff0c;Spring Boot 默认使用 SLF4J 和 Logback 作为日志框架。如果你需要使…
阅读更多...
DSP+Simulink——点亮LED灯(TMSDSP28379D)超详细

DSP+Simulink——点亮LED灯(TMSDSP28379D)超详细

实现功能&#xff1a;DSP28379D-LED灯闪烁 :matlab为2019a :环境建立见之前文章 Matlab2019a安装C2000 Processors超详细过程 matlab官网链接&#xff1a; Getting Started with Embedded Coder Support Package for Texas Instruments C2000 Processors Overview of Creat…
阅读更多...
2025-1-10-sklearn学习(36、37) 数据集转换-无监督降维+随机投影 沙上并禽池上暝。云破月来花弄影。

2025-1-10-sklearn学习(36、37) 数据集转换-无监督降维+随机投影 沙上并禽池上暝。云破月来花弄影。

文章目录 sklearn学习(36、37) 数据集转换-无监督降维随机投影sklearn学习(36) 数据集转换-无监督降维36.1 PCA: 主成份分析36.2 随机投影36.3 特征聚集 sklearn学习(37) 数据集转换-随机投影37.1 Johnson-Lindenstrauss 辅助定理37.2 高斯随机投影37.3 稀疏随机矩阵 sklearn学…
阅读更多...
HarmonyOS鸿蒙-@State@Prop装饰器限制条件

HarmonyOS鸿蒙-@State@Prop装饰器限制条件

一、组件Components级别的状态管理&#xff1a; State组件内状态限制条件 1.State装饰的变量必须初始化&#xff0c;否则编译期会报错。 // 错误写法&#xff0c;编译报错 State count: number;// 正确写法 State count: number 10; 2.嵌套属性的赋值观察不到。 // 嵌套的…
阅读更多...
Oracle Dataguard（主库为双节点集群）配置详解（3）：配置主库

Oracle Dataguard（主库为双节点集群）配置详解（3）：配置主库

Oracle Dataguard&#xff08;主库为双节点集群&#xff09;配置详解&#xff08;3&#xff09;&#xff1a;配置主库 目录 Oracle Dataguard&#xff08;主库为双节点集群&#xff09;配置详解&#xff08;3&#xff09;&#xff1a;配置主库一、开启归档二、开启强制日志三、…
阅读更多...
最新文章

Copyright @ 2022~2023