39
Muszę wiedzieć: Jaka jest złożoność czasu HashMap.containsKey() w java?Jaka jest złożoność czasu HashMap.containsKey() w java?
A
Odpowiedz
47
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).
+0
to jest to, co myślałem wcześniej. Ale to nie jest poprawne. Spójrz na odpowiedź Jigara Joshi. Twoja odpowiedź jest poprawna dla 'HashTable', która nie pozwala na wartości null. – AlexR
+1
@AlexR: Myślę, że całkowicie nie rozumiesz kodu w odpowiedzi Jigara. Nie ma absolutnie nic wspólnego z wartościami pustymi, a pętla for wykonuje pętle tylko przez połączoną listę wpisów w jednym segmencie, który jest O (1), jeśli, jak stwierdzono dwukrotnie w mojej odpowiedzi, funkcja hash wykonuje swoje zadanie. –
+0
Jeśli uda mi się wybrać klucze już na mapie, jest to O (n). –
8
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 }
11
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).
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
@OlegSklyar To pytanie pomógł mi, bo miałem do wdrożenia sama HashMap. – trinity420
@ trinity420 Czy to uzasadnia brak przeczytania dokumentacji API, gdy masz pytanie dotyczące interfejsu API? –