【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 log2N,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在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. 它的迭代器至少是前向迭代器。

在这里插入图片描述

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<iostream>
#include<unordered_set>using namespace std;int main()
{unordered_set<int> us;return 0;
}

在这里插入图片描述


1.1.2.1.2 有参构造函数(使用迭代器进行初始化构造)
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 拷贝构造函数
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 的迭代器是单向的,所以没有 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()函数
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()函数
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()函数
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 = trueiterator 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()函数
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()函数
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()函数
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()函数
	  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()函数
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()函数
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的文档介绍

  1. unordered_map是存储<key, value>键值对的关联式容器,其允许通过keys快速的索引到与其对应的value。
  2. 在unordered_map中,键值通常用于惟一地标识元素,而映射值是一个对象,其内容与此键关联。键和映射值的类型可能不同。
  3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value,unordered_map将相同哈希值的键值对放在相同的桶中。
  4. unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭代方面效率较低。
  5. unordered_maps实现了直接访问操作符(operator[]),它允许使用key作为参数直接访问value。
  6. 它的迭代器至少是前向迭代器。

在这里插入图片描述

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 无参构造函数
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 有参构造函数(使用迭代器进行初始化构造)
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 拷贝构造函数
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 的迭代器是单向的,所以没有 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()函数
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()函数
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()函数
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 = trueiterator 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[]
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()函数
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()函数
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()函数
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()函数
	  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()函数
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()函数
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};
哈希函数设置为: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之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单

常见哈希函数

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

  2. 除留余数法 ------ (常用)
    设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key%p(p<=m),将关键码转换成哈希地址

  3. 平方取中法 ------ (了解)
    假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址;再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况

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

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

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


2.4 哈希冲突解决

解决哈希冲突两种常见的方法是:闭散列和开散列

2.4.1 闭散列

闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢?

2.4.1.1 线性探测

例如下图中的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,hashAddr为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。
线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

①插入
------⑴通过哈希函数获取待插入元素在哈希表中的位置
------⑵如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素
在这里插入图片描述

②删除
------采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

// 哈希表每个空间给个标记
// 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 开散列实现及测试
// 整数类型
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:15size_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封装实现、位图和布隆过滤器将会在后面的文章进行讲解。

如果有什么建议和疑问,或是有什么错误,大家可以在评论区中提出。
希望大家以后也能和我一起进步!!🌹🌹
如果这篇文章对你有用的话,希望大家给一个三连支持一下!!🌹🌹

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

探索序列到序列模型:了解编码器和解码器架构的强大功能

目录 一、说明 二、什么是顺序数据&#xff1f; 三、编码器解码器架构的高级概述&#xff1a; 3.1 编码器和解码器架构的简要概述&#xff1a; 3.2 训练机制&#xff1a;编码器和解码器架构中的前向和后向传播&#xff1a; 四、编码器解码器架构的改进&#xff1a; 4.1.…

Spring自定义标签体系和应用

我们知道&#xff0c;在使用Dubbo框架时&#xff0c;需要指定配置文件中的application、protocol、registry、provider、service等服务器端和客户端的配置项&#xff0c;典型的配置方法如下所示。通过这些配置项&#xff0c;我们可以基于Spring容器来启动Dubbo服务。 <!-- …

SpringBoot 实现RequestBodyAdvice封装统一接受类功能

