在Java中HashMap.containsKey（）的时间复杂度是多少？

I need to know: What is the time complexity of HashMap.containsKey() in java?

我需要知道：java中HashMap.containsKey（）的时间复杂度是多少？

4 个解决方案

#1

From the API doc ofHashMap:

来自HashMap的API文档：

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

假设散列函数在桶之间正确地分散元素，该实现为基本操作（get和put）提供了恒定时间性能。

Since containsKey() is just a get() that throws away the retrieved value, it's O(1) (assuming the hash function works properly, again).

由于containsKey（）只是抛出检索值的get（），因此它是O（1）（假设哈希函数再次正常工作）。

#2

Generally O(1), but if we're using a bad hashCode function, we need to add multiple elements to one bucket so it can be O(n) in worst case.

通常是O（1），但是如果我们使用一个糟糕的hashCode函数，我们需要将多个元素添加到一个桶中，因此在最坏的情况下它可以是O（n）。

#3

It is O(1) in general, however in worst case it is O(n)

一般是O（1），但最坏的情况是O（n）

 public boolean containsKey(Object key) {
  352           return getEntry(key) != null;
  353       }
  354   
  355       /**
  356        * Returns the entry associated with the specified key in the
  357        * HashMap.  Returns null if the HashMap contains no mapping
  358        * for the key.
  359        */
  360       final Entry<K,V> getEntry(Object key) {
  361           int hash = (key == null) ? 0 : hash(key.hashCode());
  362           for (Entry<K,V> e = table[indexFor(hash, table.length)];
  363                e != null;
  364                e = e.next) {
  365               Object k;
  366               if (e.hash == hash &&
  367                   ((k = e.key) == key || (key != null && key.equals(k))))
  368                   return e;
  369           }
  370           return null;
  371       }

#4

The time complexity of containsKey has changed in JDK-1.8, as others mentioned it is O(1) in ideal cases. However, in case of collisions where the keys are Comparable, bins storing collide elements aren't linear anymore after they exceed some threshold called TREEIFY_THRESHOLD, which is equal to 8,

containsKey的时间复杂度在JDK-1.8中已经改变，正如其他人提到的在理想情况下它是O（1）。但是，如果键是可比较的碰撞，存储碰撞元素的箱子在超过一个名为TREEIFY_THRESHOLD的阈值后不再是线性的，等于8，

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

In other word, TreeNodes will be used (similar to those in TreeMap) to store bins, (ie: a Red-Black tree structure) and this leaves us with an O(lgn) complexity in-case of collisions.

换句话说，将使用TreeNodes（类似于TreeMap中的那些）来存储箱（即：红黑树结构），这使得我们在碰撞的情况下具有O（lgn）复杂度。

The same applies for get(key) where where both methods call getNode internally

这同样适用于get（key），其中两个方法都在内部调用getNode

Note: n here is the size of the bin and not the HashMap

注意：这里的n是bin的大小而不是HashMap

#1