unordered_map哈希策略函数
1. load_factor
float load_factor() const noexcept;
load_factor 函数用于获取当前散列表的负载因子，它返回一个 float 值表示负载因子。
负载因子是指当前散列表中包含的元素数量与桶的总数之比。通常，负载因子越小，散列表的性能越好，因为冲突的概率较低。
示例代码：
#include <iostream> #include <unordered_map> int main() { std::unordered_map<int, std::string> map; // 设置一些键值对 map[1] = "one"; map[2] = "two"; map[3] = "three"; // 获取当前负载因子 float lf = map.load_factor(); std::cout << "Load Factor: " << lf << std::endl; return 0; }
在这个示例中，我们创建了一个 std::unordered_map 容器，并插入了一些键值对。然后，我们使用 load_factor 函数获取了当前负载因子，并将其打印出来。
2. max_load_factor
max_load_factor 函数用于设置或获取散列表的最大负载因子。最大负载因子是在发生重新哈希（rehashing）之前允许的最大负载因子。
float max_load_factor() const noexcept;：获取当前散列表的最大负载因子。void max_load_factor(float z);：设置散列表的最大负载因子为z。
示例代码：
#include <iostream> #include <unordered_map> int main() { std::unordered_map<int, std::string> map; // 获取当前最大负载因子 float maxLF = map.max_load_factor(); std::cout << "Current Max Load Factor: " << maxLF << std::endl; // 设置最大负载因子为新值 map.max_load_factor(0.75); // 获取新的最大负载因子 maxLF = map.max_load_factor(); std::cout << "Updated Max Load Factor: " << maxLF << std::endl; return 0; }
在这个示例中，我们首先获取了当前散列表的最大负载因子，然后将其修改为新值。通过调用 max_load_factor 函数，可以控制散列表在重新哈希之前的负载因子，以优化性能。
3. rehash
rehash 函数用于重新调整散列表的桶（buckets）数量，以便容纳至少 n 个元素，以提高散列表的性能。重新哈希会更改桶的数量，重新分布元素，因此它可能会耗费一些时间。
void rehash(size_type n);：重新调整散列表的桶的数量，使其至少能够容纳n个元素。
示例代码：
#include <iostream> #include <unordered_map> int main() { std::unordered_map<int, std::string> map; // 添加一些元素 map[1] = "One"; map[2] = "Two"; map[3] = "Three"; // 获取当前桶的数量 size_t currentBucketCount = map.bucket_count(); std::cout << "Current Bucket Count: " << currentBucketCount << std::endl; // 重新调整桶的数量 map.rehash(10); // 获取新的桶的数量 currentBucketCount = map.bucket_count(); std::cout << "Updated Bucket Count: " << currentBucketCount << std::endl; return 0; }
在这个示例中，我们首先添加了一些元素到散列表中，然后使用 rehash 函数将桶的数量重新调整为 10。重新哈希可能会在添加大量元素后用于优化性能，以确保负载因子保持在合适的范围内。
4. reserve
reserve 函数用于预留至少能够容纳 n 个元素的桶空间，以提高散列表的性能。这个函数可以帮助你在插入大量元素之前分配足够的桶空间，以避免频繁的重新哈希操作。
void reserve(size_type n);：预留至少能够容纳n个元素的桶空间。
示例代码：
#include <iostream> #include <unordered_map> int main() { std::unordered_map<int, std::string> map; // 预留足够的桶空间 map.reserve(100); // 预留至少能容纳 100 个元素的桶空间 // 添加一些元素 for (int i = 0; i < 100; ++i) { map[i] = "Value " + std::to_string(i); } // 获取当前桶的数量 size_t currentBucketCount = map.bucket_count(); std::cout << "Current Bucket Count: " << currentBucketCount << std::endl; return 0; }
在这个示例中，我们使用 reserve 函数预留了至少能够容纳 100 个元素的桶空间，然后向散列表中添加了 100 个元素。这可以帮助提高性能，因为预留了足够的桶空间，避免了在插入元素时频繁的重新哈希操作。
unordered_map开散列形式模拟实现
修改上篇哈希博客的哈希表实现
template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } };
operator()是函数调用运算符的重载，允许对象像函数一样被调用。- 函数接受一个参数
key，该参数表示要计算哈希值的键。 - 函数体内，
(size_t)key将键key强制转换为size_t类型，以得到其哈希值。 - 哈希值是一个用于标识键在哈希表中位置的数值。通常，哈希函数会将不同的键映射到不同的哈希值，以便在哈希表中进行高效的查找操作
哈希迭代器增加
template<class K, class T, class Hash, class KeyOfT> struct __HashIterator { typedef HashNode<T> Node; typedef HashTable<K, T, Hash, KeyOfT> HT; typedef __HashIterator<K, T, Hash, KeyOfT> Self; Node* _node; HT* _pht; __HashIterator(Node* node, HT* pht) :_node(node) , _pht(pht) {} T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } Self& operator++() { if (_node->_next) { // 当前桶中迭代 _node = _node->_next; } else { // 找下一个桶 Hash hash; KeyOfT kot; size_t i = hash(kot(_node->_data)) % _pht->_tables.size(); ++i; for (; i < _pht->_tables.size(); ++i) { if (_pht->_tables[i]) { _node = _pht->_tables[i]; break; } } // 说明后面没有有数据的桶了 if (i == _pht->_tables.size()) { _node = nullptr; } } return *this; } bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } };
typedef HashNode<T> Node;：为HashNode<T>类型起一个别名Node，HashNode通常表示哈希表中的节点。typedef HashTable<K, T, Hash, KeyOfT> HT;：为HashTable模板类实例化后的类型起一个别名HT，HashTable通常表示哈希表。typedef __HashIterator<K, T, Hash, KeyOfT> Self;：为迭代器自身的类型起一个别名Self，这个别名在迭代器内部用于定义迭代器类型。Node* _node;：指向当前迭代节点的指针。迭代器用于遍历哈希表中的节点，当前节点的信息存储在_node中。HT* _pht;：指向哈希表的指针。哈希表的信息存储在_pht中，迭代器可能需要访问哈希表的属性以实现迭代操作。T& operator*()：重载*运算符，使迭代器可以像指针一样用*来访问当前节点的数据。T* operator->()：重载->运算符，使迭代器可以像指针一样用->来访问当前节点的数据。Self& operator++()：重载前置自增运算符++，使迭代器可以前进到下一个节点。该函数会检查当前桶内是否还有节点，如果有，则移到下一个节点；否则，找到下一个非空桶，将_node指向该桶的第一个节点。bool operator!=(const Self& s) const：重载不等于运算符!=，用于比较两个迭代器是否不相等。bool operator==(const Self& s) const：重载等于运算符==，用于比较两个迭代器是否相等。
typedef __HashIterator<K, T, Hash, KeyOfT> iterator; iterator begin() { for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) { return iterator(_tables[i], this); } } return end(); } iterator end() { return iterator(nullptr, this); }
typedef __HashIterator<K, T, Hash, KeyOfT> iterator;：这一行定义了iterator类型为__HashIterator的别名，从而使你能够像使用普通的 C++ 迭代器一样使用它。iterator begin()函数：这个函数返回指向哈希表中第一个非空桶的迭代器。它通过遍历_tables容器中的桶，找到第一个非空桶，并创建一个对应的迭代器，然后返回该迭代器。如果没有找到非空桶，就返回end()迭代器，表示遍历结束。iterator end()函数：这个函数返回表示遍历结束的迭代器。它返回一个迭代器，其中的_node成员为nullptr，表示当前没有有效节点可供迭代。这在标识迭代结束时非常有用。
添加__stl_num_primes函数
inline size_t __stl_next_prime(size_t n) { static const size_t __stl_num_primes = 28; static const size_t __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; for (size_t i = 0; i < __stl_num_primes; ++i) { if (__stl_prime_list[i] > n) { return __stl_prime_list[i]; } } return -1; }
__stl_num_primes定义了一个常量数组，其中包含了一系列素数值。这些素数值是经过精心选择的，用于在数据结构的容量扩展时作为新容量的候选值。- 函数首先遍历这个素数数组，找到第一个大于给定数
n的素数，并返回它。这个操作保证了容器的大小总是选择了一个足够大的素数，以降低哈希冲突的概率。 - 如果没有找到适合的素数，函数返回 -1，这表示发生了异常情况，可以根据需要进行错误处理。
这个函数的主要目的是为了优化哈希表的性能，确保它的容量总是选择一个适当的素数，以提高哈希算法的效率(参考STL源码)。
修改insert函数
pair<iterator, bool> Insert(const T& data) { Hash hash; KeyOfT kot; // 去重 iterator ret = Find(kot(data)); if (ret != end()) { return make_pair(ret, false); } // 负载因子到1就扩容 if (_size == _tables.size()) { vector<Node*> newTables; newTables.resize(__stl_next_prime(_tables.size()), nullptr); // 旧表中节点移动映射新表 for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hashi = hash(kot(cur->_data)) % newTables.size(); cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } size_t hashi = hash(kot(data)) % _tables.size(); // 头插 Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_size; return make_pair(iterator(newnode, this), true); }
- 首先，代码创建了一个
Hash和一个KeyOfT的实例，这是为了获取键的哈希值和键本身。 - 接下来，代码通过调用
Find(kot(data))函数来检查是否已经存在具有相同键的元素。如果找到了相同的键，就不进行插入操作，而是返回一个pair，其中iterator部分指向已存在的元素，而bool部分设置为false表示插入失败。 - 如果没有找到相同的键，就会继续进行插入操作。首先，代码检查当前哈希表的负载因子是否达到了1（即元素个数等于哈希表大小），如果是的话，就需要进行扩容操作。
- 扩容操作会创建一个新的哈希表
newTables，其大小通过调用__stl_next_prime(_tables.size())来确定，这确保了新的表大小是一个素数。然后，代码会遍历旧的哈希表，将每个节点重新映射到新的哈希表中。这是为了保持哈希表的均匀分布和减少哈希冲突的可能性。 - 最后，代码计算待插入元素的哈希值，并将新节点插入到新的哈希表中。这是通过在头部插入方式实现的，新节点的
_next指针指向当前桶的头节点，然后更新当前桶的头节点为新节点。同时，元素个数_size会增加 1。 - 最终，代码返回一个
pair，其中iterator部分指向新插入的元素，而bool部分设置为true表示插入成功。
添加桶函数
size_t Size() { return _size; } // 表的长度 size_t TablesSize() { return _tables.size(); } // 桶的个数 size_t BucketNum() { size_t num = 0; for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) { ++num; } } return num; } size_t MaxBucketLenth() { size_t maxLen = 0; for (size_t i = 0; i < _tables.size(); ++i) { size_t len = 0; Node* cur = _tables[i]; while (cur) { ++len; cur = cur->_next; } if (len > maxLen) { maxLen = len; } } return maxLen; }
Size(): 这个函数返回哈希表中元素的总数量，即哈希表的大小。TablesSize(): 此函数返回哈希表内部存储桶的数量，也就是哈希表的实际大小。BucketNum(): 这个函数用于计算当前哈希表中非空桶的数量，也就是包含元素的桶的个数。MaxBucketLenth(): 此函数用于查找哈希表中最长桶的长度，也就是具有最多元素的桶中元素的数量。
修改后HashTable.h全部代码
#pragma once #include<iostream> #include<utility> #include<vector> #include<string> using namespace std; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t val = 0; for (auto ch : key) { val *= 131; val += ch; } return val; } }; namespace Bucket { template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) {} }; // 前置声明 template<class K, class T, class Hash, class KeyOfT> class HashTable; template<class K, class T, class Hash, class KeyOfT> struct __HashIterator { typedef HashNode<T> Node; typedef HashTable<K, T, Hash, KeyOfT> HT; typedef __HashIterator<K, T, Hash, KeyOfT> Self; Node* _node; HT* _pht; __HashIterator(Node* node, HT* pht) :_node(node) , _pht(pht) {} T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } Self& operator++() { if (_node->_next) { // 当前桶中迭代 _node = _node->_next; } else { // 找下一个桶 Hash hash; KeyOfT kot; size_t i = hash(kot(_node->_data)) % _pht->_tables.size(); ++i; for (; i < _pht->_tables.size(); ++i) { if (_pht->_tables[i]) { _node = _pht->_tables[i]; break; } } // 说明后面没有有数据的桶了 if (i == _pht->_tables.size()) { _node = nullptr; } } return *this; } bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } }; template<class K, class T, class Hash, class KeyOfT> class HashTable { typedef HashNode<T> Node; template<class K, class T, class Hash, class KeyOfT> friend struct __HashIterator; public: typedef __HashIterator<K, T, Hash, KeyOfT> iterator; iterator begin() { for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) { return iterator(_tables[i], this); } } return end(); } iterator end() { return iterator(nullptr, this); } ~HashTable() { for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } } inline size_t __stl_next_prime(size_t n) { static const size_t __stl_num_primes = 28; static const size_t __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; for (size_t i = 0; i < __stl_num_primes; ++i) { if (__stl_prime_list[i] > n) { return __stl_prime_list[i]; } } return -1; } pair<iterator, bool> Insert(const T& data) { Hash hash; KeyOfT kot; // 去重 iterator ret = Find(kot(data)); if (ret != end()) { return make_pair(ret, false); } // 负载因子到1就扩容 if (_size == _tables.size()) { vector<Node*> newTables; newTables.resize(__stl_next_prime(_tables.size()), nullptr); // 旧表中节点移动映射新表 for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hashi = hash(kot(cur->_data)) % newTables.size(); cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } size_t hashi = hash(kot(data)) % _tables.size(); // 头插 Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_size; return make_pair(iterator(newnode, this), true); } iterator Find(const K& key) { if (_tables.size() == 0) { return end(); } Hash hash; KeyOfT kot; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { return iterator(cur, this); } cur = cur->_next; } return end(); } bool Erase(const K& key) { if (_tables.size() == 0) { return false; } Hash hash; KeyOfT kot; size_t hashi = hash(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { // 1、头删 // 2、中间删 if (prev == nullptr) { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_size; return true; } prev = cur; cur = cur->_next; } return false; } size_t Size() { return _size; } // 表的长度 size_t TablesSize() { return _tables.size(); } // 桶的个数 size_t BucketNum() { size_t num = 0; for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) { ++num; } } return num; } size_t MaxBucketLenth() { size_t maxLen = 0; for (size_t i = 0; i < _tables.size(); ++i) { size_t len = 0; Node* cur = _tables[i]; while (cur) { ++len; cur = cur->_next; } if (len > maxLen) { maxLen = len; } } return maxLen; } private: vector<Node*> _tables; size_t _size = 0; // 存储有效数据个数 }; };
利用哈希表封装实现unordered_map
#pragma once #include "HashTable.h" namespace yulao { template<class K, class V, class Hash = HashFunc<K>> class unordered_map { struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: typedef typename Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } pair<iterator, bool> Insert(const pair<K, V>& kv) { return _ht.Insert(kv); } V& operator[](const K& key) { pair<iterator, bool> ret = _ht.Insert(make_pair(key, V())); return ret.first->second; } private: Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht; }; }
这里我们就将unordered_map的基础功能简易实现完毕啦！！！