一、相关往期文章 SpringBootVue实现AOP系统日志功能_aop的vue完整项目 Spring AOP (面向切面编程&#xff09;原理与代理模式—实例演示_面向切面aop原理详解 二、需求分析 按照一般情况&#xff0c;统一接受类可以像以下的方式进行处理&#xff1a; 如果不想使用 Request…

Shiro721 反序列化漏洞(CVE-2019-12422)

目录 Shiro550和Shiro721的区别 判断是否存在漏洞 漏洞环境搭建 漏洞利用 利用Shiro检测工具 利用Shiro综综合利用工具 这一篇还是参考别的师傅的好文章学习Shiro的反序列化漏洞 上一篇也是Shiro的反序列化漏洞&#xff0c;不同的是一个是550一个是721&#xff0c;那么这…

【vue scrollTo 数据无限滚动 】

vue数据无限滚动 参考来源 Vue3 实现消息无限滚动的新思路 —— 林三心不学挖掘机 vue3代码 <template><div class"scroll-container" ref"scrollRef"><div v-for"(item, index) in list" :key"index" style"hei…

网络协议安全:TCP/IP协议栈的安全问题和解决方案

「作者简介」:北京冬奥会网络安全中国代表队,CSDN Top100,就职奇安信多年,以实战工作为基础对安全知识体系进行总结与归纳,著作适用于快速入门的 《网络安全自学教程》,内容涵盖Web安全、系统安全等12个知识域的一百多个知识点,持续更新。 这一章节我们需要知道TCP/IP每…

【Git】--Part3--远程操作 配置 标签管理

1. 远程仓库 Git 是分布式版本控制系统&#xff0c;同⼀个 Git 仓库&#xff0c;可以分布到不同的机器上。怎么分布呢&#xff1f; 最早&#xff0c;肯定只有⼀台机器有⼀个原始版本库&#xff0c;此后&#xff0c;别的机器可以 “克隆” 这个原始版本库&#xff0c;⽽且每台机…

JavaSE 面向对象程序设计初级 静态static 包package 常量final 代码块 代码实操理论内存原理详解

目录 static(静态) 静态的特点 应用示例 静态变量 静态方法 注意事项 内存图 重新认识main方法 包 什么是包 使用导包在什么时候 final关键字 常量 命名规范 细节&#xff08;重点&#xff09; 权限修饰符 代码块 局部代码块 构造代码块 静态代码块 个人号…

vue中实现百度地图全国与省市地图切换

前言 本文主要是用于示例全国地图&#xff0c;点击省市地图直接跳转到该省市地图并展示&#xff0c;可以拓展在地图上显示标记点&#xff08;本文未做示例&#xff09;&#xff0c;后续有完整代码&#xff0c;但是由于需要与本来项目业务代码进项分割&#xff0c;可能会有些问题…

多模态大模型面对误导性问题:看懂图片也会答错,一骗就中招

多模态大语言模型&#xff08;MLLMs&#xff09;因其在视觉理解和推理方面的突出表现&#xff0c;例如生成详细的图像描述和回答复杂的问题等&#xff0c;逐渐成为近期AI研究的热点。 然而&#xff0c;Bunny 团队的最新研究发现&#xff0c;尽管许多MLLMs对视觉内容能够正确理…

RocketMQ快速入门:集成spring, springboot实现各类消息消费(七)附带源码

0. 引言 rocketmq支持两种消费模式&#xff1a;pull和push&#xff0c;在实际开发中这两种模式分别是如何实现的呢&#xff0c;在spring框架和springboot框架中集成有什么差异&#xff1f;今天我们一起来探究这两个问题。 1. java client实现消息消费 1、添加依赖 <depen…

方舟云康亏损收窄:三年近10亿销售成本,平均付费及月活仍大幅承压

《港湾商业观察》施子夫 三度递表后&#xff0c;终于通过聆讯&#xff0c;方舟云康控股有限公司(以下简称&#xff0c;方舟云康)有望近期内挂牌港交所。方舟云康的国内运营主体为广州方舟云康信息科技集团有限公司、广州方舟医药有限公司。 值得关注的是&#xff0c;亏损的难…

Python日志管理利器:如何高效管理平台日志

一、为什么需要日志管理&#xff1f; 日志是应用程序的重要组成部分&#xff0c;它记录了应用程序的运行状态、错误信息以及用户交互等关键信息。良好的日志管理可以帮助开发人员及时发现和解决问题&#xff0c;提高应用程序的稳定性和可靠性。 项目在本地开发调试时&#xf…

vscode字符多行自动增长插件。

多行字符自动增长插件CharAutoIncre 当你使用shiftalt选中了多行,并输入了’1’,这时这几行都变成了’1’. 这时你可以选中&#xff08;shift左键&#xff09;为’1’的这几行, 接下来按下shiftaltq此时’1’变为了’12345’自增长的样式。 同时本插件支持字符’a-z,A-Z’。 目…

【知识图谱】基于neo4j开发的信息化文档分析系统(源码)

一、项目介绍 一款全源码&#xff0c;可二开&#xff0c;可基于云部署、私有部署的企业级知识库云平台&#xff0c;一款让企业知识变为实打实的数字财富的系统&#xff0c;应用在需要进行文档整理、分类、归集、检索、分析的场景。 为什么建立知识库平台&#xff1f; 助力企业…

IDEA中 pom.xml 设置自动提示

IDEA中 pom.xml 自动提示 IDEA中 pom.xml 自动提示设置如下&#xff1a; file–>Settings–>Build,Execution…–>Build Tools–>Maven–>Repositories 会看到类似表格的画面&#xff0c;内容是你的maven地址&#xff0c;选中后&#xff0c;右边有个Update的按…

Python酷库之旅-第三方库openpyxl(01)

目录 一、 openpyxl库的由来 1、背景 2、起源 3、发展 4、特点 4-1、支持.xlsx格式 4-2、读写Excel文件 4-3、操作单元格 4-4、创建和修改工作表 4-5、样式设置 4-6、图表和公式 4-7、支持数字和日期格式 二、openpyxl库的优缺点 1、优点 1-1、支持现代Excel格式…

鄂州职业大学2024年成人高等继续教育招生简章

鄂州职业大学&#xff0c;作为一所享有盛誉的高等学府&#xff0c;一直以来都致力于为社会培养具备专业技能和良好素养的优秀人才。在成人高等继续教育领域&#xff0c;该校同样表现出色&#xff0c;为广大渴望继续深造、提升自身能力的成年人提供了宝贵的学习机会。 随着社会…

椭圆的矩阵表示法

椭圆的矩阵表示法 flyfish 1. 标准几何表示法 标准几何表示法是通过椭圆的几何定义来表示的&#xff1a; x 2 a 2 y 2 b 2 1 \frac{x^2}{a^2} \frac{y^2}{b^2} 1 a2x2​b2y2​1其中&#xff0c; a a a 是椭圆的长半轴长度&#xff0c; b b b 是椭圆的短半轴长度。 2.…

一文带你全面详细了解安全运维

一、安全运维-网络 1、IP地址相关 IP地址属于网络层地址&#xff0c;用于标识网络中的节点设备。 IP地址由32bit构成&#xff0c;每8bit一组&#xff0c;共占用4个字节。 IP地址由两部分组成&#xff0c;网络位和主机位。 IP地址分类&#xff1a; 类别网络位子网掩码私有地…