1. Dom
  2. Pytanie i odpowiedź
  3. Co koszt iteracji w HashSet zależy również od pojemności mapy podkładu?

Co koszt iteracji w HashSet zależy również od pojemności mapy podkładu?

2012-08-22 7 views
8

Z Javadocs z HashSet:Co koszt iteracji w HashSet zależy również od pojemności mapy podkładu?

Klasa ta oferuje stałą wydajność czasową dla podstawowych operacji (dodawać, usuwać, zawiera i rozmiar), przy założeniu, że funkcja hash rozprasza elementów prawidłowo wśród wiader. Iteracja w tym zestawie wymaga czasu proporcjonalnego do sumy rozmiaru instancji HashSet o numerze (liczba elementów) plus "pojemność" instancji klasy HashMap (liczba segmentów). Tak więc, jest to bardzo ważne, aby nie ustawić początkową zdolność zbyt wysoki (lub współczynnika obciążenia zbyt niska) jeśli iteracja wydajność jest ważna

Dlaczego iteracja zajmuje czas proporcjonalny do sumy (liczbę elementów w zestawie + wielkość mapy podkładu), a nie tylko liczbę elementów w samym zestawie?

.

Źródło

2012-08-22 Geek

+5

Jak iteracyjne nad wszystkimi elementami bez również iteracji nad wszystkimi pustymi wiadrami? – sepp2k

+0

Powiązane: http://stackoverflow.com/a/11903357/829571 – assylias

+0

Możesz również [sprawdzić kod] (http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/ 7-b147/java/util/HashSet.java? Av = f # 168) i przejdź do dołu, aby zobaczyć, co dzieje się pod maską. – assylias

Odpowiedz

12

HashSet jest uzupełniany przy użyciu HashMap, gdzie elementy są klawiszami map. Ponieważ mapa ma zdefiniowaną liczbę segmentów, które mogą zawierać jeden lub więcej elementów, iteracja musi sprawdzać każdy segment, niezależnie od tego, czy zawiera on elementy, czy nie.

Źródło

2012-08-22 09:20:17 Thomas

+0

jakie są wartości tej nieszczęść? – Geek

+3

@Geek, ponieważ wartości nie mają znaczenia, że ​​są po prostu sztucznymi obiektami (a dokładniej, jest to jeden fałszywy obiekt: 'private static final Object OBECNA = nowa Object();'). – Thomas

3

Korzystanie z LinkedHashSet następuje po "połączonej" liście wpisów, więc liczba pól nie ma znaczenia. Zwykle nie miałbyś HashSet, gdzie pojemność jest o wiele większa niż dwukrotnie większa niż faktycznie użyta. Nawet jeśli nie, skanowanie milionów wpisów, głównie null nie zajmuje dużo czasu (milisekundach)

Źródło

2012-08-22 09:22:30

+2

2 ms za każdy 1 milion null na mojej maszynie ;-) – assylias

+0

@assylias Brzmi o prawicy. Iterowanie przez HashSet nie będzie ładne bez względu na to, co zrobisz.Naprawdę chcesz wykonać wyszukiwanie lub posortowaną kolekcję, w której pracujesz tylko nad kilkoma wpisami, jeśli chcesz mieć szybkość. –

0

Dlaczego iteracja zajmuje czas proporcjonalny do sumy (liczba elementów w zestawie + pojemności podkładu mapie) i nie tylko pod numerem elementów w samym zestawie?

Elementy są rozproszone wewnątrz podstawowej HashMap, która jest poparta tablicą.
Nie wiadomo więc, które wiadra są zajęte (ale wiadomo, ile elementów jest całkowicie dostępnych).
Więc iteracyjne nad wszystkie elementy wszystkie wiadra należy sprawdzić

Źródło

2012-08-22 09:25:45 Cratylus

Powiązane problemy

 Powiązane problemy