【C++ | 数据结构】从哈希的概念 到封装C++STL中的unordered系列容器

文章目录

  • 一、unordered系列容器的底层结构 - 哈希
    • 1. 哈希概念
    • 2. 哈希冲突
  • 二、解决哈希冲突
    • 方法一：合理设计哈希函数
      • 🚩哈希函数设计原则
      • 🚩常见哈希函数
    • 方法二：开闭散列
      • 🚩闭散列
        • 线性探测法（实现）
          • 1. 基本骨架
          • 2. 插入和扩容
          • 3. 查找
          • 4. 删除
          • 5. 仿函数HashFunc
        • 二次探测法（介绍）
      • 🚩开散列
        • 实现
  • 三、std::unordered_set和std::unordered_map
    • STL中的unordered_map介绍
    • STL中的unordered_set介绍
    • unordered_multimap
    • unordered_multiset
  • 四、用hashtable模拟实现unordered_set和unordered_map
    • hashtable实现
    • my_unordered_map实现
    • my_unordered_set实现
    • 其他STL模拟实现（持续更新）

一、unordered系列容器的底层结构 - 哈希

1. 哈希概念

  • 引入：
    顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( l o g 2 N log_2 N log2​N)，搜索的效率取决于搜索过程中元素的比较次数。

    尽管平衡二叉搜索树的查找方式已经很快了，但我们仍然认为该方法不够极致，理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构，通过某种函数(HashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

  • 插入元素
    根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
  • 搜索元素
    对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希方法（或散列法），哈希方法中使用的转换函数称为哈希函数（或散列函数），构造出来的结构称为哈希表(Hash Table)（或散列表）

[!Example] 例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity
（capacity为存储元素底层空间总的大小)
请添加图片描述
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？发现该位置已经有元素，这就是哈希冲突。

2. 哈希冲突

对于两个数据元素的关键字 k i k_i ki​和 k j k_j kj​ (i != j)，有 k i k_i ki​ != k j k_j kj​
但有：Hash( k i k_i ki​) == Hash( k j k_j kj​)
即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希冲突指的是：不同的输入数据经过哈希函数计算后，产生了相同的哈希值。当两个或多个不同的输入数据生成相同的哈希值时，就发生了哈希冲突。

由于哈希函数将无限的输入域映射到有限的输出域，所以在理论上，哈希冲突是不可避免的。好的哈希函数应该尽量减少哈希冲突的概率，使其发生的概率非常低。如果哈希冲突的概率过高，将会降低哈希函数的效率和可靠性，因为哈希冲突可能会导致数据的错误匹配或冲突。

二、解决哈希冲突

引起哈希冲突的一个原因可能是：哈希函数设计不够合理

方法一：合理设计哈希函数

🚩哈希函数设计原则

  • 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单

🚩常见哈希函数

  1. 直接定址法 (常用)
    取关键字的某个线性函数为散列地址： H a s h （ K e y ） = A ∗ K e y + B Hash（Key）= A*Key + B Hash（Key）=A∗Key+B
    优点：简单、均匀
    缺点：需要事先知道关键字的分布情况
    使用场景：适合查找比较小且连续的情况

    下面这道题是哈希直接定址法的典型例子：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

class Solution
{
public:
    int firstUniqChar(string s)
    {
        int countA[26]={0};
        for(auto ch:s)
        {
            countA[ch-'a']++;
        }
  
        for(int i=0;i<s.size();i++)
        {
            if(countA[s[i]-'a']==1)
            {
                return i;
            }
        }
        return -1;
    }
};

  1. 除留余数法 (常用)
    设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： H a s h ( k e y ) = k e y ( m o d ) p Hash(key) = key (mod) p Hash(key)=key(mod)p，(其中 mod 是取余操作)，将关键码转换成哈希地址

  2. 平方取中法 (了解)
    哈希函数： H a s h ( k e y ) = ( k e y 2 > > r ) Hash(key)=(key^2>>r) Hash(key)=(key2>>r) 按位与 (m−1)
    （其中 >> 是右移操作，r 是一个常数，通常选取为关键字位数的一半）
    假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
    再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
    平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

  3. 折叠法 (了解)
    折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
    折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

  4. 随机数法 (了解)
    选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
    通常应用于关键字长度不等时采用此法

  5. 数学分析法 (了解)
    设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：
    假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
    数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

方法二：开闭散列

🚩闭散列

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去；那如何寻找下一个空位置呢？有两种方法 – 线性探测法和二次探测法。

线性探测法（实现）

线性探测是从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

