Question

Java HashMap 复杂度的问题

Java HashMap 中 get(Object key) 时间复杂度是O(1)这个应该没有疑问对吧,可是containsKey(Object key) 和containsValue(Object value) 复杂度是多少呢? 是O(1)还是O(n)还是都不是,能简单说一下他搜索原理吗?谢谢!

Answer 1

containsKey的复杂度是O(1)，它是直接根据给定的参数key来计算hashcode，看看相关位置上是否有。如果相关位置已被占用，就继续寻找下一个位置。下面是JDK实现containsKey的主要代码：
int hash = hash(k);
int i = indexFor(hash, table.length);
Entry e = table[i];
while (e != null) {
if (e.hash == hash && eq(k, e.key))
return true;
e = e.next;
}
containsValue的复杂度是O(n)，对于hashmap，value是依赖于key的，所以只能遍历整个集合。以下是JDK实现的主要代码：
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;

Answer 2

原则上时间复杂度同意楼上的.不过个人理解HashMap的时间复杂度取决于链表中元素的个数。其实就是和放在map里元素key的hashcode有关~设计的不好的话可能时间复杂度会增加~不过理想状态下以上三种就是:O(1),O(1),O(n)

Answer 3

第一个是O(n)，因为是遍历整个集合 ，第二个是O(m*n)，看他们提供的源码实现就可知道，两重for循环