Jaka jest złożoność czasowa Java'owej metody
put(E) dla HashMap w notacji O i dlaczego jest to c*n i kiedy mamy taki przypadek? :-)A kiedy mamy przypadek, że mimo tej złożoności rzeczywisty czas jest bliski 1? :-)
Jak uniknąć tego by ten rzeczywisty czas działania
put(E) był daleki od c*n, a bliski 1? :-)Podobne postybeta
Java 8 + lambdy = wolno ;-)
Klasa statyczna - ki diabeł?;-)
Potęga lokalności
Motorola Rulez, czyli Motorola Atrix 4G rządzi :-)
Stereotypy
Jak dla mnie to wygląda to na rehashowanie kiedy miejsce w tablicy się kończy i zwiększa ona swoją wielkość.
OdpowiedzUsuńJak rozumiem to odpowiedź na dlaczego put ma złożoność O(n). Jeżeli tak to jest błędna ;-)
OdpowiedzUsuńWypełnianie ponowne jest dopiero po przekroczeniu tresholdu, więc w idealnym świecie mamy pierwsze włożenie 1, następne 1, 1,1 i aż do 16 [naprawdę chyba 12], wtedy jest przepisanie czyli +16 i znów do tym razem chyba 32 czy jakoś tak i tak dalej.
Ale idealny przypadek mamy tylko wtedy gdy każdy obiekt wkładany do mapy ma inny hashcode, jeżeli wszystkie mają identyczny, np. 0 to układane są w łańcuchu, czyli przy pierwszym wkładaniu lądujemy w pierwszym elemencie tablicy, w drugim też indeks w tablicy to 0, czyli trzeba sprawdzić czy next dla tego elementu to null, jeśli tak to się tam dopisać, jeśli nie to pójść do następnego obiektu i sprawdzić jego next i tak dalej. Łącznie będzie tego n operacji.
A o tym to nie pomyślałem, dobrze będzie już wiedzieć :)
OdpowiedzUsuń