Java Hash Map containsValue的时间复杂度是多少呢

这是它的源码:

 public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

是在遍历数组里先得到头节点,然后再遍历链表得到value,,时间复杂度是O(n)还是O(n²)

6个回答

介于O(n)和O(n²)之间,更接近于O(n),取决于key的hash重合度,如果所有的value都分布于单独的key,则复杂度就是O(n)。

肯定是O(n²),因为需要先循环出key 才能得到key封装的值。

O(n²),先循环key,在取的value,底层也是用equals比较!

楼主可以先去读hashmap的put方法的源码 了解一下HashMap的数据结构

james_zhg 正解

你得看这个数据长啥样
这样的话
0 1 2数组长3每个位置链表长3
0 0 0
1 1 1
2 2 2
是O(n²)

或者数组长9每个位置链表长1
0 1 2 3 4 5 6 7 8 9
是O(n)

因为是要key的hash值一样的数据才回放到链表中
所有一般O(n²)是不会出现的,比较接近O(n)

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
密码学哈希函数生日攻击的存储复杂度是多少??

密码学哈希函数生日攻击的存储复杂度是多少???以及生日攻击的原理和证明 。。求!!!

java hashmap集合如何最优的去除value为null或空的元素

java hashmap集合如何最优的去除value为null或空的元素

hash_map 自定义hash函数出错

最近在使用hash_map 的时候发现不能自定义hash 函数,只要这样的话,就会出问题,hash_map<const char*, int, hash<const char*>, eqstr> day ;但是如果这样的话就不会有问题了,还望大神求解呀 hash_map<const char*, int> days; #include<iostream> #include<hash_map> #include<string> using namespace std; struct eqstr //定义比较函数,字符串的比较函数需要单独定义 { bool operator()(const char* a1, const char* a2) const { return strcmp(a1,a2)==0; } }; int main() { hash_map<const char*, int, hash<const char*>, eqstr> days; days["january1"] = 31; days["january2"] = 41; days["january3"] = 61; days["january4"] = 51; hash_map<const char*, int, hash<const char*>, eqstr>::iterator ite1=days.begin(); hash_map<const char*, int, hash<const char*>, eqstr>::iterator ite2 = days.end(); for (; ite1 != ite2; ++ite1) { cout << ite1->first << endl; } system("pause"); return 0; } ``` ``` ![图片说明](https://img-ask.csdn.net/upload/201803/18/1521363288_472206.jpg) 。

std::map和stdext::hash_map效率问题

近期,接到一个项目,由于需要在程序运行中解析一部分数据,且该部分数据需要向后提供。 所以前同事在设计时使用了stdext::hash~map。 近期在优化该程序,需要将处理能力提高100%,我从IO,队列锁等方面改了一大通,现在效率才提高50%。 所以想问下经验较多的人,map和hash~map效率到底差距有多少(结合我的使用场景)。 1、每个map(hash~map)最多只有100个数据,键值为string std::map<string, MyDataStruct> 键值长度4~30个字符不等,且会存在汉语(会影响效率吗) 2、每个处理逻辑map均会重新构建, 两者插入效率是否差异较大。 3、查询效率,该部分自己已经写代码测试过。两者效率(vs2008+STLport)差异不大,查询10万次hash~map约少个1毫秒。(GetTicketCount()); 由于现在想知道,但是手头没有电脑,没法测试,想问下大家具体的经验。最好是自己做过实验的。

在map中,如何找出value的最大值

如何找出value.得最大值,并且根据value的最大值返回对应的key值

关于intel TBB里的concurrent_hash_map里的find方法

