【C++】哈希的概念及STL中有关哈希容器的使用
是阿建吖! 2024-07-30 12:05:09 阅读 90
目录
前言一、unordered系列关联式容器1.1 标准库中的unordered_set1.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_map1.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
log2N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍。
1.1 标准库中的unordered_set
1.1.1 unordered_set的介绍
unordered_set的文档介绍
在内部,unordered_set没有对按照任何特定的顺序排序。在unordered_set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。unordered_set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。在unordered_set中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。它的迭代器至少是前向迭代器。
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 无参构造函数
<code>unordered_set ( size_type n = /* see below */,
const hasher& hf = hasher(),
const key_equal& eql = key_equal());
#include<iostream>
#include<unordered_set>
using namespace std;
int main()
{
unordered_set<int> us;
return 0;
}
1.1.2.1.2 有参构造函数（使用迭代器进行初始化构造）
<code>template <class InputIterator>
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<int> us(s.begin(), s.end());
return 0;
}
1.1.2.1.3 拷贝构造函数
<code>unordered_set ( const unordered_set& ust );
int main()
{
string s("I Love You");
unordered_set<int> us1(s.begin(), s.end());
unordered_set<int> us2(us1);
return 0;
}
1.1.2.2 unordered_set iterator 的使用
由于 unordered_set 的迭代器是单向的，所以没有 <code>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<int> us(s.begin(), s.end());
unordered_set<int>::iterator it = us.begin();
while (it != us.end())
{
cout << *it << ' ';
++it;
}
return 0;
}
1.1.2.3 unordered_set 对象的容量操作
1.1.2.3.1 size()函数
<code>size_type size() const noexcept;获取数据个数
int main()
{
string s("I Love You");
unordered_set<int> us(s.begin(), s.end());
cout << us.size() << endl;
return 0;
}
1.1.2.3.2 empty()函数
<code>bool empty() const noexcept;判断是否为空
int main()
{
string s("I Love You");
unordered_set<int> us1;
unordered_set<int> us2(s.begin(), s.end());
cout << "us1 empty:" << us1.empty() << endl;
cout << "us2 empty:" << us2.empty() << endl;
return 0;
}
1.1.2.4 unordered_set 对象的增删查改及访问
1.1.2.4.1 insert()函数
<code>pair<iterator,bool> insert ( const value_type& val );
在unordered_set 中插入一个元素val：
若unordered_set 中有这个元素，插入失败,则返回一个pair对象
pair.first=原来val元素位置的迭代器,pair.second = false
若unordered_set 中没有这个元素，插入成功,则返回一个pair对象
pair.first=新插入val元素位置的迭代器,pair.second = true
iterator insert ( const_iterator hint, const value_type& val );
从hint位置开始查找插入位置，
若unordered_set 中有这个元素，并返回原来val位置的迭代器
若unordered_set 中没有这个元素，返回插入wal元素位置的迭代器
template <class InputIterator>
void insert ( InputIterator first, InputIterator last );
插入一段迭代器区间的元素
int main()
{
unordered_set<int> us;
string ss("I Love Y");
// pair<iterator, bool> insert(const value_type & val);
pair<unordered_set<int>::iterator, bool> ret;
for (int i = 0; i < 14; i += 2)
{
ret = us.insert(i % 10);
cout << "插入元素：" << *ret.first
<< " 是否成功：" << ret.second << endl;
}
for (auto e : us)
{
cout << e << ' ';
}
cout << endl;
// iterator insert ( const_iterator hint, const value_type& val );
us.insert(us.begin(), 520);
for (auto e : us)
{
cout << e << ' ';
}
cout << endl;
// template <class InputIterator>
//void insert(InputIterator first, InputIterator last);
us.insert(ss.begin(), ss.end());
for (auto e : us)
{
cout << e << ' ';
}
cout << endl;
return 0;
}
1.1.2.4.2 erase()函数
<code>iterator erase ( const_iterator position );
删除position位置的元素
size_type erase ( const key_type& k );
删除元素k并返回删除k的个数
iterator erase ( const_iterator first, const_iterator last );
删除一段迭代器区间内的元素
int main()
{
unordered_set<int> us{ 8,4,0,1,5,7,2,3 };
for (auto e : us)
{
cout << e << ' ';
}
cout << endl;
unordered_set<int>::iterator it = us.begin();
// iterator erase ( const_iterator position );
us.erase(it);
for (auto e : us)
{
cout << e << ' ';
}
cout << endl;
// 删除元素val并返回val的个数
// size_type erase(const key_type & k);
cout << "erase number:" << us.erase(5) << endl;;
for (auto e : us)
{
cout << e << ' ';
}
cout << endl;
// 删除一段迭代器区间内的元素
// iterator erase ( const_iterator first, const_iterator last );
us.erase(++us.begin(), --us.end());
for (auto e : us)
{
cout << e << ' ';
}
cout << endl;
return 0;
}
1.1.2.4.3 swap()函数
<code>void swap ( unordered_set& ust );
交换两个unordered_set的数据空间
int main()
{
unordered_set<int> us1{ 1,3,5,7,9 };
unordered_set<int> us2{ 0,2,4,6,8 };
cout << "us1：";
for (auto e : us1)
{
cout << e << ' ';
}
cout << endl;
cout << "us2：";
for (auto e : us2)
{
cout << e << ' ';
}
cout << endl;
us1.swap(us2);
cout << "us1：";
for (auto e : us1)
{
cout << e << ' ';
}
cout << endl;
cout << "us2：";
for (auto e : us2)
{
cout << e << ' ';
}
cout << endl;
return 0;
}
1.1.2.4.4 clear()函数
<code>void clear() noexcept;
清除unordered_set中的有效数据
int main()
{
unordered_set<int> us{ 1,3,5,7,9 };
cout << "us size:" << us.size() << endl;
us.clear();
cout << "us size:" << us.size() << endl;
return 0;
}
1.1.2.4.5 find()函数
<code> iterator find ( const key_type& k );
const_iterator find ( const key_type& k ) const;
返回unordered_set中为k元素位置的迭代器
int main()
{
unordered_set<int> us{ 1,3,5,7,9 };
unordered_set<int>::iterator ret = us.find(5);
cout << *ret << endl;
return 0;
}
1.1.2.4.6 count()函数
<code>size_type count ( const key_type& k ) const;
返回unordered_set中为k元素的个数
由于unordered_set并不允许相同的元素存在
所以unordered_set中所有元素的个数都是1
int main()
{
unordered_set<int> us{ 1,3,5,7,9 };
size_t count = us.count(9);
return 0;
}
1.1.2.5 unordered_set的桶操作
1.1.2.5.1 bucket_count()函数
<code>size_type bucket_count() const noexcept;
返回哈希桶中桶的总个数
1.1.2.5.2 bucket_size()函数
size_type bucket_size ( size_type n ) const;
返回n号桶中有效元素的总个数
1.1.2.5.3 bucket()函数
size_type bucket ( const key_type& k ) const;
返回元素key所在的桶号
int main()
{
unordered_set<int> us;
for (int i = 0; i < 1000; i++)
{
us.insert(i + rand());
}
cout << "bucket_count:" << us.bucket_count() << endl;
cout << "bucket_size:" << us.bucket_size(20) << endl;
cout << "bucket:" << us.bucket(*us.begin()) << endl;
return 0;
}
1.2 标准库中的unordered_map
1.2.1 unordered_map的介绍
unordered_map的文档介绍
unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。它的迭代器至少是前向迭代器。
unordered_map的模板参数列表介绍
Key：表示unordered_map中键的类型，即键的类型。
T：表示unordered_map中值的类型，即映射到键的值的类型。
Hash：表示用于计算键的哈希值的哈希函数对象类型，默认为std::hash，用于确定键在unordered_map内部存储位置的函数。
Pred：表示用于比较两个键是否相等的函数对象类型，默认为std::equal_to，用于检查unordered_map中的键是否相等。
Alloc：表示用于分配内存的分配器类型，默认为std::allocator<std::pair<const Key, T>>，用于分配和释放unordered_map内存空间。（目前不需要掌握）
1.2.2 unordered_map的常用接口说明
1.2.2.1 unordered_map对象的常见构造
1.2.2.1.1 无参构造函数
<code>unordered_map ( size_type n = /* see below */,
const hasher& hf = hasher(),
const key_equal& eql = key_equal());
#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
unordered_map<int,int> um;
return 0;
}
1.2.2.1.2 有参构造函数（使用迭代器进行初始化构造）
<code>template <class InputIterator>
unordered_map ( InputIterator first, InputIterator last,
size_type n = /* see below */,
const hasher& hf = hasher(),
const key_equal& eql = key_equal());
unordered_map 是 C++ STL 中的一种无序关联容器，它通过哈希表实现，可以提供快速的插入、查找和删除操作。
当你尝试使用其他容器的迭代器构造 unordered_map 时，可能会遇到编译错误，因为 unordered_map 的构造函数通常不接受其他容器类型的迭代器。
如果正在使用其他容器（如 vector、list 等），确保使用正确的迭代器类型进行构造。unordered_map 构造函数接受的是一对指向键值对的迭代器，其中每个键值对是一个 pair<const Key, Value> 类型的对象。
int main()
{
vector<pair<string, string>> v({ { "string","字符串" }, { "sort","排序" } });
unordered_map<string, string> um1(v.begin(),v.end());
unordered_map<string, string> um2(um1.begin(), um1.end());
return 0;
}
1.2.2.1.3 拷贝构造函数
<code>unordered_map ( const unordered_map& ump );
int main()
{
vector<pair<string, string>> v({ { "string","字符串" }, { "sort","排序" } });
unordered_map<string, string> um1(v.begin(), v.end());
unordered_map<string, string> um2(um1);
return 0;
}
1.2.2.2 unordered_map iterator 的使用
由于 unordered_map 的迭代器是单向的，所以没有 <code>rbegin() 和 rend() 函数 。
1.1.2.2.1 begin()函数
iterator begin() noexcept;
const_iterator begin() const noexcept;
获取第一个数据位置的iterator/const_iterator
1.2.2.2.2 end()函数
iterator end() noexcept;
const_iterator end() const noexcept;
获取最后一个数据的下一个位置的iterator/const_iterator
int main()
{
vector<pair<string, string>> v({ { "string","字符串" }, { "sort","排序" } });
unordered_map<string, string> um(v.begin(), v.end());
unordered_map<string, string>::iterator it = um.begin();
while (it != um.end())
{
cout << it->first << ' ' << it->second << endl;
++it;
}
return 0;
}
1.2.2.3 unordered_set 对象的容量操作
1.2.2.3.1 size()函数
<code>size_type size() const noexcept;获取数据个数
int main()
{
vector<pair<string, string>> v({ { "string","字符串" }, { "sort","排序" } });
unordered_map<string, string> um(v.begin(), v.end());
cout << um.size() << endl;
return 0;
}
1.2.2.3.2 empty()函数
<code>bool empty() const noexcept;判断是否为空
int main()
{
vector<pair<string, string>> v({ { "string","字符串" }, { "sort","排序" } });
unordered_map<string, string> um1;
unordered_map<string, string> um2(v.begin(), v.end());
cout << "um1 empty:" << um1.empty() << endl;
cout << "um2 empty:" << um2.empty() << endl;
return 0;
}
1.2.2.4 unordered_map对象的增删查改及访问
1.2.2.4.1 insert()函数
<code>pair<iterator,bool> insert ( const value_type& val );
在unordered_map中插入键值对val：
若unordered_map中有这个键值对，插入失败,则返回一个pair对象
pair.first=原来val位置的迭代器,pair.second = false
若unordered_map中没有这个键值对，插入成功,则返回一个pair对象
pair.first=新插入val位置的迭代器,pair.second = true
iterator insert ( const_iterator hint, const value_type& val );
从hint位置开始查找插入位置，
若unordered_map中有这个键值对，并返回原来val位置的迭代器
若unordered_map中没有这个键值对，返回插入val位置的迭代器
template <class InputIterator>
void insert ( InputIterator first, InputIterator last );
插入一段迭代器区间的元素
int main()
{
vector<pair<string, string>> v({ { "string","字符串" }, { "sort","排序" } });
unordered_map<string, string> um1;
unordered_map<string, string> um2(v.begin(), v.end());
// pair<iterator, bool> insert(const value_type & val);
pair<unordered_map<string, string>::iterator,bool> ret1 =
um1.insert(make_pair("empty", "空"));
cout << ret1.first->first << ' ' << ret1.first->second
<< ' ' << "插入是否成功：" << ret1.second << endl;
for (auto um : um1)
{
cout << um.first << um.second << endl;
}
cout << endl;
// iterator insert(const_iterator hint, const value_type & val);
unordered_map<string, string>::iterator ret2 =
um1.insert(um1.begin(), make_pair("want", "想要"));
cout << ret2->first << ' ' << ret2->second << endl;
for (auto um : um1)
{
cout << um.first << um.second << endl;
}
cout << endl;
// template <class InputIterator>
//void insert(InputIterator first, InputIterator last);
um1.insert(um2.begin(), um2.end());
for (auto um : um1)
{
cout << um.first << um.second << endl;
}
cout << endl;
return 0;
}
1.2.2.4.2 operator[]
<code>mapped_type& operator[] ( const key_type& k );
mapped_type& operator[] ( key_type&& k );
int main()
{
vector<pair<string, string>> v({ { "string","字符串" }, { "sort","排序" } });
unordered_map<string, string> um(v.begin(), v.end());
// 若unordered_map中有这个元素，那么就返回key对应value的引用
cout << "operator[]:" << um["string"] << endl;
// 若map中没有这个元素，那么map中将会插入这个元素
// 使用默认构造初始化value，并返回
cout << "operator[]:" << um["want"] << endl;
return 0;
}
1.2.2.4.3 erase()函数
<code>iterator erase ( const_iterator position );
删除position位置的元素
size_type erase ( const key_type& k );
删除元素k并返回k的个数
iterator erase ( const_iterator first, const_iterator last );
删除一段迭代器区间内的元素
int main()
{
unordered_map<string, string> um({ { "string","字符串" }, { "sort","排序" } });
um.insert(make_pair("want", "想要"));
um.insert(make_pair("love", "爱"));
um.insert(make_pair("name", "名字"));
for (auto pr : um)
{
cout << pr.first << ' ' << pr.second << endl;
}
cout << endl;
// iterator erase(const_iterator position);
um.erase(++um.begin());
for (auto pr : um)
{
cout << pr.first << ' ' << pr.second << endl;
}
cout << endl;
// size_type erase(const key_type & k);
cout << "erase number:" << um.erase("string") << endl;
for (auto pr : um)
{
cout << pr.first << ' ' << pr.second << endl;
}
cout << endl;
um.erase(++um.begin(), --um.end());
for (auto pr : um)
{
cout << pr.first << ' ' << pr.second << endl;
}
cout << endl;
return 0;
}
1.2.2.4.4 swap()函数
<code>void swap ( unordered_map& ump );
交换两个unordered_map的数据空间
int main()
{
unordered_map<string, string> um1({ { "string","字符串" }, { "sort","排序" } });
unordered_map<string, string> um2({ { "want", "想要" }, { "love", "爱" } });
cout << "um1：" << endl;
for (auto pa : um1)
{
cout << pa.first << ' ' << pa.second << endl;
}
cout << endl;
cout << "um2：" << endl;
for (auto pa : um2)
{
cout << pa.first << ' ' << pa.second << endl;
}
cout << endl;
um1.swap(um2);
cout << "um1：" << endl;
for (auto pa : um1)
{
cout << pa.first << ' ' << pa.second << endl;
}
cout << endl;
cout << "um2：" << endl;
for (auto pa : um2)
{
cout << pa.first << ' ' << pa.second << endl;
}
cout << endl;
return 0;
}
1.2.2.4.5 clear()函数
<code>void clear() noexcept;
清除unordered_map中的有效数据
int main()
{
unordered_map<string, string> um({ { "string","字符串" }, { "sort","排序" } });
cout << "um size:" << um.size() << endl;
um.clear();
cout << "um size:" << um.size() << endl;
return 0;
}
1.2.2.4.6 find()函数
<code> iterator find ( const key_type& k );
const_iterator find ( const key_type& k ) const;
返回unordered_map中为k元素位置的迭代器
int main()
{
unordered_map<string, string> um({ { "string","字符串" }, { "sort","排序" } });
unordered_map<string, string>::iterator it = um.find("string");
cout << it->first << ' ' << it->second << endl;
return 0;
}
1.2.2.4.7 count()函数
<code>size_type count ( const key_type& k ) const;
返回unordered_map中关键码为k元素的个数
由于unordered_map并不允许相同的元素存在
所以unordered_map中所有元素的个数都是1
int main()
{
unordered_map<string, string> um({ { "string","字符串" }, { "sort","排序" } });
cout << "count : " << um.count("string") << endl;
return 0;
}
1.2.2.5 unordered_map的桶操作
1.2.2.5.1 bucket_count()函数
<code>size_type bucket_count() const noexcept;
返回哈希桶中桶的总个数
1.2.2.5.2 bucket_size()函数
size_type bucket_size ( size_type n ) const;
返回n号桶中有效元素的总个数
1.2.2.5.3 bucket()函数
size_type bucket ( const key_type& k ) const;
返回关键码为key所在的桶号
int main()
{
srand(time(0));
const size_t N = 10000;
unordered_map<int, int> um;
for (size_t i = 0; i < N; ++i)
{
int num = rand();
um.insert(make_pair(num, num));
}
cout << "bucket_count:" << um.bucket_count() << endl;
cout << "bucket_size:" << um.bucket_size(20) << endl;
cout << "bucket:" << um.bucket(um.begin()->first) << endl;
return 0;
}
二、底层结构
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。
2.1 哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(
l
o
g
2
N
log_2 N
log2N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：<code>hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？
答：我们会发现44的存储位置应该是4，但是我们发现4上已经有元素了，那么继续向后查找存储位置，但是我们会发现后面的5、6和7上都有元素了，所以44只能存在8这个位置了，所以这里我们发现产生冲突的数据堆积在一块。
2.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)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
发生哈希冲突该如何处理呢？
答：设计合理的哈希函数，使其能够将输入值均匀地映射到哈希表的各个位置；或者根据数据集的特征调整哈希函数的设计，减少冲突的可能性。
2.3 哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
常见哈希函数
直接定址法 ------ (常用)
取关键字的某个线性函数为散列地址：<code>Hash(Key) = A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
除留余数法 ------ (常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key%p(p<=m),将关键码转换成哈希地址
平方取中法 ------ (了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
折叠法 ------ (了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
随机数法 ------ (了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
2.4 哈希冲突解决
解决哈希冲突两种常见的方法是：闭散列和开散列
2.4.1 闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
2.4.1.1 线性探测
例如下图中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
①插入
------⑴通过哈希函数获取待插入元素在哈希表中的位置
------⑵如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
②删除
------采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
<code>// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{ EMPTY, EXIST, DELETE};
线性探测的实现及测试
#include<iostream>
#include<string>
#include<vector>
#include<unordered_set>
#include<set>
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& s)
{
size_t sum = 0;
for (size_t i = 0; i < s.size(); i++)
{
sum = sum * 31 + s[i];
}
return sum;
}
};
namespace open_address
{
enum status
{
EMPTY,
EXIST,
DELETE
};
template<class K , class V>
struct HashNode
{
pair<K, V> _kv;
status _st;
// 默认构造函数
HashNode() : _st(EMPTY) { }
HashNode(pair<K, V>& kv, status st = EMPTY)
:_kv(kv)
, _st(st)
{ }
};
template<class K, class V , class HF = HashFunc<K>>
class hash_table
{
public:
hash_table(int n = 10)
:_table(vector<HashNode<K, V>>(n))
,_n(n)
{ }
bool Insert(const pair<K, V>& kv)
{
// 每个关键码只能存在一个
if (Find(kv.first))
return false;
// 当负载因子为0.7时扩容
if (_n * 10 / _table.size() == 7)
{
int newsize = 2 * _table.size();
hash_table<K,V> newtable(newsize);
for (int i = 0; i < _table.size(); i++)
{
newtable.Insert(_table[i]._kv);
}
// 这里只需要交换存储的数据即可
// 因为两个表中数据个数相同，不需要交换
newtable._table.swap(_table);
}
// 找到hashi对应位置为 EMPTY 或 DELETE 的位置
HF hf;
int hashi = hf(kv.first) % _table.size();
while (_table[hashi]._st == EXIST)
{
hashi++;
hashi %= _table.size();
}
// 插入元素
_n++;
_table[hashi]._kv = kv;
_table[hashi]._st = EXIST;
return true;
}
bool Erase(const K& key)
{
HashNode* tmp = Find(key.first);
// 找不到则删除失败
if (tmp == nullptr)
return false;
// 找到了，删除，改变状态即可
tmp->_st = DELETE;
_n--;
return true;
}
HashNode<K,V>* Find(const K& key)
{
HF hf;
// 当hashi指向的位置为 EXIST 或 DELETE 时
// 需要一直查找，直到遇到 EMPTY 时停止
int hashi = hf(key) % _table.size();
while (_table[hashi]._st != EMPTY)
{
// 找到，返回这个节点
// 找到这个节点的状态必须时 EXIST
// 因为删除的时候，只修改了状态为 DELETE
// 节点的关键码没有改变，若没有这个条件的限制
// 删除某个元素后，再插入这个元素就插入不进去了
if (_table[hashi]._st == EXIST &&
_table[hashi]._kv.first == key)
{
return &_table[hashi];
}
hashi++;
hashi %= _table.size();
}
// 找不到返回空
return nullptr;
}
size_t Size()const
{
return _n;
}
bool Empty() const
{
return _n == 0;
}
void Swap(hash_table<K, V>& ht)
{
swap(_n, ht._n);
_table.swap(ht._table);
}
void Print()
{
for (int i = 0; i < _table.size(); i++)
{
cout << '[' << _table[i]._kv.first << "]->" <<
_table[i]._kv.second << endl;
}
cout << endl;
}
private:
vector<HashNode<K,V>> _table;
size_t _n; // 哈希表中有效元素的个数
/
public:
void TestHT()
{
hash_table<int, int> ht;
int a[] = { 4,14,24,34,5,7,1 };
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Insert(make_pair(3, 3));
ht.Insert(make_pair(3, 3));
ht.Insert(make_pair(-3, -3));
ht.Print();
}
void TestHT2()
{
string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
//HashTable<string, int, HashFuncString> ht;
hash_table<string, int> 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));
}
}
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.4.1.2 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：
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是表的大小。
对于2.1中如果要插入44，产生冲突，使用解决后的情况为：
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
2.4.2 开散列
2.4.2.1.开散列概念
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
2.4.2.2 开散列实现及测试
<code>// 整数类型
template<class 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 sum = 0;
for (int i = 0; i < s.size(); i++)
{
sum = sum * 31 + s[i];
}
return sum;
}
};
namespace hash_bucket
{
template<class K, class V>
struct HashNode
{
HashNode* _next;
pair<K, V> _kv;
HashNode(const pair<K, V>& kv)
:_kv(kv)
, _next(nullptr)
{ }
};
template<class K, class V , class HF = HashFunc<K>>
class hash_table
{
public:
typedef HashNode<K, V> Node;
public:
hash_table(int n = 10)
:_table(vector<Node*>(n))
,_n(0)
{ }
~hash_table()
{
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
bool Insert(const pair<K, V>& kv)
{
// 不允许有相同的值
Node* tmp = Find(kv.first);
if (tmp != nullptr)
return false;
HF hf;
// 扩容
if (_n == _table.size())
{
int newcapacity = 2 * _table.size();
hash_table newtable(newcapacity);
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
int hashi = hf(cur->_kv.first) % newcapacity;
cur->_next = newtable._table[hashi];
newtable._table[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable._table);
}
// 头插
int hashi = hf(kv.first) % _table.size();
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
_n++;
return true;
}
bool Erase(const K& key)
{
Node* tmp = Find(key);
// 找不到则删除失败
if (tmp == nullptr)
return false;
HF hf;
int hashi = hf(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
Node* next = cur->_next;
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_table[hashi] = next;
}
else
{
prev->_next = next;
}
_n--;
delete cur;
return true;
}
else
{
prev = cur;
cur = next;
}
}
return false;
}
Node* Find(const K& key)
{
HF hf;
int hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (cur ->_kv.first == key)
return cur;
cur = cur->_next;
}
// 找不到返回空
return nullptr;
}
void Some()
{
size_t bucketSize = 0;
size_t maxBucketLen = 0;
size_t sum = 0;
double averageBucketLen = 0;
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
{
++bucketSize;
}
size_t bucketLen = 0;
while (cur)
{
++bucketLen;
cur = cur->_next;
}
sum += bucketLen;
if (bucketLen > maxBucketLen)
{
maxBucketLen = bucketLen;
}
}
averageBucketLen = (double)sum / (double)bucketSize;
printf("all bucketSize:%d\n", _table.size());
printf("bucketSize:%d\n", bucketSize);
printf("maxBucketLen:%d\n", maxBucketLen);
printf("averageBucketLen:%lf\n\n", averageBucketLen);
}
private:
vector<Node*> _table;
int _n;
public:
void TestHT1()
{
hash_table<int, int> ht;
int a[] = { 4,14,24,34,5,7,1 };
for (auto e : a)
{
ht.Insert(make_pair(e, e));
}
ht.Insert(make_pair(3, 3));
ht.Insert(make_pair(3, 3));
ht.Insert(make_pair(-3, -3));
ht.Some();
}
void TestHT2()
{
string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
//HashTable<string, int, HashFuncString> ht;
hash_table<string, int> 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));
}
}
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));
}
void TestHT3()
{
const size_t N = 1000;
unordered_set<int> us;
set<int> s;
hash_table<int, int> ht;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; ++i)
{
//v.push_back(rand()); // N比较大时，重复值比较多
v.push_back(rand() + i); // 重复值相对少
//v.push_back(i); // 没有重复，有序
}
// 21:15
size_t begin1 = clock();
for (auto e : v)
{
s.insert(e);
}
size_t end1 = clock();
cout << "set insert:" << end1 - begin1 << endl;
size_t begin2 = clock();
for (auto e : v)
{
us.insert(e);
}
size_t end2 = clock();
cout << "unordered_set insert:" << end2 - begin2 << endl;
size_t begin3 = clock();
for (auto e : v)
{
ht.Insert(make_pair(e, e));
}
size_t end3 = clock();
cout << "hash_table insert:" << end3 - begin3 << endl << endl;
size_t begin4 = clock();
for (auto e : v)
{
s.find(e);
}
size_t end4 = clock();
cout << "set find:" << end4 - begin4 << endl;
size_t begin5 = clock();
for (auto e : v)
{
us.find(e);
}
size_t end5 = clock();
cout << "unordered_set find:" << end5 - begin5 << endl;
size_t begin6 = clock();
for (auto e : v)
{
ht.Find(e);
}
size_t end6 = clock();
cout << "hash_table find:" << end6 - begin6 << endl << endl;
cout << "插入数据个数：" << us.size() << endl << endl;
ht.Some();
size_t begin7 = clock();
for (auto e : v)
{
s.erase(e);
}
size_t end7 = clock();
cout << "set erase:" << end7 - begin7 << endl;
size_t begin8 = clock();
for (auto e : v)
{
us.erase(e);
}
size_t end8 = clock();
cout << "unordered_set erase:" << end8 - begin8 << endl;
size_t begin9 = clock();
for (auto e : v)
{
ht.Erase(e);
}
size_t end9 = clock();
cout << "hash_table Erase:" << end9 - begin9 << endl << endl;
}
};
}
2.4.2.3 开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。
下面扩容部分在insert函数中。
namespace hash_bucket
{
template<class K, class V , class HF = HashFunc<K>>
class hash_table
{
public:
typedef HashNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
// 不允许有相同的值
Node* tmp = Find(kv.first);
if (tmp != nullptr)
return false;
HF hf;
// 扩容
if (_n == _table.size())
{
int newcapacity = 2 * _table.size();
hash_table newtable(newcapacity);
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
int hashi = hf(cur->_kv.first) % newcapacity;
cur->_next = newtable._table[hashi];
newtable._table[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable._table);
}
// 头插
int hashi = hf(kv.first) % _table.size();
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
_n++;
return true;
}
private:
vector<Node*> _table;
int _n;
}
2.4.2.4 开散列的思考
只能存储key为整形的元素，其他类型怎么解决？
答：写一个仿函数将当前类型转化为整数。
// 整数类型
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 特化为string版本
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t sum = 0;
for (int i = 0; i < s.size(); i++)
{
sum = sum * 31 + s[i];
}
return sum;
}
};
2.4.2.5 开散列与闭散列比较
应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <=0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。
结尾
由于不想文章篇幅太过长，有关于哈希表的实现、unordered_set 和 unordered_map封装实现、位图和布隆过滤器将会在后面的文章进行讲解。
如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。