1. 基本骨架
#pragma once
#include <vector>

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 闭散列
namespace chen
{
	enum Status
	{
		EMPTY,
		EXIST,
		DELETE
	};
	
	template<class K,class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _s;       //状态
	};
	
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		
		// 插入
		bool Insert(const std::pair<K, V>& kv) { ... }
		
		// 查找
		HashData<K,V>* Find(const K& key) { ... }
		
		// 删除
		bool Erase(const K& key) { ... }
		
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._s == EXIST)
				{
					cout << "[" << i << "]->" << _tables[i]._kv.first 
						 << ":" << _tables[i]._kv.second << endl;
				}
				else if (_tables[i]._s == EMPTY)
				{
					printf("[%ud]->\n", i);
				}
				else
				{
					printf("[%ud]->D\n", i);
				}
			}
			cout << endl;
		}
		
	private:
		std::vector<HashData<K,V>> _tables;
		size_t _n = 0;    // 存储的关键字个数
	};

	void TestHT1()
	{
		chen::HashTable<int, int> ht;
		int a[] = { 42,45,345,4,37,45,23 };
		for (auto e : a)
		{
			ht.Insert(std::make_pair(e, e));
		}
		
		ht.Print();
		ht.Insert(std::make_pair(42, 42));
		ht.Print();
		
		ht.Erase(42);
		ht.Erase(45);
		
		ht.Print();
	}
	
	void TestHT2()
	{
		string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		//HashTable<string, int, HashFuncString> ht;
		HashTable<string, int, HashFunc<string>> ht;
		for (auto& e : arr)
		{
			//auto ret = ht.Find(e);
			HashData<string, int>* ret = ht.Find(e);
			if (ret)
			{
				ret->_kv.second++;
			}
			else
			{
				ht.Insert(make_pair(e, 1));
			}
		}
		
		ht.Print();
		
		ht.Insert(make_pair("apple", 1));
		ht.Insert(make_pair("sort", 1));
		
		ht.Insert(make_pair("abc", 1));
		ht.Insert(make_pair("acb", 1));
		ht.Insert(make_pair("aad", 1));
		
		ht.Print();
	}
}
2. 插入和扩容
bool Insert(const std::pair<K, V>& kv)
{
	if (Find(kv.first))
	{
		return false; // 如果关键字已存在，则返回false
	}
	
	// 负载因子_n/size == 0.7 就扩容
	if (_n * 10 / _tables.size() == 7)
	{
		size_t newSize = _tables.size() * 2;
		HashTable<K, V, Hash> newHT;
		newHT._tables.resize(newSize);
		// 遍历旧表，将数据插入新表
		for (size_t i = 0;i < _tables.size();i++)
		{
			if (_tables[i]._s == EXIST)
			{
				newHT.Insert(_tables[i]._kv);
			}
		}
		
		_tables.swap(newHT._tables); // 交换旧表和新表
	}
	
	Hash hf;
	// 线性探测，找到合适的位置插入数据
	size_t hashi = hf(kv.first) % _tables.size();
	while (_tables[hashi]._s == EXIST)
	{
		hashi++;
		hashi %= _tables.size();
	}
	
	_tables[hashi]._kv = kv; // 插入数据
	_tables[hashi]._s = EXIST; // 设置状态为存在
	++_n; // 更新关键字个数
	return true; // 插入成功，返回true
}
3. 查找
HashData<K,V>* Find(const K& key)
{
	Hash hf;
	size_t hashi = hf(key) % _tables.size();
	while (_tables[hashi]._s != EMPTY)
	{
		if (_tables[hashi]._s==EXIST
			&& _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi];
		}
		
		hashi++;
		hashi %= _tables.size();
	}
	
	return NULL;
}
4. 删除
bool Erase(const K& key)
{
	HashData<K, V>* ret = Find(key);
	if (ret)
	{
		ret->_s = DELETE;
		--_n;
		return true;
	}
	else
	{
		return false;
	}
}
5. 仿函数HashFunc
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 原始写法
struct HashFuncString
{
	size_t operator()(const string& key)
	{
		// BKDR方法
		size_t hash = 0;
		for (auto ch : key)
		{
			hash *= 31;
			hash += ch;
		}
		return hash;
	}
};

// 模板特化写法
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		// BKDR方法
		size_t hash = 0;
		for (auto ch : key)
		{
			hash *= 31;
			hash += ch;
		}
		return hash;
	}
};
二次探测法（介绍）

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为： H i H_i Hi​ = ( H 0 H_0 H0​ + i 2 i^2 i2 )% m, 或者： H i H_i Hi​ = ( H 0 H_0 H0​ - i 2 i^2 i2 )% m。其中：i =1,2,3…， H 0 H_0 H0​是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

