【C++】哈希的概念及STL中有关哈希容器的使用

06-25 1299阅读

【C++】哈希的概念及STL中有关哈希容器的使用

目录

  • 前言
  • 一、unordered系列关联式容器
    • 1.1 标准库中的unordered_set
      • 1.1.1 unordered_set的介绍
      • 1.1.2 unordered_set的常用接口说明
        • 1.1.2.1 unordered_set对象的常见构造
          • 1.1.2.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/)
          • 1.1.2.1.2 [有参构造函数（使用迭代器进行初始化构造）](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/)
          • 1.1.2.1.3 [拷贝构造函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/)
          • 1.1.2.2 unordered_set iterator 的使用
            • 1.1.2.2.1 [begin()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/begin/)
            • 1.1.2.2.2 [end()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/end/)
            • 1.1.2.3 unordered_set 对象的容量操作
              • 1.1.2.3.1 [size()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/size/)
              • 1.1.2.3.2 [empty()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/empty/)
              • 1.1.2.4 unordered_set 对象的增删查改及访问
                • 1.1.2.4.1 [insert()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/insert/)
                • 1.1.2.4.2 [erase()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/erase/)
                • 1.1.2.4.3 [swap()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/swap/)
                • 1.1.2.4.4 [clear()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/clear/)
                • 1.1.2.4.5 [find()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/find/)
                • 1.1.2.4.6 [count()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/count/)
                • 1.1.2.5 unordered_set的桶操作
                  • 1.1.2.5.1 [bucket_count()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/bucket_count/)
                  • 1.1.2.5.2 [bucket_size()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/bucket_size/)
                  • 1.1.2.5.3 [bucket()函数](https://legacy.cplusplus.com/reference/unordered_set/unordered_set/bucket/)
                  • 1.2 标准库中的unordered_map
                    • 1.2.1 unordered_map的介绍
                    • 1.2.2 unordered_map的常用接口说明
                      • 1.2.2.1 unordered_map对象的常见构造
                        • 1.2.2.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/unordered_map/)
                        • 1.2.2.1.2 [有参构造函数（使用迭代器进行初始化构造）](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/unordered_map/)
                        • 1.2.2.1.3 [拷贝构造函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/unordered_map/)
                        • 1.2.2.2 unordered_map iterator 的使用
                          • 1.1.2.2.1 [begin()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/begin/)
                          • 1.2.2.2.2 [end()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/end/)
                          • 1.2.2.3 unordered_set 对象的容量操作
                            • 1.2.2.3.1 [size()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/size/)
                            • 1.2.2.3.2 [empty()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/empty/)
                            • 1.2.2.4 unordered_map对象的增删查改及访问
                              • 1.2.2.4.1 [insert()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/insert/)
                              • 1.2.2.4.2 [operator[]](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/operator%5B%5D/)
                              • 1.2.2.4.3 [erase()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/erase/)
                              • 1.2.2.4.4 [swap()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/swap/)
                              • 1.2.2.4.5 [clear()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/clear/)
                              • 1.2.2.4.6 [find()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/find/)
                              • 1.2.2.4.7 [count()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/count/)
                              • 1.2.2.5 unordered_map的桶操作
                                • 1.2.2.5.1 [bucket_count()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/bucket_count/)
                                • 1.2.2.5.2 [bucket_size()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/bucket_size/)
                                • 1.2.2.5.3 [bucket()函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/bucket/)
                                • 二、底层结构
                                  • 2.1 哈希概念
                                  • 2.2 哈希冲突
                                  • 2.3 哈希函数
                                  • 2.4 哈希冲突解决
                                    • 2.4.1 闭散列
                                      • 2.4.1.1 线性探测
                                      • 2.4.1.2 二次探测
                                      • 2.4.2 开散列
                                        • 2.4.2.1.开散列概念
                                        • 2.4.2.2 开散列实现及测试
                                        • 2.4.2.3 开散列增容
                                        • 2.4.2.4 开散列的思考
                                        • 2.4.2.5 开散列与闭散列比较
                                        • 结尾

                                          前言

                                          本篇文章将讲述关于哈希的概念、哈希函数、哈希冲突和冲突后的解决方案，具体有闭散列和开散列，并且文章中还有对闭散列中的线性探测、开散列的模拟实现和测试。文章中还会对 unordered_set 和 unordered_map 中经常使用的函数进行对概念和特性的讲解，还会介绍它们函数的使用方法。

                                          由于不想文章篇幅太过长，有关于哈希表的实现、unordered_set 和 unordered_map封装实现、位图和布隆过滤器将会在后面的文章进行讲解。

                                          一、unordered系列关联式容器

                                          在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 l o g 2 N log_2N log2​N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍。

                                          1.1 标准库中的unordered_set

                                          1.1.1 unordered_set的介绍

                                          unordered_set的文档介绍

                                          1. 在内部,unordered_set没有对按照任何特定的顺序排序。
                                          2. 在unordered_set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。unordered_set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
                                          3. 在unordered_set中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
                                          4. 它的迭代器至少是前向迭代器。

                                          【C++】哈希的概念及STL中有关哈希容器的使用

                                          unordered_set的模板参数列表介绍

                                          Key：表示unordered_set中存储的元素类型，即键的类型，也是值的类型。

                                          Hash：表示用于计算元素哈希值的哈希函数对象类型，默认为std::hash，用于确定元素在unordered_set内部存储位置的函数。

                                          Pred：表示用于比较两个元素是否相等的函数对象类型，默认为std::equal_to，用于检查unordered_set中的元素是否相等。

                                          Alloc：表示用于分配内存的分配器类型，默认为std::allocator，用于分配和释放unordered_set内存空间（目前不需要掌握）。

                                          1.1.2 unordered_set的常用接口说明

                                          1.1.2.1 unordered_set对象的常见构造
                                          1.1.2.1.1 无参构造函数
                                          unordered_set ( size_type n = /* see below */,
                     const hasher& hf = hasher(),
                     const key_equal& eql = key_equal());

                                          #include
