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

C++ 哈希表

java 2025/7/6 3:23:04

1. 哈希表的概念

在vector、list的顺序结构中，查找效率为 $O (N)$ ，在set、map的树型结构中，查找效率为 $O(log_2{N})$ ，有没有更优的结构 —— 哈希表

如果让数据按照某种规则映射到某个值，而这个值又是数组的下标，这样，数组的下标与数据之前就建立起了一种关系；查找时，按照相同的规则，自然就能指定的数据，其效率达到 $O (1)$

接下来，问题就变成如何规定映射关系？

最容易想到的：就让数组下标本身作为映射关系，存储的值与其下标相同

这样方便而简单，但却有很大的缺陷：如果数据中的最大值与最小值相差很大，而数据个数又很少，那么实际上大部分空间都是浪费了

在这里插入图片描述

有没有一种即能将数据映射到数组中的每一个位置，又尽量的少浪费空间的方法，这里给出的方法是除留余数法

将要存储数据的 值 % 数组的大小，得到的就是数据实际存储的位置

在这里插入图片描述

上述过程中，数据与数组下标之间的映射关系的计算方法叫做哈希算法/哈希函数，而以这种方式存储数据的数组叫做哈希表

当然，如果仅仅使用除留余数法的话，仍存在问题：

数据的个数 > 数组的容量时，根据鸽巢原理，一定会有两个数据映射到同一个下标，如何解决？
如果要存储的数据不是整形，而是字符串，不就不能进行取余操作了吗，如何解决？

对于两个数据映射到同一个下标的问题，我们称为哈希冲突

解决哈希冲突主要有两种方法：

闭散列：开放定址法
开散列：哈希桶

开放定址法的策略是：当新插入的数据与原数据发生哈希冲突时，按照特定的方法寻找空的位置给新插入数据

这里特定的方法主要有两种：

线性探测
二次探测

哈希桶的策略是：哈希表中的每个位置都是一个桶结构，当新插入数据与原数据发生冲突时，直接挂到当前桶下

而对于要存储的数据不能进行取余操作，只需再构建一层映射关系，比如string，我们让string映射到某个整数，再让这个整数映射到哈希表的下标即可

2. 哈希表的实现

开放定址法

这里主要讲解线性探测

使用开放定址法解决哈希冲突时，哈希表中每个位置的初始值应该多少？好像是几都不合适，因为不管是几，遍历到该位置时，这个位置到底是空、已经删除，还是有数据无法确认；因此，每个位置还需要添加一个状态标记

enum Status
{EXIST,EMPTY,DELETE
};template<typename K, typename V>
struct HashData
{HashData() = default;HashData(const pair<K, V>& kv):_kv(kv){}pair<K, V> _kv;Status _status = EMPTY;
};

插入的流程：首先根据除留余数法计算它映射到的位置，如果该位置已有数据，往后找，直到为空

在这里插入图片描述

当然，如果哈希表中的数据过多，冲突的概率也就变大，遍历的次数就会越来越多，效率就变低

因此，什么时候进行扩容就十分关键，这里提出负载因子的概念，负载因子 = 有效数据个数 / 表的大小，当负载因子超过某个值时，进行扩容

如何选定负载因子的临界值？如果该值过小，比如0.5，意味着哈希表中总会有50%的空间被浪费，如果过大，哈希表的整体效率就会变低

这里选定0.7作为负载因子的临界值，即当负载因子超过0.7时，进行扩容

当然，插入数据的前提是该数据不在哈希表中；因此，插入之前先查找

至于删除，可以利用查找，找到后直接将数据的状态啊置为DELETE即可

