【C++】哈希——unordered系列容器&哈希概念&哈希冲突(上)

本文涉及的产品
对象存储 OSS,20GB 3个月
对象存储 OSS,恶意文件检测 1000次 1年
对象存储 OSS,内容安全 1000次 1年
简介: 【C++】哈希——unordered系列容器&哈希概念&哈希冲突(上)

1. unordered系列的关联式容器


1.1 引言

在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到l o g 2 N log_2 Nlog

2

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

注意:实际上,unordered系列容器的使用和map/set基本一致,区别就在于unordered系列只支持单向迭代器,并且由于结构的限制,遍历unordered系列容器的顺序是无序


1.2 unordered_map的使用说明

使用文档

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lh9sfZMp-1684930297303)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2013.41.16.png)]

void Test_unordered_map()
{
    unordered_map<string, int> countMap;
    string arr[] = { "苹果", "西瓜", "香蕉","苹果", "西瓜", "西瓜"};
    for(const auto& str : arr)
    {
        //countMap[str]++;
        auto it = countMap.find(str);
        if(it == countMap.end())
        {
            countMap.insert(make_pair(str, 1));
        }
        else
        {
            it->second++;
        }
    }
    for(const auto& kv : countMap)
    {
        cout << kv.first << ":" << kv.second << endl;
    }
    cout << endl;
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zQ3hv30X-1684930297304)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2013.48.12.png)]


除了map的接口之外,由于unordered_map的底层是哈希桶,所以,有一些只属于哈希桶的接口

函数原型 功能介绍
size_t bucket_count() const 返回哈希桶中桶的总个数
size_t max_bucket_count() const 返回哈希桶中能够容纳的最大的桶个数
size_t bucket_size(size_t n) const 返回哈希桶中有效元素个数
**size_t bucket(const K& key) ** 返回元素key所在的桶号


1.3 unordered_set的使用说明

使用文档

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l4MBpovo-1684930297304)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2013.33.08.png)]

void Test_unordered_set()
{
    unordered_set<int> us;
    us.insert(10);
    us.insert(2);
    us.insert(4);
    us.insert(5);
    us.insert(3);
    us.insert(1);
    us.insert(10);
    unordered_set<int>::iterator it = us.begin();
    while(it != us.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YZHaJAyB-1684930297304)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2014.04.56.png)]


1.4 unordered_set和unordered_map的应用


在长度为2*N的数组中找到重复出现N次的数


[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xTk0r0sx-1684930297305)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2014.44.00.png)]


1.5 性能比较

void Test_efficient()
{
  const size_t N = 1000000;//测试的数据个数
    //构造两个数组,一个有序一个无序,用于测试
  vector<int> SortV;
    vector<int> UnsortV;
  SortV.reserve(N);
  UnsortV.reserve(N);
  srand(time(0));
  for (int i = 0; i < N; ++i)
  {
    UnsortV.push_back(rand());
        SortV.push_back(i);
  }
    //开始测试
    unordered_set<int> SortUs;
    unordered_set<int> UnsortUs;
  set<int> SortS;
  set<int> UnsortS;
    cout << "有序插入效率对比" << endl;
  size_t begin1 = clock();
  for (auto e : SortV)
  {
    SortS.insert(e);
  }
  size_t end1 = clock();
  cout << "set insert sorted:" << end1 - begin1 << endl;
  size_t begin2 = clock();
  for (auto e : SortV)
  {
    SortUs.insert(e);
  }
  size_t end2 = clock();
  cout << "unordered_set insert sorted:" << end2 - begin2 << endl;
    cout << "无序插入效率对比" << endl;
  size_t begin3 = clock();
  for (auto e : UnsortV)
  {
    UnsortS.insert(e);
  }
  size_t end3 = clock();
  cout << "set insert unsort:" << end3 - begin3 << endl;
  size_t begin4 = clock();
  for (auto e : UnsortV)
  {
    UnsortUs.insert(e);
  }
  size_t end4 = clock();
  cout << "unordered_set insert unsort:" << end4 - begin4 << endl;
    cout << "有序查找效率对比" << endl;
    size_t begin5 = clock();
  for (auto e : SortV)
  {
    SortS.find(e);
  }
  size_t end5 = clock();
  cout << "set find sorted:" << end5 - begin5 << endl;
  size_t begin6 = clock();
  for (auto e : SortV)
  {
    SortUs.find(e);
  }
  size_t end6 = clock();
  cout << "unordered_set find sorted:" << end6 - begin6 << endl;
    cout << "无序查找效率对比" << endl;
    size_t begin7 = clock();
  for (auto e : UnsortV)
  {
    UnsortS.find(e);
  }
  size_t end7 = clock();
  cout << "set find unsorted:" << end7 - begin7 << endl;
  size_t begin8 = clock();
  for (auto e : UnsortV)
  {
    UnsortUs.find(e);
  }
  size_t end8 = clock();
  cout << "unordered_set find unsorted:" << end8 - begin8 << endl;
    cout << "有序删除效率对比" << endl;
  size_t begin9 = clock();
  for (auto e : SortV)
  {
    SortS.erase(e);
  }
  size_t end9 = clock();
  cout << "set erase sorted:" << end9 - begin9 << endl;
  size_t begin10 = clock();
  for (auto e : SortV)
  {
    SortUs.erase(e);
  }
  size_t end10 = clock();
  cout << "unordered_set erase:" << end10 - begin10 << endl;
    cout << "无序删除效率对比" << endl;
    size_t begin11 = clock();
  for (auto e : UnsortV)
  {
    UnsortS.erase(e);
  }
  size_t end11 = clock();
  cout << "set erase sorted:" << end11 - begin11 << endl;
  size_t begin12 = clock();
  for (auto e : UnsortV)
  {
    UnsortUs.erase(e);
  }
  size_t end12 = clock();
  cout << "unordered_set erase:" << end12 - begin12 << endl;
}


