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

左正在杭州_116726
  • 18

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

回复
阅读 16.7k
4 个回答

与数量无关,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) 若那个位置上已经有一个链表(发生冲突),则遍历检查equals,若有相等则修改相应的Entry,否则接到链表尾端
3) 若位置上无链表则作为链表头存储

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

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

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

其实影响因素有很多的,包括:key的类型、value的类型、堆大小等等,而且这个查询效率得有个容忍值吧,“不影响查询效率”这句话太飘渺了。

_声_远_
  • 1
新手上路,请多包涵

HashMap操作的时间复杂度是O(1),也就是常数,所以它和key的多少没有关系。
你可以先找点资料看看Hash算法的基本概念。

小木子叔
  • 1
新手上路,请多包涵

跟多少没有关系,key的数量补超过占整个集合的60%到70% 这个比例,查询速度是最佳的

你知道吗?

宣传栏