🚩开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中，如图：
请添加图片描述

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
请添加图片描述

实现
namespace HashBucket
{
	template<class K, class V>
	struct HashNode
	{
		HashNode<K, V>* _next;
		pair<K, V> _kv;

		HashNode(const pair<K, V>& kv)
			:_next(nullptr)
			, _kv(kv)
		{}
	};

	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};

	// 特化
	template<>
	struct HashFunc<string>
	{
		// BKDR
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto ch : s)
			{
				hash += ch;
				hash *= 31;
			}

			return hash;
		}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		~HashTable()
		{
			for (auto& cur : _tables)
			{
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				cur = nullptr;
			}
		}

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;

			Hash hash;
			size_t hashi = hash(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)
		{
			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;

					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}


		size_t GetNextPrime(size_t prime)
		{
			// SGI
			static const int __stl_num_primes = 28;
			static const unsigned long __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
			};

			size_t i = 0;
			for (; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > prime)
					return __stl_prime_list[i];
			}

			return __stl_prime_list[i];
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;
			}

			Hash hash;

			// 负载因因子==1时扩容
			if (_n == _tables.size())
			{
				size_t newsize = GetNextPrime(_tables.size());
				vector<Node*> newtables(newsize, nullptr);
				for (auto& cur : _tables)
				{
					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = hash(cur->_kv.first) % newtables.size();

						// 头插到新表
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}
				}

				_tables.swap(newtables);
			}

			size_t hashi = hash(kv.first) % _tables.size();
			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			++_n;
			return true;
		}

		size_t MaxBucketSize()
		{
			size_t max = 0;
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				auto cur = _tables[i];
				size_t size = 0;
				while (cur)
				{
					++size;
					cur = cur->_next;
				}

				//printf("[%d]->%d\n", i, size);
				if (size > max)
				{
					max = size;
				}
			}

			return max;
		}
	private:
		vector<Node*> _tables; // 指针数组
		size_t _n = 0;         // 存储有效数据个数
	};

	void TestHT2()
	{
		string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		HashTable<string, int, HashFunc<string>> ht;
		for (auto& e : arr)
		{
			//auto ret = ht.Find(e);
			HashNode<string, int>* ret = ht.Find(e);
			if (ret)
			{
				ret->_kv.second++;
			}
			else
			{
				ht.Insert(make_pair(e, 1));
			}
		}
	}
}

三、std::unordered_set和std::unordered_map

STL中的unordered_map介绍

  1. unordered_map 是存储 <key, value> 键值对的关联式容器，其允许通过 key 快速的索引到与其对应的value – 计算出余数找到下标位置。

  2. 在 unordered_map 中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

  3. 在内部, unordered_map 没有对 <kye, value> 按照任何特定的顺序排序, 为了能在常数范围内找到 key 所对应的 value， unordered_map 将相同哈希值的键值对放在相同的桶中 – 开散列解决哈希冲突。

  4. unordered_map 容器通过 key 访问单个元素要比 map 快，但它在遍历元素子集的范围迭代方面效率较低。

  5. unordered_map 也重载了直接访问操作符 (operator[])，它允许使用 key 作为参数直接访问 value。

  6. unordered_map 的迭代器是一个单向迭代器 – 哈希桶的结构是单链表。

测试：

#include <iostream>
#include <unordered_map>

