您好,匿名用户

java HashMap 最多放多少个key 不影响查询效率

0 投票

java HashMap 最多放多少个key 不影响查询效率 数量级是多少?

用户头像 提问 2012年 12月1日 @ Dionysus 下士 (574 威望)
分享到:

1个回答

0 投票

与数量无关,HashMap读取性能主要取决于放入HashMap中的key对象的hashCode方法的实现,即此方法返回值导致的Hash冲突的比例,冲突越多,性能越差。

解释一下。楼上有人说HashMap时间复杂度为O(1),这是理想情况;说与值大小和堆大小相关……属于扯谈。java.util.HashMap的实现是一个标准的hash表+链表结构:
1. HashMap中持有一个数组成员变量table
2. table的每个元素都是一个链表(用于解决冲突)
3. 链表的每个元素Entry都存储着一对key/value

当执行HashMap.put(key, value)的时候:
1) HashMap会根据key.hashCode()方法来决定这一对key/value存储在数组table中的位置
2) 若那个位置上已经有一个链表(发生冲突),则接到链表尾端,否则作为链表头存储

那么当执行HashMap.get(key)的时候,查询过程也是一样的两步:
1) 根据key.hashCode()方法确定在table中的位置
2) 遍历所在位置的链表,若找到equals的key则返回,否则返回null

综上所述,第一步时间复杂度是O(1),第二步却是O(n)(n指链表长度)。所以key.hashCode()导致产生冲突的数量决定了这张HashMap的查询性能

详细情况可以参见java.util.HashMap源码实现

用户头像 回复 2012年 12月1日 @ Wukong 上士 (1,535 威望)
提一个问题:

相关问题

0 投票
1 回复 78 阅读
0 投票
1 回复 85 阅读
0 投票
0 回复 16 阅读
0 投票
1 回复 24 阅读

欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。
温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。

欢迎访问随意问技术百科,为了给您提供更好的服务,请及时反馈您的意见。
...