为什么在unordered_map中插入字符串的平均时间复杂度是恒定的？
在unordered_map中插入字符串的平均时间复杂度是恒定的，这是因为unordered_map是基于哈希表实现的数据结构。
哈希表是一种以键值对存储数据的数据结构，它通过将键映射到哈希表中的一个位置来实现快速的查找和插入操作。在unordered_map中，字符串作为键，通过哈希函数将字符串映射到哈希表的一个位置。
在插入字符串时，首先会计算字符串的哈希值，然后根据哈希值找到对应的位置。如果该位置为空，则直接将字符串插入到该位置；如果该位置已经存在其他元素，则通过链表或者红黑树等数据结构解决冲突，将新的字符串插入到合适的位置。
由于哈希函数的设计和哈希表的扩容机制，使得在大多数情况下，字符串的插入操作可以在常数时间内完成。只有在哈希冲突较多的情况下，才可能需要进行链表或者红黑树的操作，此时插入操作的时间复杂度会略微增加，但仍然是非常高效的。
总结起来，unordered_map中插入字符串的平均时间复杂度是恒定的，这是因为它利用了哈希表的快速查找和插入特性，通过哈希函数将字符串映射到哈希表的位置，实现了高效的插入操作。
相关·内容
3回答
关键字查找在std::map O(1)上吗？我一直以为是这样的，直到我想得更多。它是基于树实现的，所以查找时间应该是O(log )，对吗？
还有，有没有可能让O(1)查找字符串键，也许是std::unordered_map？
浏览 4提问于2013-04-18得票数 40
std::unordered_map保证O(1)时间搜索，但它如何管理冲突？
索赔
无序映射是一个关联容器，包含具有唯一键的键值对。元素的搜索、插入和删除具有平均恒定时间复杂度.
假设所有哈希代码都相同的情况下，冲突是如何内部处理的？
如果散列码对每个键都是唯一的，我的假设将是完全错误的。在这种情况下，在根本没有冲突的情况下，如何创建唯一的哈希码？
std::unordered_map的哈希函数采用什么方法来保证O(1)搜索？
浏览 3提问于2016-05-04得票数 5
回答已采纳
正如在新标准中引入的std::unordered_map/std::unordered_set一样，它使用散列函数并具有插入/删除/获取元素的平均恒定复杂性，如果我们不需要按特定顺序迭代集合，似乎没有理由使用“旧的”std::map/std::set？或者还有其他一些情况/原因，当std::map/std::set会是更好的选择？会不会是给前任的。更少的内存消耗，或者他们比“无序”版本唯一的优点是排序？
浏览 0提问于2021-03-01得票数 0
1回答
C++库(包括unordered_map和multimap)中的内置映射和集合要求find函数(用于查找特定元素)使用迭代器来遍历元素。C++参考站点声称使用这些数据结构查找元素需要平均恒定的时间，就像常规的哈希表一样。但是，在找到元素之前，迭代器不是必须遍历整个列表，使平均时间为O(n)吗？
浏览 1提问于2014-08-23得票数 6
回答已采纳
3回答
我正在LeetCode上解决一个问题，但还没有人能够解释我的问题。
问题是：
给定任意的勒索条字符串和另一个包含所有杂志信件的字符串，编写一个函数，如果可以从杂志中构造赎金说明，则返回true；否则，它将返回false。
杂志字符串中的每一封信只能在你的勒索信中使用一次。
注意:您可以假设这两个字符串只包含小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab&
浏览 0提问于2019-04-01得票数 7
回答已采纳
我需要使用一个平均支持恒定时间查找的数据结构。我认为使用std::unordered_map是一个很好的方法。我的数据是数字的“集合”。
|115|190|380|265|
这些数字不必按特定顺序排列。我需要大约O(1)时间来确定这个数据结构中是否存在给定的数字。我有使用std::unordered_map的想法，它实际上是一个哈希表(我是对的吗？)因此，数字将是键，然后我就会有虚拟的值。
因此，基本上，我首先需要确定数据结构中是否存在匹配给定数字的密钥，并根据该条件运行一些算法。除了这个条件之外，我还想更新一个特定的键。假设是190，我想在其中添加20，所以现在关键是210。现在的数据结构应
浏览 3提问于2018-09-25得票数 6
回答已采纳
在STL中使用int数组还是unordered_map在内存和时间复杂度方面哪一个更有效？
哈希指的是存储由键值和映射值组合而成的元素，以及根据键快速检索单个元素。
其实我是想解决的问题。我的解决办法是：-
#include <bits/stdc++.h>
#define MAX 15000005
using namespace std;
/*
* author: vivekcrux
*/
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
浏览 0提问于2018-09-21得票数 1
在维基百科关于动态数组的文章中，它提到(除了关于分期插入时间的正常部分)：
这个比例的值是我们增加容量的常数因子，它导致了一个时空权衡:每次插入操作的平均时间约为a/(a 1)，而浪费的细胞数在(a−1)n上有界。
我可以看到浪费细胞的(a-1)n是从哪里来的，但是有人能解释为什么平均时间是a/(a-1)吗？
浏览 2提问于2011-07-27得票数 3
找不到合适的答案
为什么插入函数需要o(n)时间复杂度，而我们提供了插入位置？有人能告诉我原因吗.在我看来，这是因为迭代器，，，可能是我错了，但我想要澄清它。
我从给定的链接中读到了它，但我没有找到正确的问题答案。
浏览 2提问于2020-07-16得票数 0
回答已采纳
我对同一函数有两种不同的实现
IPAddress UMNS::lookup(const HostName& name) const{
auto it=ns.find(name);
if(it!=ns.end()){
return (*it).second;
}
return NON_EXISTING_ADDRESS;
}
和
IPAddress UMNS::lookup(const HostName& name) const{
auto it=find_if(ns.begin(),ns.end(),
[
浏览 0提问于2014-02-24得票数 0
是否unordered_map中按特定顺序插入的键将在使用迭代器迭代映射时以相同顺序的形式出现？
例如:如果我们在B中插入(4,3)，(2，5)，(6，7)并迭代如下：
for(auto it=B.begin();it!=B.end();it++) {
cout<<(it->first);
}
它会给我们4，2，6或者钥匙可能有任何顺序吗？
浏览 0提问于2018-06-15得票数 47
回答已采纳
1回答
日安！
我有一个关于二进制搜索树插入方法的时间复杂度的问题。我读了一些关于这个问题的答案，但有些答案是不同的。二叉树插入方法的平均时间复杂度是O(log )，最坏情况是O(n)？或者对于平均情况是O(n log n)，对于最坏情况是O(n^2)？什么时候它在平均情况下变成O(n log n)，在最坏情况下变成O(n^2)？
浏览 1提问于2014-10-17得票数 3
1回答
这里我有800个派生类的Base和这些类型的8000000个对象的列表，这些对象可以是任意顺序的。目标是尽可能有效地将列表划分为800种类型。在这里，我编写了两个函数来实现这一点。第一个应该是O(M*logN)时间，其中M是列表的大小，N= Base的具体派生类的数目，第二个应该是O(M)时间。但是，当我计时输出时，第二个输出显然不会比第一个log800快一倍。我搞错时间复杂性了吗？更好的是，是否有一个更快的功能，使整个比较成为一个没有意义的点？
#include <iostream>
#include <list>
#include <unordered_map
浏览 2提问于2015-06-15得票数 0
回答已采纳
在实践中，是否存在必须使用std::unordered_map而不是std::map的情况？
我知道它们之间的区别，比如内部实现、搜索元素的时间复杂性等等。
但是我真的找不到std::unordered_map不能被std::map取代的情况。
浏览 11提问于2022-01-06得票数 4
回答已采纳
查找是通过整数或字符串完成的。整数和字符串都保证在集合中是唯一的。集合的大小大约是这些对的500。
集合的接口将是两个函数，一个函数将整数转换为字符串，另一个函数将字符串转换为相应的整数。
似乎没有方法来捡起“适当”的容器。
一种方法是使用std::vector，这是默认的，因为它将存储在一个连续的内存中，所以我们确保缓存命中？但是我知道编译时集合的大小，所以std::array？
或者，由于顺序并不重要，但是查找需要很快，所以我们可以使用基于散列的解决方案，比如std::map？但关键是什么，价值是什么？或者一个人可以有2个std：：map (std::map<int，std::str
浏览 15提问于2022-11-30得票数 -1
为什么ArrayList add()和add( index，E)复杂度是摊销常数时间？
为什么O(1)用于单add()操作，O (n )用于单add(int index，E)操作，O(n)用于添加n个元素(n add操作)？假设我们很少使用add ( index，E)添加到数组末端？
数组(和ArrayList)的操作复杂性不是已经有n个元素的：
加()- O(1)？
添加(int索引，E) - O(n)？
如果我们做了一百万次插入，平均1和2不可能是O(1)，对吗？
甲骨文为什么说
添加操作运行在分期常数时间中，即添加n个元素需要O(n)时间。
I认为复杂性对于add
浏览 17提问于2017-07-20得票数 22
回答已采纳
3回答
int main()
{
auto n=0, sockNumber=0, pairs=0;
unordered_map<int, int> numberOfPairs;
cin >> n;
for(int i=0; i<n; ++i)
{
cin >> sockNumber;
numberOfPairs.insert({sockNumber, 0}); // >>>>>> HERE <<<<<<
浏览 7提问于2016-12-04得票数 2
回答已采纳
5回答
假设我想用字符串作为键来映射数据。我应该选择哪个容器，map还是unordered_map？unordered_map占用了更多的内存，所以让我们假设内存不是问题，问题是速度。
unordered_map一般给出的平均复杂度为O(1)，最坏情况为O(n)。在什么情况下它会达到O(n)？什么时候map比unordered_map更省时？当n很小时会发生这种情况吗？
假设我会使用STL unordered_map和默认的haser。地图。字符串是关键字。
如果我打算遍历元素而不是每次访问一个单独的元素，我应该选择map吗
浏览 2提问于2012-12-10得票数 94
回答已采纳
我得到了关于在C++中实现通用回忆录的内容。但是，正如有人在此注释中所指出的那样，原始代码进行了2次查找，而下面的代码只进行了一次查找。
template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func)
{
std::map<std::tuple<Args...>, ReturnType> cache;
return
浏览 1提问于2016-04-13得票数 1
回答已采纳
我想知道以下函数的复杂度。
我知道std::map是用红黑树实现的，插入的复杂度是O(logN)。
但是，如果我不断向一个空地图添加N个项目，我该如何计算呢？
void add(int N, std::map<int, int>& map) {
for (int i = 0; i < N; ++i) {
map[i] = i;
}
}
提前谢谢你，
浏览 0提问于2013-03-20得票数 2
回答已采纳
由于插入排序的时间复杂度是O(n^2)，那么桶排序O(n+k)在每个桶上使用插入排序时的平均案例时间复杂度是怎样的？这里k是桶的数目。
浏览 0提问于2019-02-21得票数 2
回答已采纳
1回答
我试图理解为什么Rabin算法最坏的运行时间是O(nm)，而平均情况是O(n+m)。
有人能帮我吗？
浏览 7提问于2016-09-09得票数 5
3回答
我正在学习不同的排序算法及其时间/空间复杂度，并看到冒泡排序和插入排序等算法的空间复杂度为O(1)。
这让我感到奇怪，因为最低的空间复杂度肯定是O(n) (例如，存储数据集所需的内存，仅此而已)？
浏览 1提问于2017-05-10得票数 7
回答已采纳
我试图将元素插入到unordered_map覆盖当前对位置的某个位置。我尝试了以下代码：
unordered_map<string, string>::iterator it = myMap.begin() + 256;
myMap.insert(it, newPair);
这是不工作的，因为它会留下一个错误。有人能帮忙吗？事先谢谢你。
浏览 0提问于2017-05-12得票数 1
回答已采纳
2回答
对于某些任务，是一个很好的数据结构。但是，我找不到任何关于执行查找的时间复杂度的信息。
我猜它与平均字长成线性关系，与图中的字数成对数关系。
那么它是O(L * log W)吗，其中W是单词的数量，L是平均单词长度？
浏览 3提问于2011-04-19得票数 1
回答已采纳
我手头有问题，可以通过以下两种方式解决。
if(...) //First if statement
for( i = 0; i < n; i++ ) //Loop over n elements
{ ... } //Some statement; Time Complexity O(1)
if(...) //Second if statement
for( i = 0; i < n; i++ ) //Loop over n elements
{ ... } //Some statement; Time Complexity
浏览 2提问于2016-01-18得票数 1
Map (或HashMap)需要恒定的时间来插入、删除和检索。虽然到目前为止我所知道的所有其他数据结构都不需要固定的时间，但它们用于上述操作的时间取决于输入的大小。
那么，为什么我们需要所有其他的数据结构呢？HashMap不是通用的数据结构吗？
浏览 0提问于2017-01-21得票数 1
回答已采纳
1回答
我正在学习AVL树。AVL树是通过旋转来平衡自身的二进制搜索树。因为它们是平衡的，所以查询时间是O(log )。但是添加条目的顺序对于避免每次插入的最坏情况O(log )旋转也很重要。
它的渐近运行时间是多少：
(a)在AVL树中添加n个具有连续键的条目(插入所有条目的时间，而不是每个条目)
b)搜索不在树中的关键字。
我所理解的是这个高度是O(log )，所以插入到AVL树中的最坏情况是O(log )。搜索AVL树完全不同于BST，因此也需要与树的高度成比例的时间，使得O(log )。
这是正确的吗？
浏览 0提问于2020-10-14得票数 0
我想知道在哪些用例中，我们可以通过拥有有序的关联容器来感兴趣。
换句话说，为什么使用std::map而不使用std::unorderd_map
浏览 1提问于2011-06-22得票数 2
回答已采纳
4回答
我不明白为什么我不能拥有一个以unordered_map作为关键类型的array<int,3>：
#include <unordered_map>
using namespace std;
int main() {
array<int,3> key = {0,1,2};
unordered_map< array<int,3> , int > test;
test[key] = 2;
return 0;
}
我犯了一个很长的错误，最相关的部分是
main.cpp:11:9: error: no ma
浏览 8提问于2017-03-09得票数 11
回答已采纳
ArrayList的大多数实现在内部使用一个数组，当在列表中添加元素时，该数组的大小已经耗尽，它通过执行以下操作来调整大小或“增长”：
使用新批新分配的memory.copying缓存新数组--将内部数组的所有元素放入新数组。将内部数组设置为新数组。将内部数组的设置索引N - 1设置为元素对象，其中N是数组的新大小。<code>f 211</code>
提供的解释是，增加列表对于您的平均添加操作来说是非常必要的，因此平均添加的时间复杂性是O(1)，因此是摊销的恒定时间。
我搞不懂这有什么意义。假设列表是由Q增长的。简单的算术系列将告诉您，如果我要将x元素添加到Array
浏览 3提问于2020-11-09得票数 1
回答已采纳
2回答
函数时间复杂度
、、、
在书中读到，调用子例程被认为是恒定时间操作，即使子例程本身不是在恒定时间内执行，而是取决于输入大小。如果我有下面这段代码：
void func(int m){
int n = 10;
subrout(m);//function which complexity depends on m
subrout2(n);//function which complexity depends on n
}
我想我可以认为func()是一个常数时间函数，例如O(1)？
如果我有这样的结果：
void func(){
int n = 10;
Type object;
o
浏览 5提问于2017-02-13得票数 0
1回答
对于一个算法的平均时间复杂度，您使用了什么符号？在我看来，正确的方法是使用大θ来引用一组结果(即使特定的尝试可能不同)。例如，平均数组搜索将是n+1(Θ)/2。
是这样的吗？
对平均搜索时间的解释是/2:在n个第一个整数的访问时间和为n(n+1)/2的情况下，大量随机访问数组的平均时间为(n (n+1)/2 )/n =(n+1)/2，在这种情况下，我认为Θ(n+1)/2将是平均访问时间。这(对我来说)很有意义，但由于我对渐近符号(以及一般的编程)还不熟悉，我想知道这是否是一种常见的做法。
我之所以问这个问题，是因为我很困惑地发现，在像http://bigocheatsheet.com这样的页面
浏览 0提问于2013-05-11得票数 1
回答已采纳
4回答
public void addOccurence(String word) {
if (hm.containsKey(word)){
hm.put(word, hm.get(word)+1);
}
else {hm.put(word, 1); }
}
我知道，平均而言，put(k,v)和get(v)以o(1)为例，他们的最坏情况是o(n)。那containsKey(v)呢？以及如何确定运行时间，如：
hm.put(word, hm.get(word)+1)
最坏的情况是o(n^2)，平均是o(1)吗？
浏览 6提问于2013-11-20得票数 2
回答已采纳
1回答
我已经创建了一个简单的程序，它使用无序映射保持数组中元素的计数。我想知道下面程序的时间复杂度。
是简单的O(n)时间吗？
无序映射上的操作需要多长时间？
(即在map中查找键，如果存在，则将其值递增1，如果不是，则将键初始化为1)
这是在固定时间、对数时间还是线性时间内完成的？
如果不是在固定的时间，那么请给我一个更好的方法。
#include <unordered_map>
#include<iostream>
int main()
{
int n;
std::cin >> n;
int arr[100];
浏览 1提问于2019-10-10得票数 1
因此，我有一个图(std::map)，它将字符串存储为键，值是字符串集(图中每个节点的邻接列表)：
std::map<std::string, std::set<std::string>> graph
我的插入代码很简单：
graph[from].insert(to)，其中既是字符串，也是字符串。因此，我将插入到一组与键from相关联的字符串中。
对于这个插入位的平均和最坏的时间复杂度，我认为它们是O(x*log(V) * y*log(n))，其中x是字符串的长度，y是字符串的长度，V是图中的节点数，n是图中的边数(我包括字符串长度，因为我认为我们还必须考虑std::s
浏览 14提问于2022-10-21得票数 -1
回答已采纳
1回答
下面我附上了一个代码块。请告诉我下面的代码是如何有O(n)时间运行时间的。
def _height2(self, p):
if self.is_leaf(p):
return 0
else:
return 1 + max(self._height2(c) for c in self.children(p))
我不明白它在O(n)时间复杂度中是如何工作的。请帮我学一下。
浏览 4提问于2020-09-14得票数 0
回答已采纳
vector<int> topKFrequent(vector<int>& nums, int k) {
if(k==nums.size())
return nums;
map<int,int> mp;
for(int i=0;i<nums.size();i++)
mp[nums[i]]++;
multimap<int,int> m;
for(auto& it:mp){
m.insert({it.second,it.first});
浏览 8提问于2022-04-25得票数 -1
回答已采纳
1回答
以下代码的时间复杂度是多少？
def func(n):
for _ in range(n):
if n == 4:
for _ in range(n):
<do something>
对于一个特定的输入(n = 4)，它将只是O(n^2)，但对于所有其他输入，它将是O(n)。在这种情况下，最坏的情况显然是O(n^2)，但我的讲师说O(n)是正确的答案。如果"big-Oh“符号表示的是最坏的情况，为什么它不是O(n^2)？
另一个是：
def func2(n):
for _ in rang
浏览 0提问于2014-04-01得票数 1
我知道如何单独计算快速排序和插入排序的复杂度，但当我混合使用这两种排序时…
代码如下：
#define THRESHOLD 50
// regular insertion sort
void isort(int *array, size_t n) {
int key, i, j;
for(j = 1; j < n; j++){
key = array[j];
i = j - 1;
while (array[i] > key && i>=0) {
array[i + 1] = array[i];
i--;
浏览 0提问于2016-10-20得票数 0
如果我们测量一个数组的时间复杂度，我们可以在时间复杂度计算中忽略不同的数组吗？(即如果我们只关心外部数组的增长，我可以说是O(N)，还是必须给出总的时间复杂度O(N*M)。
for (int i = 0; i <= n.size(); ++i) {
// codes inside the body of outer loop
for (int j = 0; j <= m.size(); ++j) {
// codes inside the body of both outer and inner loop
}
}
浏览 0提问于2020-09-22得票数 0
4回答
快速排序时间复杂度
、、、、
我最近读到了关于时间复杂性的文章，我发现快速排序的平均时间复杂度为O(nlog(n))。
问题1:我不明白的是，日志(N)是如何在时间复杂性方程中出现的？
问题2:为什么我们总是使用大O表示法来寻找算法的时间复杂性？我们为什么不用其他符号呢？
浏览 7提问于2012-08-15得票数 1
回答已采纳
2回答
据我理解，hashmap插入是O(1)，对于数组列表，插入是O(n)，因为对于hashmap，哈希函数计算哈希码和索引，并插入条目，数组列表每次输入新元素时都会进行比较。
浏览 3提问于2015-05-06得票数 2
回答已采纳
2回答
我曾经相信，unordered_map在时间复杂度上比C++中的地图要好。但今天，当我做一个问题(莫莉的化学品)，我有超过时间限制。经过大量的猜测(因为我认为我的解决方案是正确的)，我尝试使用一个映射而不是一个unordered_map，令人惊讶的是，我得到了accepted.In，在某些情况下，由于大量的碰撞，unordered_map可以有一个很大的常数乘数，这将使它的实际复杂度增加到比一个映射的复杂度更高(欢迎进行更正)。
我搜索了很多关于不同time complexity的functions of maps and unordered maps，但我没有找到合适的内容，因为我想知道什么
浏览 0提问于2020-08-21得票数 0
回答已采纳
通过摊销分析，我们知道用N方法插入StringBuilder#append需要花费O(N)时间。但这就是我迷路的地方。考虑一下，inputString是来自用户的输入字符串。
for (int i = 0; i < N; i++) {
s.append(inputString);
// where s is an empty StringBuilder object at the beginning
// and inputString is the string that is taken from the user
}
这是否应该具有O(inputString.
浏览 0提问于2019-06-27得票数 6
回答已采纳
我知道如果我有一个依赖于N个元素的嵌套循环，那么它的时间复杂度将是O(N^2)。 在这种情况下，我有一个固定大小的循环，嵌套在一个N循环中，如下所示： while (i < N)
while (j < 1000){
// code //
j++;
}
i++;
} 这里的时间复杂度是多少？它不是O(N^2)，但我不知道它是O(N)还是介于两者之间的某个东西。在我看来，它不是线性的。T
浏览 14提问于2020-09-21得票数 1
在Python语言中可以将字典视为C++中的地图
而插入复杂度是恒定时间？那么字典的排序复杂度又如何呢？那么迭代呢？
需要一些好的观点或链接到好的资源。
谢谢!
浏览 3提问于2011-03-31得票数 0
回答已采纳
1回答
最快的预打包键值对搜索
、、、、
我想用c++ (伪代码)实现以下数据结构：
Map<Integer, Integer> // Key->Value pairs
Map.put(1,6);
Map.put(2,5);
Map.put(6,89);
Map.put(7,23);
... etc ...
Map.get(2) .... returns 5
换句话说，给定一对整数，其中一个是查找键，那么让我从其中一个键检索值的最快的库实现是什么？不需要对Value->Key进行相反的搜索。
这张地图的大小可能在10000个元素的数量级上。
我假设二叉树搜索将产生最快的查找时间？std:map是最好的
浏览 2提问于2011-03-10得票数 0
回答已采纳
对于像std::set和std::map这样的数据类型，在对数时间内进行查找，是否需要实现来维护begin和end迭代器？访问begin和end是否意味着可以在对数时间内进行查找？
我一直认为开始和结束总是发生在恒定的时间内，但是我在Josuttis中找不到任何证实这一点的地方。现在我正在做一些我需要对性能进行分析的事情，我想确保覆盖我的基础。
谢谢
浏览 4提问于2008-09-17得票数 8
回答已采纳
1回答
我在Python3.9中解决了Euler项目中的this问题。有一件事引起了我的注意，那就是使用set比使用list的性能更好。 ? 上图显示了set和list的时间与项目数的关系。列表时间呈指数增长，而集合的性能相对恒定。 我的问题是，为什么当项数增加时，list的性能会很差，而sets的性能却相当稳定？ 下面是我的代码： from time import perf_counter
import matplotlib.pyplot as plt
def using_set(limit):
seq = set()
for i in range(2,limit):
浏览 14提问于2021-07-23得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