int main() 
{
    // (constructor) 构造函数
    std::unordered_map<int, std::string> myMap;

    // (insert) 插入元素
    myMap.insert({1, "One"});
    myMap.insert({2, "Two"});
    myMap.insert({3, "Three"});

    // (constructor) 通过范围构造函数
    std::unordered_map<int, std::string> rangeMap(myMap.begin(), myMap.end());

    // (constructor) 通过初始化列表构造函数
    std::unordered_map<int, std::string> initListMap = {{4, "Four"}, {5, "Five"}, {6, "Six"}};

    // (empty) 测试容器是否为空
    std::cout << "Is map empty? " << (myMap.empty() ? "Yes" : "No") << std::endl;

    // (size) 返回容器大小
    std::cout << "Size of map: " << myMap.size() << std::endl;

    // (find) 查找元素
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Element with key 2 found in map: " << it->second << std::endl;
    }

    // (count) 计算特定键的元素数量
    int count = myMap.count(3);
    std::cout << "Number of elements with key 3: " << count << std::endl;

    // (emplace) 构造并插入元素
    myMap.emplace(7, "Seven");

    // (erase) 删除元素
    myMap.erase(1);

    // (clear) 清空容器
    myMap.clear();

    // (hash_function) 获取哈希函数
    std::hash<int> hashFunction = myMap.hash_function();

    // (key_eq) 获取键的等价比较谓词
    auto keyEqual = myMap.key_eq();

    // (get_allocator) 获取分配器
    auto allocator = myMap.get_allocator();

    // (constructor) 拷贝构造函数
    std::unordered_map<int, std::string> copyMap(rangeMap);

    // (operator=) 赋值运算符
    std::unordered_map<int, std::string> assignedMap = initListMap;
    
    // (emplace_hint) 构造并插入元素带有提示位置
    auto hint = assignedMap.begin();
    assignedMap.emplace_hint(hint, 10, "Ten");

    // (swap) 交换内容
    myMap.swap(assignedMap);

    // (begin) 返回迭代器指向开头
    for (auto iter = myMap.begin(); iter != myMap.end(); ++iter) {
        std::cout << "Key: " << iter->first << ", Value: " << iter->second << std::endl;
    }

    // (cbegin) 返回 const 迭代器指向开头
    for (auto iter = myMap.cbegin(); iter != myMap.cend(); ++iter) {
        std::cout << "Key: " << iter->first << ", Value: " << iter->second << std::endl;
    }

    // (bucket_count) 返回桶的数量
    std::cout << "Bucket count: " << myMap.bucket_count() << std::endl;

    // (max_bucket_count) 返回最大桶的数量
    std::cout << "Max bucket count: " << myMap.max_bucket_count() << std::endl;

    // (bucket) 返回元素的桶号
    std::cout << "Bucket for key 2: " << myMap.bucket(2) << std::endl;

    // (bucket_size) 返回桶中元素的数量
    std::cout << "Bucket size for key 2: " << myMap.bucket_size(myMap.bucket(2)) << std::endl;

    // (load_factor) 返回当前负载因子
    std::cout << "Load factor: " << myMap.load_factor() << std::endl;

    // (max_load_factor) 获取或设置最大负载因子
    std::cout << "Max load factor: " << myMap.max_load_factor() << std::endl;
    myMap.max_load_factor(0.7);

    // (rehash) 设置桶的数量
    myMap.rehash(10);

    // (reserve) 请求容器容量变化
    myMap.reserve(20);

    return 0;
}

STL中的unordered_set介绍

unordered_set 和 unordered_map 的区别再于 unordered_set 是 K模型 的容器，而 unordered_map 是 KV模型 的容器，虽然二者底层都是开散列的哈希表，但是哈希表中每个节点的 data 的类型是不同的 – unordered_set 是单纯的 key，而 unordered_map 是 KV 构成的键值对，只是 哈希表 通过 KeyOfT 仿函数使得自己能够兼容 K模型 的 unordered_set 和 KV模型 的 unordered_map 而已。

unordered_set 和 unordered_map 的功能与要求基本一样：

  1. unordered_set 的查询效率为 O(1)；
  2. unordered_set 遍历得到序列的元素顺序是不确定的；
  3. unordered_set 的底层结构为开散列的哈希表；
  4. unordered_set 对 key 的要求是能够转换为整形。

与 unordered_map 为数不多的不同的地方在于，unordered_set 不需要修改 value，所以也就不支持 operator[] 函数；

测试：

