unordered_map的使用

这篇具有很好参考价值的文章主要介绍了unordered_map的使用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

unordered_map的使用


简介

无序映射(Unordered maps)是用于存储键值和映射值组合成的元素的关联容器,并允许基于其键快速检索各个元素。在unordered_map中,键值通常用于唯一地标识元素,而映射值是具有与该键关联的内容的对象。键的类型和映射的值可能会有所不同。


一、unordered_map内部实现

unordered_map内部实现了一个哈希表(也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序是无序的。

二、与map的区别

1.map

1,map内置红黑树,使得查找,插入,删除的平均时间复杂度为O(logN)
2,map内部元素有序

2.unordered_map

1,unordered_map查找,插入,删除的平均时间复杂度为 O(1)
2,unordered_map内部元素无序

三、问题

当我们的输入数据随机时,每个项平均只会遇到O(1)的冲突,但是如果我们输入特殊数据使得这些输入都产生冲突,就会变成O(n^2)。

四,解决方案

参考文章:https://codeforces.com/blog/entry/62393%E3%80%82文章来源地址https://www.toymoban.com/news/detail-662628.html

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map<int,int,custom_hash>mp;

到了这里,关于unordered_map的使用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】哈希表封装实现 unordered_map 和 unordered_set

    在 C++98 中,STL 提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 O(logN),即最差情况下只需要比较红黑树的高度次;但是当树中的节点非常多时,其查询效率也不够极致。 最好的查询是,不进行比较或只进行常数次比较就能够将元素找到,因此在 C++11 中,

    2023年04月16日
    浏览(48)
  • 从哈希桶角度看 unordered_map 与 unordered_set 的实现

    哈希函数与哈希桶是计算机科学中用于实现高效数据检索的重要工具。在之前的博客中,我们已经详细探讨了哈希的基本概念、哈希函数的构造方法以及哈希桶的工作原理等内容。在本篇博客中,我们将进一步深入探索C++中的unordered系列数据结构,并利用之前介绍的哈希桶原

    2024年03月22日
    浏览(39)
  • 【C++】用哈希桶模拟实现unordered_set和unordered_map

    顺序结构中(数组)查找一个元素需要遍历整个数组,时间复杂度为O(N);树形结构中(二叉搜索树)查找一个元素,时间复杂度最多为树的高度次logN。理想的搜索方法: 可以不经过任何比较,一次直接从表中得到要搜索的元素。 构造一种存储结构, 通过某种函数使元素的

    2024年04月11日
    浏览(51)
  • 由[哈希/散列]模拟实现[unordered_map/unordered_set] (手撕迭代器)

    以下两篇文章均为笔者的呕心沥血 想要搞懂本篇文章的uu请自行查阅 哈希/散列的细节实现 哈希/散列–哈希表[思想到结构][==修订版==] 手撕迭代器的细节处理 模拟实现map/set[改编红黑树实现map/set容器底层]

    2024年02月07日
    浏览(45)
  • [C++]哈希表实现,unordered_map\set封装

    目录 ​​​​​​​ 前言: 1 哈希 1.1 为什么有哈希 1.2 哈希结构 1.3 哈希冲突  2 闭散列 2.1 闭散列结点结构和位置状态表示 2.2 哈希类结构 2.3 插入 2.4 查找 2.5 删除 3 开散列 3.1 哈希表结点结构 3.2 哈希表结构 3.3 插入 3.4 查找、删除 3.5 迭代器实现 4 map和set的封装 4.1 map的封

    2024年02月08日
    浏览(49)
  • 【C++】开散列哈希表封装实现unordered_map和unordered_set

    在未达成目的之前,一切具有诱惑力的事物都显得那么不堪一击 1. 在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2 N l o g 2 ​ N ,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。 最好的查询是

    2023年04月09日
    浏览(83)
  • C++利用开散列哈希表封装unordered_set,unordered_map

    1.之前我们已经实现了开散列的哈希表,今天我们来用它封装unordered_set,unordered_map 2.本文的封装比利用红黑树封装set和map更加复杂 建议大家先去看我的红黑树封装set和map再来看本文 因为有很多地方跟红黑树封装set和map时是同样的思路和方法,所以本文不会太去赘述一遍 因为un

    2024年03月24日
    浏览(55)
  • C++ 哈希+unordered_map+unordered_set+位图+布隆过滤器(深度剖析)

    想象一下,你有一个巨大的图书馆,里面摆满了成千上万本书。如果你想要找到其中一本特定的书,你会怎么做?如果你按照书的编号来有序地排列它们,找到特定的书本可能会很容易。但是,如果书籍是随机地摆放,你可能需要逐本地查找,这个过程会非常耗时。 而哈希函

    2024年02月21日
    浏览(52)
  • 【C++】STL——用一个哈希表封装出unordered_map和unordered_set

    根据先前对unordered_map和unordered_set的学习,我们得知其底层是借助哈希表来实现的,接下来我们会使用上篇博客实现的开散列哈希表来模拟实现unordered_map和unordered_set,哈希表源代码链接: Hash/Hash/HashBucket.h · wei/cplusplus - 码云 - 开源中国 (gitee.com) 下面我们对哈希表进行改造,

    2023年04月18日
    浏览(46)
  • 【C++】如何用一个哈希表同时封装出unordered_set与unordered_map

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.哈希桶源码  2.哈希表模板参数的控制 3.字符串作为键值如何映射哈希值

    2024年03月26日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包