最近用到了intel TBB里的concurrent_hash_map里的bool find( accessor& result, const Key& key ),我在if语句里判断了之后,可是发现好像进去了find函数之后就出不来了,有人直到是为什么吗,跪求大神们赐教。 代码如下: bool ThreadSafeLRUCache<TKey, TValue, THash>:: setTValue(const TKey& key,TValue& value) { HashMapAccessor hashAccessor; printf("enter setvalue\n"); if(!m_map.find(hashAccessor, key)){ printf("return false\n"); return false; } printf("left setvalue"); void *ptemp; // Acquire the lock, but don't block if it is already held std::unique_lock<ListMutex> lock(m_listMutex, std::try_to_lock); if (lock) { printf("enter lock\n"); ptemp = hashAccessor->second.m_value.value; hashAccessor->second.m_value = value; lock.unlock(); printf("left lock\n"); } scalable_free(ptemp); return true; }

hash_map,unordered_map以string作为键,插入一千多万条数据后崩溃

代码: #include "stdafx.h" #include"iostream" #include<string> #include<map> #include<sstream> #include<time.h> #include<hash_map> using namespace std; typedef hash_map<string, double> myMap; void CharsAllSequen(myMap &resultMap, string &str, unsigned int n, double defaultVal); void Clear0ForStrQuen(myMap &resultMap); int main() { myMap totalMap; myMap resultMap; string str; CharsAllSequen(resultMap, str, 6, 0.00323223); stringstream ss; for (int i = 0; i < 3000; i++) { myMap::iterator iter; for (iter = resultMap.begin(); iter != resultMap.end(); ++iter) { string strTemp = iter->first; ss.str(""); ss.clear(); ss << "_"; ss << i; strTemp += ss.str(); totalMap.insert(myMap::value_type(strTemp, iter->second + i / 3001.0)); } } return 0; } void Clear0ForStrQuen(myMap &resultMap) { myMap::iterator iter = resultMap.begin(); while (iter!=resultMap.end()) { iter->second = 0; ++iter; } } //获取特定长度,由0,1,2,3四个字符组成的字符串,比如010203,作为key,值设置为defaultVal void CharsAllSequen(myMap &resultMap, string &str, unsigned int n, double defaultVal) { if (n==0) { if (str.size()>0) { resultMap.insert(myMap::value_type(str, defaultVal)); } else { return; } } else { for (int i = 0; i < 4; i++) { stringstream ss; ss << i; string temp = ss.str(); str.append(temp); CharsAllSequen(resultMap, str, n - 1, defaultVal); str = str.substr(0, str.size() - 1); } } } ![图片说明](https://img-ask.csdn.net/upload/201603/30/1459321907_516343.png)

redis如何批量更新HASH表value值?

redis如何批量更新HASH表value值? 不使用Java代码的情况下,单纯利用redis自身功能, 如何实现批量更新HASH表value值? 请教各位老师,谢谢。

关于#include<ext/hash_map>问题

In file included from /usr/include/c++/4.8/ext/hash_map:60:0, from AlgorithmNBM.h:9, from AlgorithmNBM.cpp:10: /usr/include/c++/4.8/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. [-Wcpp] #warning \ ^ 求大神相助,急,谢谢!!!

java 不明白HashSet的查询效率比数组高是怎么实现的?

HashSet的查询效率比数组高?

java中map的hashmap的用法

创建对象并加入到hashmap中,若想查找hashmap中某个对象的某个属性是否存在如何查找

java求几个hashmap中key的并集,输出value

现有几个hashmap,可能有相同的key,但是value不同,求key的并集, 并输出在不同hashmap中的不同value,若不存在则为-1 比如hashmap1{(我,1),(你,2),(他,3),(它,4)} hashmap2{(猴,1)(狗,3)(你,4)(他,5)} hashmap3{(猴,10)(牛,2)(狗,5)(猪,4),(它,8)} hashmap4{(我,5),(牛,6)} 输出为 key hashmap1 hashmap2 hashmap3 hashmap4 我 1 -1 -1 5 你 2 4 -1 -1 他 3 5 -1 -1 它 4 -1 8 -1 猴 -1 1 10 -1 狗 -1 3 5 -1 牛 -1 -1 2 6 猪 -1 -1 4 -1

Key是字符串时如何获取hash值

大神们,想请教一下,获取hash值的时候,是根据key的首个字符(王)还是整个key(王磊)来计算出hash值? ``` public static void main(String[] args) { HashMap<String,Integer> h = new HashMap<>(); h.put("王磊", 20); h.put("王大", 30); h.put("小红", 21); h.put("小青", 27); h.put("王二", 18); h.put("陈红", 30); System.out.println(h); ```

java Hash表的添加,访问

如何构造一个哈希表,然后对它执行元素的添加、访问等哈希表操作。求附录相关哈希表的方法,最好是带注释的。

php 的 hash('sha256', 'zxzxzx',true); 对应 java是啥?

php 的 hash('sha256', 'zxzxzx',true); 对应 java是啥?

关于Json value值取消双引号问题

我现在需要获得一个Json,格式如下: var data_d = {"id":"root","text":"根节点","isExpand":"true","childNodes":[{"id":"org1","text":"软件","showCheck":"true"}]}; 其中:childNodes对应是一个数组,[{value}],需要这样的格式。 我在后台处理的代码如下: Map<String,Object> map = new HashMap<String,Object>(); map.put("id", "root"); map.put("text", "根节点"); map.put("isExpand", "true"); map.put("childNodes", "["+hmap()+"]"); private static Map<String,Object> hmap(){ Map<String,Object> map = new HashMap<String,Object>(); map.put("id", "root"); map.put("text", "根节点"); map.put("showCheck",true); return map; } String map2 = mapToJson(map); 打印出来的结果是: [json]: [{"id":"root","text":"根节点","isExpand":"true","childNodes":"[{id\u003droot, text\u003d根节点, showCheck\u003dtrue}]"}] 格式不符合,换一种,直接用json: JSONObject json = new JSONObject(); json.put("id", "root"); json.put("text", "根节点"); json.put("isExpand", "true"); json.put("childNodes", "["+con2List().toString().replace("\"", "'")+"]"); private static JSONObject con2List() throws JSONException{ JSONObject jo = new JSONObject(); jo.put("id", "org1"); jo.put("text", "软件"); jo.put("showCheck", "true"); return jo; } 打印出来的结果是: [json]: {"id":"root","text":"根节点","isExpand":"true","childNodes":"[{'id':'org1','text':'软件','showCheck':'true'}]"} 格式也不符合,childNodes对应的是:"[{value}]",多了双引号。 有人说这个是标准的json格式,但是我需要的就是开头那样的格式,json也好,string也好都可以。 求大神来解答。

java的集合 链表和hash表问题

刚刚看了java集合 有些不懂的地方 链表为什么有利于增删 hash表为什么有利于改查

HashMap建立索引的Java问题

有几句话类似于s1=....;s2=......;s3=.....;能够实现输出其中的单词并显示在哪句话中,利用hashmap的技术

Java concurrentHashmap 如何进行分段遍历操作

Java concurrentHashmap 如何进行分段遍历操作 如: concurrentHashmap存了1000条数据; 如何分10次,每次100条进行遍历操作 群里大神提到一种方案: 对长连接进行hash取模,分布在不同的hashmap 我的补充: 如果我想支持50万并发,就一次性的初始化500个hashmap,放到list中 对每个长连接取模,放到对应下标的hashmap中

如果能重来,我不会选择北漂——初见北京

一个人走的路

技术大佬:我去,你写的 switch 语句也太老土了吧

昨天早上通过远程的方式 review 了两名新来同事的代码,大部分代码都写得很漂亮,严谨的同时注释也很到位,这令我非常满意。但当我看到他们当中有一个人写的 switch 语句时,还是忍不住破口大骂:“我擦,小王,你丫写的 switch 语句也太老土了吧!” 来看看小王写的代码吧,看完不要骂我装逼啊。 private static String createPlayer(PlayerTypes p...

副业收入是我做程序媛的3倍,工作外的B面人生是怎样的?

提到“程序员”,多数人脑海里首先想到的大约是:为人木讷、薪水超高、工作枯燥…… 然而,当离开工作岗位,撕去层层标签,脱下“程序员”这身外套,有的人生动又有趣,马上展现出了完全不同的A/B面人生! 不论是简单的爱好,还是正经的副业,他们都干得同样出色。偶尔,还能和程序员的特质结合,产生奇妙的“化学反应”。 @Charlotte:平日素颜示人,周末美妆博主 大家都以为程序媛也个个不修边幅,但我们也许...

我说我不会算法,阿里把我挂了。

不说了,字节跳动也反手把我挂了。

2020年大厂Java面试前复习的正确姿势(800+面试题答案解析)

前言 个人觉得面试也像是一场全新的征程,失败和胜利都是平常之事。所以,劝各位不要因为面试失败而灰心、 丧失斗志。也不要因为面试通过而沾沾自喜,等待你的将是更美好的未来,继续加油! 本篇分享的面试题内容包括:Java、MyBatis、ZooKeeper、Dubbo、Elasticsearch、Redis、MySQL、Spring、SpringBoot、SpringCloud、RabbitMQ...

抖音上很火的时钟效果

反正,我的抖音没人看,别人都有几十万个赞什么的。 发到CSDN上来,大家交流下~ 主要用到原生态的 JS+CSS3。 具体不解释了,看注释: &lt;!DOCTYPE html&gt; &lt;html lang="en"&gt; &lt;head&gt; &lt;meta charset="UTF-8"&gt; &lt;title&gt;Title&lt;/tit...

记录下入职中软一个月(外包华为)

我在年前从上一家公司离职,没想到过年期间疫情爆发,我也被困在家里,在家呆着的日子让人很焦躁,于是我疯狂的投简历,看面试题,希望可以进大公司去看看。 我也有幸面试了我觉得还挺大的公司的(虽然不是bat之类的大厂,但是作为一名二本计算机专业刚毕业的大学生bat那些大厂我连投简历的勇气都没有),最后选择了中软,我知道这是一家外包公司,待遇各方面甚至不如我的上一家公司,但是对我而言这可是外包华为,能...

又出事了?网站被攻击了?高中生?

北京时间2020年3月27日9点整,如往常一样来到公司,带开电脑,正准备打开Github网站看一会源代码,再开始手头的工作。哟吼,一直打不开,一直出现如下页面: 我想很多网友也尝到了甜头,各大技术群炸开了锅,据网友反馈有攻击者正在发起大规模的中间人挟持,京东和Github等网站等网站都受到了影响。 什么是中间中间人挟持呢? 简而言之,就是攻击者在数据网络传输的过程中,截获传输过程中的数据并篡改...

培训班出来的人后来都怎么样了?(二)

接着上回说,培训班学习生涯结束了。后面每天就是无休止的背面试题,不是没有头脑的背,培训公司还是有方法的,现在回想当时背的面试题好像都用上了,也被问到了。回头找找面试题,当时都是打印下来天天看,天天背。 不理解呢也要背,面试造飞机,上班拧螺丝。班里的同学开始四处投简历面试了,很快就有面试成功的,刚开始一个,然后越来越多。不知道是什么原因,尝到胜利果实的童鞋,不满足于自己通过的公司,嫌薪水要少了,选择...

面试了一个 31 岁程序员,让我有所触动,30岁以上的程序员该何去何从?

最近面试了一个31岁8年经验的程序猿,让我有点感慨,大龄程序猿该何去何从。

大三实习生,字节跳动面经分享,已拿Offer

说实话,自己的算法,我一个不会,太难了吧

程序员垃圾简历长什么样?

已经连续五年参加大厂校招、社招的技术面试工作,简历看的不下于万份 这篇文章会用实例告诉你,什么是差的程序员简历! 疫情快要结束了,各个公司也都开始春招了,作为即将红遍大江南北的新晋UP主,那当然要为小伙伴们做点事(手动狗头)。 就在公众号里公开征简历,义务帮大家看,并一一点评。《启舰:春招在即,义务帮大家看看简历吧》 一石激起千层浪,三天收到两百多封简历。 花光了两个星期的所有空闲时...

工作八年,月薪60K,裸辞两个月,投简历投到怀疑人生!

近日,有网友在某职场社交平台吐槽,自己裸辞两个月了,但是找工作却让自己的心态都要崩溃了,全部无果,不是已查看无回音,就是已查看不符合。 “工作八年,两年一跳,裸辞两个月了,之前月薪60K,最近找工作找的心态崩了!所有招聘工具都用了,全部无果,不是已查看无回音,就是已查看不符合。进头条,滴滴之类的大厂很难吗???!!!投简历投的开始怀疑人生了!希望 可以收到大厂offer” 先来看看网...

我把华为小米年报放一起,发现华为才是真·手机公司,小米确实不靠卖手机赚钱...

郭一璞 发自 凹非寺量子位 报道 | 公众号 QbitAI国产手机界的两大玩家,华为&amp;小米,昨天在同一天前后脚发布了2019年财报。同行冤家,发财报也碰在了同一天。那我们就对比...

大牛都会用的IDEA调试技巧!!!

导读 前天面试了一个985高校的实习生,问了他平时用什么开发工具,他想也没想的说IDEA,于是我抛砖引玉的问了一下IDEA的调试用过吧,你说说怎么设置断点...

97年世界黑客编程大赛冠军作品(大小仅为16KB),惊艳世界的编程巨作

这是世界编程大赛第一名作品(97年Mekka ’97 4K Intro比赛)汇编语言所写。 整个文件只有4095个字节, 大小仅仅为16KB! 不仅实现了3D动画的效果!还有一段震撼人心的背景音乐!!! 内容无法以言语形容,实在太强大! 下面是代码,具体操作看最后! @echo off more +1 %~s0|debug e100 33 f6 bf 0 20 b5 10 f3 a5...

不要再到处使用 === 了

我们知道现在的开发人员都使用 === 来代替 ==,为什么呢?我在网上看到的大多数教程都认为,要预测 JavaScript 强制转换是如何工作这太复杂了,因此建议总是使用===。这些都...

什么是a站、b站、c站、d站、e站、f站、g站、h站、i站、j站、k站、l站、m站、n站?00后的世界我不懂!

A站 AcFun弹幕视频网,简称“A站”,成立于2007年6月,取意于Anime Comic Fun,是中国大陆第一家弹幕视频网站。A站以视频为载体,逐步发展出基于原生内容二次创作的完整生态,拥有高质量互动弹幕,是中国弹幕文化的发源地;拥有大量超粘性的用户群体,产生输出了金坷垃、鬼畜全明星、我的滑板鞋、小苹果等大量网络流行文化,也是中国二次元文化的发源地。 B站 全称“哔哩哔哩(bilibili...

十个摸鱼,哦,不对,是炫酷(可以玩一整天)的网站!!!

文章目录前言正文**1、Kaspersky Cyberthreat real-time map****2、Finding Home****3、Silk – Interactive Generative Art****4、Liquid Particles 3D****5、WINDOWS93****6、Staggering Beauty****7、Ostagram图片生成器网址****8、全历史网址*...

终于,月薪过5万了!

来看几个问题想不想月薪超过5万?想不想进入公司架构组?想不想成为项目组的负责人?想不想成为spring的高手,超越99%的对手?那么本文内容是你必须要掌握的。本文主要详解bean的生命...

毕业5年,我熬夜整理出了这50个优质的电子书网站,吐血推荐!

大家好,我是武哥,最近经常有小伙伴问我要电子书,都什么年代了,还找不到电子书吗?如果要说原因,那就是你还没遇到武哥我(手动滑稽~)!我今天把这么多年我经常看的电子书网站整理一下给大家,基本上能解决大家的需求。不管是在校生还是已经工作了,相信肯定对你有所帮助! 1.鸠摩搜书 首先给大家推荐的网站是:鸠摩搜书 地址:https://www.jiumodiary.com/ 这个网上非常棒,上面有很多优质...

MySQL性能优化(五):为什么查询速度这么慢

前期回顾: MySQL性能优化(一):MySQL架构与核心问题 MySQL性能优化(二):选择优化的数据类型 MySQL性能优化(三):深入理解索引的这点事 MySQL性能优化(四):如何高效正确的使用索引 前面章节我们介绍了如何选择优化的数据类型、如何高效的使用索引,这些对于高性能的MySQL来说是必不可少的。但这些还完全不够,还需要合理的设计查询。如果查询写的很糟糕,即使表结构再合理、索引再...

大厂的 404 页面都长啥样?最后一个笑了...

每天浏览各大网站,难免会碰到404页面啊。你注意过404页面么?猿妹搜罗来了下面这些知名网站的404页面,以供大家欣赏,看看哪个网站更有创意: 正在上传…重新上传取消 腾讯 正在上传…重新上传取消 网易 淘宝 百度 新浪微博 正在上传…重新上传取消 新浪 京东 优酷 腾讯视频 搜...

自从喜欢上了B站这12个UP主,我越来越觉得自己是个废柴了!

不怕告诉你,我自从喜欢上了这12个UP主,哔哩哔哩成为了我手机上最耗电的软件,几乎每天都会看,可是吧,看的越多,我就越觉得自己是个废柴,唉,老天不公啊,不信你看看…… 间接性踌躇满志,持续性混吃等死,都是因为你们……但是,自己的学习力在慢慢变强,这是不容忽视的,推荐给你们! 都说B站是个宝,可是有人不会挖啊,没事,今天咱挖好的送你一箩筐,首先啊,我在B站上最喜欢看这个家伙的视频了,为啥 ,咱撇...

代码注释如此沙雕,会玩还是你们程序员!

某站后端代码被“开源”,同时刷遍全网的,还有代码里的那些神注释。 我们这才知道,原来程序员个个都是段子手;这么多年来,我们也走过了他们的无数套路… 首先,产品经理,是永远永远吐槽不完的!网友的评论也非常扎心,说看这些代码就像在阅读程序员的日记,每一页都写满了对产品经理的恨。 然后,也要发出直击灵魂的质问:你是尊贵的付费大会员吗? 这不禁让人想起之前某音乐app的穷逼Vip,果然,穷逼在哪里都是...

总结了Mybatis,原来知识点也没多少嘛

看完这篇Mybatis,感觉你三天就会用了。

爬虫(101)爬点重口味的

小弟最近在学校无聊的很哪,浏览网页突然看到一张图片,都快流鼻血。。。然后小弟冥思苦想,得干一点有趣的事情python 爬虫库安装https://s.taobao.com/api?_ks...

疫情后北上广深租房价格跌了吗? | Alfred数据室

去年3月份我们发布了《北上广深租房图鉴》(点击阅读),细数了北上广深租房的各种因素对租房价格的影响。一年过去了,在面临新冠疫情的后续影响、城市尚未完全恢复正常运转、学校还没开学等情况下...

面试官给我挖坑:a[i][j] 和 a[j][i] 有什么区别?

点击上方“朱小厮的博客”,选择“设为星标”后台回复&#34;1024&#34;领取公众号专属资料本文以一个简单的程序开头——数组赋值:int LEN = 10000; int[][] ...

在拼多多上班,是一种什么样的体验?我心态崩了呀!

之前有很多读者咨询我:武哥,在拼多多上班是一种什么样的体验?由于一直很忙,没抽出时间来和大家分享。上周末特地花点时间来写了一篇文章,跟大家分享一下拼多多的日常。 1. 倒时差的作息 可能很多小伙伴都听说了,拼多多加班很严重。这怎么说呢?作息上确实和其他公司有点区别,大家知道 996,那么自然也就能理解拼多多的“11 11 6”了。 所以当很多小伙伴早上出门时,他们是这样的: 我们是这样的: 当...

相关热词 c# 按行txt c#怎么扫条形码 c#打包html c# 实现刷新数据 c# 两个自定义控件重叠 c#浮点类型计算 c#.net 中文乱码 c# 时间排序 c# 必备书籍 c#异步网络通信
立即提问