int main() 
{
    // (constructor) 构造函数
    std::unordered_set<int> mySet;

    // (insert) 插入元素
    mySet.insert(1);
    mySet.insert(2);
    mySet.insert(3);

    // (constructor) 通过范围构造函数
    int arr[] = { 4, 5, 6 };
    std::unordered_set<int> rangeSet(arr, arr + 3);

    // (constructor) 通过初始化列表构造函数
    std::unordered_set<int> initListSet = { 7, 8, 9 };

    // (empty) 测试容器是否为空
    std::cout << "Is set empty? " << (mySet.empty() ? "Yes" : "No") << std::endl;

    // (size) 返回容器大小
    std::cout << "Size of set: " << mySet.size() << std::endl;

    // (find) 查找元素
    auto it = mySet.find(2);
    if (it != mySet.end()) {
        std::cout << "Element 2 found in set." << std::endl;
    }

    // (count) 计算特定键的元素数量
    int count = mySet.count(3);
    std::cout << "Number of elements with key 3: " << count << std::endl;

    // (emplace) 构造并插入元素
    mySet.emplace(4);

    // (erase) 删除元素
    mySet.erase(1);

    // (clear) 清空容器
    mySet.clear();

    // (hash_function) 获取哈希函数
    std::hash<int> hashFunction = mySet.hash_function();

    // (key_eq) 获取键的等价比较谓词
    auto keyEqual = mySet.key_eq();

    // (get_allocator) 获取分配器
    auto allocator = mySet.get_allocator();

    // (constructor) 拷贝构造函数
    std::unordered_set<int> copySet(rangeSet);

    // (operator=) 赋值运算符
    std::unordered_set<int> assignedSet = initListSet;

    // (emplace_hint) 构造并插入元素带有提示位置
    auto hint = assignedSet.begin();
    assignedSet.emplace_hint(hint, 10);

    // (swap) 交换内容
    mySet.swap(assignedSet);

    // (begin) 返回迭代器指向开头
    for (auto iter = mySet.begin(); iter != mySet.end(); ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    // (cbegin) 返回 const 迭代器指向开头
    for (auto iter = mySet.cbegin(); iter != mySet.cend(); ++iter) {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;

    // (bucket_count) 返回桶的数量
    std::cout << "Bucket count: " << mySet.bucket_count() << std::endl;

    // (max_bucket_count) 返回最大桶的数量
    std::cout << "Max bucket count: " << mySet.max_bucket_count() << std::endl;

    // (bucket) 返回元素的桶号
    std::cout << "Bucket for key 2: " << mySet.bucket(2) << std::endl;

    // (bucket_size) 返回桶中元素的数量
    std::cout << "Bucket size for key 2: " << mySet.bucket_size(mySet.bucket(2)) << std::endl;

    // (load_factor) 返回当前负载因子
    std::cout << "Load factor: " << mySet.load_factor() << std::endl;

    // (max_load_factor) 获取或设置最大负载因子
    std::cout << "Max load factor: " << mySet.max_load_factor() << std::endl;
    mySet.max_load_factor(0.7);

    // (rehash) 设置桶的数量
    mySet.rehash(10);

    // (reserve) 请求容器容量变化
    mySet.reserve(20);

    return 0;
}

unordered_multimap

和 multimap 和 map 的区别一样，unordered_multimap 和 unordered_map 的区别在于 unordered_multimap 中允许出现重复元素，所以 unordered_multimap 中 count 用来计算 哈希表 中同一 key 值的元素的数量比较方便，但 unordered_multimap 也因此不再支持 operator[] 运算符重载，其他的地方都差不多，对细节有疑惑的建议查阅官方文档 unordered_multimap - C++ Reference (cplusplus.com)

unordered_multiset

unordered_multiset 也一样，与 unordered_set 不同的地方在于其允许出现重复元素：unordered_set - C++ Reference (cplusplus.com)

四、用hashtable模拟实现unordered_set和unordered_map

hashtable实现

为了使哈希表能够同时封装 KV模型的 unordered_map 和 K模型的 unordered_set，哈希表不能将节点的数据类型直接定义为 pair<K, V>，而是需要通过参数 T 来确定

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// HashFunc的模板特化
// 原因：不存在string类到size_t的显示类型转换
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

namespace hash_bucket
{
	// 哈希表节点
	template<class T>
	struct HashNode
	{
		HashNode<T>* _next;
		T _data;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	// 这里前置声明HashTable是因为在下面迭代器的定义里要用到HashTable这个类名（相互引用）
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	// K     ：Key的类型
	// T     ：T的类型（set就放key的类型，map就放std::pair(key,value)）迭代器封装的就是T类型的对象
	// Ref   ：T的引用类型
	// Ptr   ：T的指针类型
	// KeyOfT：用来取出T中的key的仿函数类型，因为T不一定是纯key，如果存放pair，要从中取出key
	// Hash  ：用来把key转换成size_t的仿函数类，就是算key的哈希值
	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

	public:
		Node* _node;                               // 哈希表节点指针
		size_t _hashi;                             // 哈希桶编号
		const HashTable<K, T, KeyOfT, Hash>* _pht; // 哈希表指针 为什么是const？？？

	public:
		__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
			:_node(node)
			, _pht(pht)
			, _hashi(hashi)
		{}

		__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
			:_node(node)
			, _pht(pht)
			, _hashi(hashi)
		{}

		Self& operator++()
		{
			if (_node->_next != nullptr)
			{
				// 当前桶还有节点，走到下一个节点
				_node = _node->_next;
			}
			else
			{
				// 当前桶已经走完了，从下一个桶开始找
				++_hashi;
				while (_hashi < _pht->_tables.size())
				{
					if (_pht->_tables[_hashi])
					{
						_node = _pht->_tables[_hashi];
						break;
					}

					++_hashi;
				}

				if (_hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
			}

			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node; // 迭代器不等，就是节点指针不等
		}
	};

	// unordered_set -> Hashtable<K, K>
	// unordered_map -> Hashtable<K, pair<K, V>>
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
	public:
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;

		// 友元类声明
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct __HTIterator;

	public:
		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i], this, i);
				}
			}
			return end(); // 遍历完发现没有元素，返回一个尾后迭代器
		}

		iterator end()
		{
			// 尾后迭代器，是一个无效迭代器
			return iterator(nullptr, this, -1);
		}

		const_iterator begin() const
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return const_iterator(_tables[i], this, i);
				}
			}

			return end();
		}

		const_iterator end() const
		{
			// this的类型：const HashTable<K, T, KeyOfT, Hash>*
			return const_iterator(nullptr, this, -1);
		}

		HashTable()
		{
			_tables.resize(10);
		}

		~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;
			}
		}

		// bool用来标记是否开辟新节点
		// 待插入数据已存在：false
		// 待插入数据不存在：ture
		std::pair<iterator, bool> Insert(const T& data)
		{
			Hash hf;
			KeyOfT kot;

			iterator it = Find(kot(data));
			if (it != end())
			{
				return std::make_pair(it, false);
			}

			// 负载因子最大到1 ,到1扩容
			if (_n == _tables.size())
			{
				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				// 遍历旧表
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next; // 旧的哈希桶（链表）的头节点的下一个先存着

						// 把旧的节点映射到新表
						size_t hashi = hf(kot(cur->_data)) % newTables.size();
						cur->_next = newTables[i];
						newTables[hashi] = cur;

						cur = next; // 迭代
					}

					_tables[i] = nullptr;
				}

				_tables.swap(newTables);
			}

			size_t hashi = hf(kot(data)) % _tables.size();
			Node* newnode = new Node(data);

			// 头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return std::make_pair(iterator(newnode, this, hashi), true);
		}

		iterator Find(const K& key)
		{
			Hash hf;
			KeyOfT kot;

			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur, this, hashi);
				}

				cur = cur->_next;
			}

			return end();
		}

		bool Erase(const K& key)
		{
			Hash hf;
			KeyOfT kot;

			size_t hashi = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;

					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

		void Some()
		{
			size_t bucketCount = 0;      // 哈希桶数量
			size_t maxBucketLen = 0;     // 最大哈希桶（链表）长度
			size_t sum = 0;              // 总节点数
			double averageBucketLen = 0; // 平均桶长度

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					++bucketCount;
				}

				size_t bucketLen = 0;
				while (cur)
				{
					++bucketLen;
					cur = cur->_next;
				}

				sum += bucketLen;

				if (bucketLen > maxBucketLen)
				{
					maxBucketLen = bucketLen;
				}
			}

			averageBucketLen = (double)sum / (double)bucketCount;

			printf("all bucketSize:%d\n", _tables.size());
			printf("bucketSize:%d\n", bucketCount);
			printf("maxBucketLen:%d\n", maxBucketLen);
			printf("averageBucketLen:%lf\n\n", averageBucketLen);
		}

	private:
		std::vector<Node*> _tables;
		size_t _n = 0;
	};

