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
