Jaka jest złożoność czasu HashMap.containsKey() w java?

Question

Muszę wiedzieć: Jaka jest złożoność czasu HashMap.containsKey() w java?

Answer 1

Z API doc ofHashMap:

Ta implementacja zapewnia wydajność stałą czasową dla podstawowych operacji (GET i umieścić), zakładając, że funkcja mieszająca rozprasza prawidłowo elementy wśród wiader.

Od containsKey() tylko get() że wyrzuca pobraną wartość, to O (1) (przy założeniu, że funkcja skrótu działa prawidłowo, ponownie).

Answer 2

Jest O(1) w ogóle, jednak w najgorszym przypadku jest 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  } 

Answer 3

Generalnie O (1), ale jeśli używamy złej funkcji hashCode, musimy dodać wiele elementów do jednego kubełka, aby w najgorszym przypadku było ono O (n).

Answer 4

Złożoność czasowa containsKey zmieniło się w JDK-1,8, jak inni wspomnieli, że jest O(1) w idealnych przypadkach. Jednakże, w przypadku kolizji, gdzie keys są Comparable, kosze na przechowywanie elementów Collide nie są liniowe już po przekraczają pewną wartość progową zwaną TREEIFY_THRESHOLD, która jest równa 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; 

Innymi słowy, będą wykorzystywane TreeNodes (podobne do tych w TreeMap) do przechowywania pojemników (tj. struktura czerwono-czarna drzewa) i pozostawia nam złożoność w przypadku kolizji O(lgn).

To samo dotyczy get(key) gdzie gdzie obie metody nazywamy getNode wewnętrznie

Uwaga: n jest tu wielkość bin a nie HashMap