#include
using namespace std;
int main()
{
	unordered_set us;
	return 0;
}

                                          【C++】哈希的概念及STL中有关哈希容器的使用

                                          1.1.2.1.2 有参构造函数（使用迭代器进行初始化构造）
                                          template 
         unordered_set ( InputIterator first, InputIterator last,
              size_type n = /* see below */,
              const hasher& hf = hasher(),
              const key_equal& eql = key_equal());

                                          int main()
{
	string s("I Love You");
	unordered_set us(s.begin(), s.end());
	return 0;
}

                                          【C++】哈希的概念及STL中有关哈希容器的使用

                                          1.1.2.1.3 拷贝构造函数
                                          unordered_set ( const unordered_set& ust );

                                          int main()
{
	string s("I Love You");
	unordered_set us1(s.begin(), s.end());
	unordered_set us2(us1);
	return 0;
}

                                          【C++】哈希的概念及STL中有关哈希容器的使用

                                          1.1.2.2 unordered_set iterator 的使用

                                          由于 unordered_set 的迭代器是单向的，所以没有 rbegin() 和 rend() 函数 。

                                          1.1.2.2.1 begin()函数
                                          	  iterator begin() noexcept;
const_iterator begin() const noexcept;
获取第一个数据位置的iterator/const_iterator
                                          1.1.2.2.2 end()函数
                                          	  iterator end() noexcept;
const_iterator end() const noexcept;
获取最后一个数据的下一个位置的iterator/const_iterator

                                          int main()
{
	string s("I Love You");
	unordered_set us(s.begin(), s.end());
	unordered_set::iterator it = us.begin();
	while (it != us.end())
	{
		cout 
	string s("I Love You");
	unordered_set
	string s("I Love You");
	unordered_set
	unordered_set
		ret = us.insert(i % 10);
		cout 
		cout 
		cout 
		cout 
	unordered_set 8,4,0,1,5,7,2,3 };
	for (auto e : us)
	{
		cout 
		cout 
		cout 
		cout 
	unordered_set 1,3,5,7,9 };
	unordered_set 0,2,4,6,8 };
	cout 
		cout 
		cout 
		cout 
		cout 
	unordered_set 1,3,5,7,9 };
	cout 
	unordered_set 1,3,5,7,9 };
	unordered_set
	unordered_set 1,3,5,7,9 };
	size_t count = us.count(9);
	return 0;
}

	unordered_set
		us.insert(i + rand());
	}
	cout 
	unordered_map
	vector { "string","字符串" }, { "sort","排序" } });
	unordered_map
	vector { "string","字符串" }, { "sort","排序" } });
	unordered_map
	vector { "string","字符串" }, { "sort","排序" } });
	unordered_map
		cout 
	vector { "string","字符串" }, { "sort","排序" } });
	unordered_map
	vector { "string","字符串" }, { "sort","排序" } });
	unordered_map
	vector { "string","字符串" }, { "sort","排序" } });
	unordered_map
		cout 
		cout 
		cout 
	vector { "string","字符串" }, { "sort","排序" } });
	unordered_map
	unordered_map { "string","字符串" }, { "sort","排序" } });
	um.insert(make_pair("want", "想要"));
	um.insert(make_pair("love", "爱"));
	um.insert(make_pair("name", "名字"));
	for (auto pr : um)
	{
		cout 
		cout 
		cout 
		cout 
	unordered_map { "string","字符串" }, { "sort","排序" } });
	unordered_map { "want", "想要" }, { "love", "爱" } });
	cout 
		cout 
		cout 
		cout 
		cout 
	unordered_map { "string","字符串" }, { "sort","排序" } });
	cout 
	unordered_map { "string","字符串" }, { "sort","排序" } });
	unordered_map
	unordered_map { "string","字符串" }, { "sort","排序" } });
	cout 
	srand(time(0));
	const size_t N = 10000;
	unordered_map
		int num = rand();
		um.insert(make_pair(num, num));
	}
	cout EMPTY, EXIST, DELETE};

	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
// 特化
template
	size_t operator()(const string& s)
	{
		size_t sum = 0;
		for (size_t i = 0; i
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]