template<typename K, typename V>
class HashTable
{
public:HashTable(){_table.resize(5);}bool insert(const pair<K, V>& kv){if (find(kv.first)) return false;// 当负载因子 > 0.7 时,进行扩容if (_n * 10 / _table.size() > 7){size_t newsize = _table.size() * 2;HashTable newtable;newtable._table.resize(newsize);for (int i = 0; i < _table.size(); i++){if (_table[i]._status == EXIST){newtable.insert(_table[i]._kv);}}_table.swap(newtable._table);}size_t pos = kv.first % _table.size();while (_table[pos]._status == EXIST){pos++;pos %= _table.size();}_table[pos]._kv = kv;_table[pos]._status = EXIST;_n++;return true;}HashData<K, V>* find(const K& key){size_t pos = key % _table.size();while (_table[pos]._status != EMPTY){if (_table[pos]._kv.first == key && _table[pos]._status != DELETE){return &_table[pos];}pos++;pos %= _table.size();}return nullptr;}void erase(const K& key){HashData<K, V>* res = find(key);if (res == nullptr) return;res->_status = DELETE;_n--;}private:vector<HashData<K, V>> _table;size_t _n = 0;
};

线性探测的缺点：

当发生冲突时，会往后找空的位置，这样会导致数据堆积在一起，一旦堆积的数据过多，发生冲突时往后寻找空位置的效率也就越低，哈希表的整体效率也就越低

如何缓解线性探测带来的问题？二次探测，即发生冲突时，往后以2的次方的间隔查找空的位置

哈希桶

哈希表的另一种实现方式，哈希桶，也是 STL unordered_set/map底层使用的数据结构

哈希表每个位置不再是一个个的数据，而是一个桶结构，下面可以挂载许多数据

当插入数据时，同样根据除留余数法计算出映射的位置，不同的是，发生冲突时，直接将冲突的数据挂到当前桶下即可

在这里插入图片描述

同时规定，当负载因子为1时才进行扩容，相当于平均每个桶下都有一个节点

而扩容的逻辑，我们不再遍历原哈希表，遇到一个节点就开一个新节点，挂到新哈希表下，直接遍历原哈希表，计算映射位置后，将节点的指针直接挂到新哈希表下，然后将原哈希表与新哈希表交换即可

同样的，在插入之前先查找；而删除的操作，自然也是十分简单了

template<typename K, typename V>
struct HashNode
{HashNode() = default;HashNode(const pair<K, V>& kv):_kv(kv){}using Node = HashNode<K, V>;pair<K, V> _kv;Node* _next = nullptr;
};template<typename K, typename V>
class HashTable
{
public:using Node = HashNode<K, V>;HashTable(){_table.resize(5, nullptr);}bool insert(const pair<K, V>& kv){if (this->find(kv.first)) return false;// 当负载因子为 1 时,进行扩容if (_n / _table.size() == 1){size_t newsize = _table.size() * 2;vector<Node*> newtable(newsize, nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t pos = cur->_kv.first % newtable.size();cur->_next = newtable[pos];newtable[pos] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}size_t pos = kv.first % _table.size();Node* newnode = new Node(kv);newnode->_next = _table[pos];_table[pos] = newnode;_n++;return true;}Node* find(const K& key){size_t pos = key % _table.size();Node* cur = _table[pos];while (cur){if (cur->_kv.first == key) return cur;cur = cur->_next;}return nullptr;}void erase(const K& key){size_t pos = key % _table.size();Node* cur = _table[pos], * prev = nullptr;while (cur){if (cur->_kv.first == key){Node* next = cur->_next;if (prev == nullptr) _table[pos] = next;else prev->_next = next;delete cur;return;}else{prev = cur;cur = cur->_next;}}}private:vector<Node*> _table;size_t _n = 0;
};

任意类型的映射

到目前为止，我们只完成了int类型的映射关系，如果是自定义类型，并不支持取余操作，该如何进行映射？

再构建一层映射关系，将不支持取余操作的类型映射为int，再对该int值进行取余操作

采用仿函数的方式，给哈希表传递一个仿函数，该仿函数完成任意一个类型映射成整形的操作

使用何种哈希算法将自定义类型映射为整数？那string举例，我们可以将所有字符的ASCII字符相加，作为其映射的整形，但这样做冲突率很高

实际上，专家们研究过，如何将字符串映射为整形，而又保证了其冲突率较低

其中较为著名的是BKDR算法，将结果与31/131/1313…相乘后再与字符串的ASCII相加，得到的结果冲突率是比较低的

我们使用模板的特化将字符串的哈希算法单独处理，将该仿函数作为哈希表的模板参数传入

如果有自定义类型想要映射成整数，也能够这样处理

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

template<typename K, typename V, typename Hash = HashFunc<K>>
class HashTable
{
public:using Node = HashNode<K, V>;HashTable(){_table.resize(5, nullptr);}bool insert(const pair<K, V>& kv){if (this->find(kv.first)) return false;Hash hash;// 当负载因子为 1 时,进行扩容if (_n / _table.size() == 1){size_t newsize = _table.size() * 2;vector<Node*> newtable(newsize, nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t pos = hash(cur->_kv.first) % newtable.size();cur->_next = newtable[pos];newtable[pos] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}size_t pos = hash(kv.first) % _table.size();Node* newnode = new Node(kv);newnode->_next = _table[pos];_table[pos] = newnode;_n++;return true;}Node* find(const K& key){Hash hash;size_t pos = hash(key) % _table.size();Node* cur = _table[pos];while (cur){if (cur->_kv.first == key) return cur;cur = cur->_next;}return nullptr;}void erase(const K& key){Hash hash;size_t pos = hash(key) % _table.size();Node* cur = _table[pos], * prev = nullptr;while (cur){if (cur->_kv.first == key){Node* next = cur->_next;if (prev == nullptr) _table[pos] = next;else prev->_next = next;delete cur;return;}else{prev = cur;cur = cur->_next;}}}private:vector<Node*> _table;size_t _n = 0;
};

查看全文

http://www.xdnf.cn/news/1261.html