my_unordered_map实现

namespace chen
{
	// 外层是<key,value>
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
		// 提取T中的key的仿函数类
		struct MapKeyOfT
		{
			const K& operator()(const std::pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		// 去HashTable里面拿HashTable的迭代器 作unordered_map的迭代器
		// 这里迭代器里封装的是pair<const K, V>
		typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
		typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}

		V& operator[](const K& key)
		{
			std::pair<iterator, bool> ret = _ht.Insert(std::make_pair(key, V()));
			return ret.first->second;
		}

		const V& operator[](const K& key) const
		{
			std::pair<iterator, bool> ret = _ht.Insert(std::make_pair(key, V()));
			return ret.first->second;
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

	private:
		hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash> _ht;
	};
}

my_unordered_set实现

namespace chen
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
		typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;

		const_iterator begin() const
		{
			return _ht.begin();
		}

		const_iterator end() const
		{
			return _ht.end();
		}

		std::pair<const_iterator, bool> insert(const K& key)
		{
			auto ret = _ht.Insert(key);
			return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
	private:
		hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
	};
}

其他STL模拟实现（持续更新）

https://gitee.com/chenzhuowen4384/My_STL

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/339023.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux操作系统——理解文件系统

Linux操作系统——理解文件系统

预备知识 到目前为止&#xff0c;我们所学习到的关于文件的操作&#xff0c;全部都是基于文件被打开&#xff0c;被访问&#xff0c;访问期间比较重要的有重定向&#xff0c;缓冲区&#xff0c;一切皆文件&#xff0c;当我们访问完毕的时候需要将文件关闭&#xff0c;关闭时那…
阅读更多...
Python 生成 图片网页列表 显示路径和建立时间 笔记