[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wXEUyCsZ-1684930297305)(https://pic-bed123.oss-cn-nanjing.aliyuncs.com/%E6%88%AA%E5%B1%8F2023-05-23%2015.07.18.png)]


可以看到随机数下unordered系列效率更高,但是有序数的情况下就不太行。


2. 哈希概念


unordered系列的关联式容器之所以效率比较高,是因为其底层使用了哈希结构,那么什么是哈希?


顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素 时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即**O(l o g 2 N log_2 Nlog

2

N)**搜索的效率取决于搜索过程中元素的比较次数。


理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。类似通过下标访问数组中任意位置的元素。 如果构造一种存储结构,通过某种函数(HashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系,那么在查找时通过该函数可以很快找到该元素。


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

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


接下来我们看下面这个例子:

假设有数据集{1, 7, 6, 4, 5, 9};

哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小

按照这种存放方式,如果需要查找4,就直接通过4 % 10 = 4找到hash(key) = 4的位置,直接取出来即可,省略了多次key的比较,节约了时间。

a0d13a663c124326b054b64d1c5d87b4.png

相关实践学习
借助OSS搭建在线教育视频课程分享网站
本教程介绍如何基于云服务器ECS和对象存储OSS,搭建一个在线教育视频课程分享网站。
相关文章
|
2月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
54 2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
|
2月前
|
存储 C++ 容器
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器1
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
55 5
|
2月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
59 2
|
2月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
3月前
|
运维 Cloud Native Devops
云原生架构的崛起与实践云原生架构是一种通过容器化、微服务和DevOps等技术手段,帮助应用系统实现敏捷部署、弹性扩展和高效运维的技术理念。本文将探讨云原生的概念、核心技术以及其在企业中的应用实践,揭示云原生如何成为现代软件开发和运营的主流方式。##
云原生架构是现代IT领域的一场革命,它依托于容器化、微服务和DevOps等核心技术,旨在解决传统架构在应对复杂业务需求时的不足。通过采用云原生方法,企业可以实现敏捷部署、弹性扩展和高效运维,从而大幅提升开发效率和系统可靠性。本文详细阐述了云原生的核心概念、主要技术和实际应用案例,并探讨了企业在实施云原生过程中的挑战与解决方案。无论是正在转型的传统企业,还是寻求创新的互联网企业,云原生都提供了一条实现高效能、高灵活性和高可靠性的技术路径。 ##
219 3
|
2月前
|
程序员 C++ 开发者
C++入门教程:掌握函数重载、引用与内联函数的概念
通过上述介绍和实例,我们可以看到,函数重载提供了多态性;引用提高了函数调用的效率和便捷性;内联函数则在保证代码清晰的同时,提高了程序的运行效率。掌握这些概念,对于初学者来说是非常重要的,它们是提升C++编程技能的基石。
23 0
|
4月前
|
Linux 持续交付 虚拟化
在Linux中,Docker和容器虚拟概念是什么?
在Linux中,Docker和容器虚拟概念是什么?
|
4月前
|
消息中间件 Kubernetes 数据库
在k8S中,初始化容器(init container)概念原理是什么?
在k8S中,初始化容器(init container)概念原理是什么?
|
4月前
|
安全 编译器 容器
C++STL容器和智能指针
C++STL容器和智能指针
|
4月前
|
C++ 容器
C++中自定义结构体或类作为关联容器的键
C++中自定义结构体或类作为关联容器的键
42 0