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

Question

如题所述

Answer 1

与数量无关，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源码实现

Answer 2

数量基本上不会影响查询效率

但是会占很大内存