Python 生成 图片网页列表 显示路径和建立时间 笔记

Python 一键 生成 图片网页列表 显示路径和建立时间 &#xff08;方便查看复制路径、重复一键生成&#xff09; 支持格式&#xff1a;jpg \png\ svg\ webp 图片网页列表 图示&#xff1a; 参考代码&#xff1a; # -*- coding: utf-8 -*- import os import datetime# 指定图片…
阅读更多...
八股文学习日常第一期（20240121）

八股文学习日常第一期（20240121）

零、前言 1、目的 帮助掌握面试题&#xff0c;就八股文相关内容展开进行学习和整理&#xff0c;也方便之后的复习和巩固。 2、八股文内容来源 ①https://blog.csdn.net/w20001118/article/details/125724647 一、具体内容分析 1、类的完整书写方式 1.1、类 [Access Mod…
阅读更多...
Stream toList不能滥用以及与collect(Collectors.toList())的区别

Stream toList不能滥用以及与collect(Collectors.toList())的区别

Stream toList()返回的是只读List原则上不可修改&#xff0c;collect(Collectors.toList())默认返回的是ArrayList,可以增删改查 1. 背景 在公司看到开发环境突然发现了UnsupportedOperationException 报错&#xff0c;想到了不是自己throw的应该就是操作collection不当。 发…
阅读更多...
2.上传图片到Minio服务中

2.上传图片到Minio服务中

上传图片 界面原型 第一步: 用户在课程信息编辑界面可以上传课程图片或者修改上传的课程图片 第二步: 请求媒资管理服务将课程图片上传至分布式文件系统同时在媒资管理数据库保存文件信息,上传成功后返回图片在MinIO中的地址 第三步: 请求内容管理服务保存课程信息含课程封…
阅读更多...
【网站项目】基于SSM的274办公自动化管理系统

【网站项目】基于SSM的274办公自动化管理系统

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…
阅读更多...
【Linux系统编程】进程优先级

【Linux系统编程】进程优先级

文章目录 1. 优先级的基本概念2. 为什么存在优先级3. 查看系统进程4. PRI and NI5. top命令修改已存在进程的nice值6. 其他概念 1. 优先级的基本概念 本篇文章讲解进程优先级&#xff0c;首先我们来了解一下进程优先级的概念&#xff1a; cpu资源分配的先后顺序&#xff0c;就…
阅读更多...
burp靶场--访问控制【越权】

burp靶场--访问控制【越权】

【Burp系列】超全越权漏洞实验总结 https://portswigger.net/web-security/access-control/lab-unprotected-admin-functionality 1. 访问控制【越权】 https://portswigger.net/web-security/access-control#what-is-access-control ### 什么是访问控制&#xff1a; 访问控…
阅读更多...
php基础学习之常量

php基础学习之常量

php常量的基本概念 常量是在程序运行中的一种不可改变的量&#xff08;数据&#xff09;&#xff0c;常量一旦定义&#xff0c;通常不可改变&#xff08;用户级别&#xff09;。 php常量的定义形式 使用define函数&#xff1a;define("常量名字", 常量值);使用cons…
阅读更多...
Mac NTFS 磁盘读写工具选哪个好？Tuxera 还是 Paragon？

Mac NTFS 磁盘读写工具选哪个好？Tuxera 还是 Paragon？

在使用 Mac 电脑时&#xff0c;我们经常需要读写 NTFS 格式的硬盘或 U 盘。然而&#xff0c;由于 Mac 系统不支持 NTFS 格式的读写&#xff0c;因此我们需要借助第三方工具来实现这个功能。而在市场上&#xff0c;Tuxera 和 Paragon 是两款备受推崇的 Mac NTFS 磁盘读写工具。那…
阅读更多...
GSP专版软件系统(医疗器械进销存)

GSP专版软件系统(医疗器械进销存)

