java中HashMap.containsKey()的时间复杂度是多less?

我需要知道:java中HashMap.containsKey()的时间复杂度是多less?

从HashMap的API doc of

这个实现为基本操作(get和put)提供了恒定的性能,假设散列函数在桶之间正确分散元素。

因为containsKey()只是一个get()函数,它将丢失检索到的值,它是O(1)(假设hash函数再次正常工作)。

一般来说O(1),但是如果我们使用了一个糟糕的hashCode函数,我们需要添加多个元素到一个桶中,所以在最坏的情况下它可能是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 } 

containsKey的时间复杂度在JDK-1.8 containsKey已经改变了,正如其他人提到的那样,在理想情况下它是O(1) 。 但是,如果发生碰撞的情况下, keys Comparable ,存储碰撞元素的箱在超过某个称为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; 

换句话说,将使用TreeNodes (类似于TreeMap那些)来存储分箱(即:红黑树结构),这在碰撞的情况下使我们具有O(lgn)复杂性。

get(key)同样适用于两个方法都在内部调用getNode

注意:这里是bin的大小,而不是HashMap