产品概述 软件完全符合药监局GSP认证要求&#xff0c;可订制其它平台的数据对接; 业务流程清晰&#xff0c;操作简单合理&#xff0c;软件速度非常快; 完善的序列号(UDI)管理,并与整个系统融合在一起; 财务账和业务账完美结合; 可自定义的界面、布局管理;灵活的打印样式设计; 可…
阅读更多...
有关软件测试的，任何时间都可以，软件测试主要服务项目：测试用例 报告 计划

有关软件测试的，任何时间都可以，软件测试主要服务项目：测试用例 报告 计划

有关软件测试的&#xff0c;任何时间都可以&#xff0c;软件测试主要服务项目&#xff1a; 1. 测试用例 2. 测试报告 3. 测试计划 4. 白盒测试 5. 黑盒测试 6. 接口测试 7.自动…
阅读更多...
Vuex的基础使用

Vuex的基础使用

在使用之前要先了解Vuex的组成结构&#xff0c;跟对应的使用关系。 在上图的结构图中可以看到四个组成部分&#xff0c;首先是Components&#xff08;组件&#xff09;、Actions&#xff08;行动&#xff09;、Mutations&#xff08;变化&#xff09;、state&#xff08;状态/数…
阅读更多...
Mysql运维篇（三） MySQL数据库分库分表方案

Mysql运维篇（三） MySQL数据库分库分表方案

一路走来&#xff0c;所有遇到的人&#xff0c;帮助过我的、伤害过我的都是朋友&#xff0c;没有一个是敌人&#xff0c;如有侵权请留言&#xff0c;我及时删除。 一、前言 关系型数据库本身比较容易成为系统瓶颈&#xff0c;单机存储容量、连接数、处理能力都有限。当单表的数…
阅读更多...
【MySQL进阶】SQL优化

【MySQL进阶】SQL优化

文章目录 SQL 优化主键优化数据组织方式页分裂页合并主键设计原则 insert优化order by优化group by优化limit优化count优化 SQL 优化 主键优化 数据组织方式 在InnoDB存储引擎中&#xff0c;表数据都是根据主键顺序组织存放的&#xff0c;这种存储方式的表称为索引组织表 在In…
阅读更多...
【5G 接口协议】N2接口协议NGAP（NG Application Protocol）介绍

【5G 接口协议】N2接口协议NGAP（NG Application Protocol）介绍

博主未授权任何人或组织机构转载博主任何原创文章&#xff0c;感谢各位对原创的支持&#xff01; 博主链接 本人就职于国际知名终端厂商&#xff0c;负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作&#xff0c;目前牵头6G算力网络技术标准研究。 博客…
阅读更多...
PIG框架学习3——Redisson 实现业务接口幂等

PIG框架学习3——Redisson 实现业务接口幂等

零、前言 ​ 业务接口幂等问题是在开发中遇到的&#xff0c;如果对业务接口代码不进行幂等控制&#xff0c;并且在前端没有对请求进行限制的情况下&#xff0c;可能会出现多次对接口调用&#xff0c;导致错误异常的发生。就上述情况&#xff0c;对PIGX自带的业务接口幂等实现进…
阅读更多...
无法找到mfc100.dll的解决方法分享，如何快速修复mfc100.dll文件

无法找到mfc100.dll的解决方法分享，如何快速修复mfc100.dll文件

在日常使用电脑时&#xff0c;我们可能会碰到一些系统错误提示&#xff0c;比如“无法找到mfc100.dll”的信息。这种错误通常会阻碍代码的执行或某些应用程序的启动。为了帮助您解决这一问题&#xff0c;本文将深入探讨其成因&#xff0c;并提供几种不同的mfc100.dll解决方案。…
阅读更多...
lv14 内核定时器 11

lv14 内核定时器 11

一、时钟中断 硬件有一个时钟装置&#xff0c;该装置每隔一定时间发出一个时钟中断&#xff08;称为一次时钟嘀嗒-tick&#xff09;&#xff0c;对应的中断处理程序就将全局变量jiffies_64加1 jiffies_64 是一个全局64位整型, jiffies全局变量为其低32位的全局变量&#xff0…
阅读更多...
三.Winform使用Webview2加载本地HTML页面

三.Winform使用Webview2加载本地HTML页面

Winform使用Webview2加载本地HTML页面 往期目录创建Demo2界面创建HTML页面在Demo2窗体上添加WebView2和按钮加载HTML查看效果 往期目录 往期相关文章目录 专栏目录 创建Demo2界面 经过前面两小节 一.Winform使用Webview2(Edge浏览器核心) 创建demo(Demo1)实现回车导航到指定…
阅读更多...
最新文章

Copyright @ 2022~2023