#Niezbędnik Juniora. Kolekcje w języku Java

W kur­sie Javy (a dokład­niej w lekcji 5) omówione były już pod­stawy kolekcji w języku Java. Dzisi­aj posz­erza­my tą wiedzę o infor­ma­c­je, które moga Ci się przy­dać w pra­cy oraz na roz­mowach.Kolekc­je to ta gru­pa obiek­tów z którą spotkasz się bard­zo szy­bko w swo­jej kari­erze. O ile częs­to wystar­czy ich pod­sta­wowa zna­jo­mość, warto nieco się zgłębić i poz­nać ich wady/zalety, aby wiedzieć którą kolekc­je zas­tosować kiedy. W tej lekcji zajmiemy się imple­men­tac­ja­mi, które rozsz­erza­ją inter­fe­js Col­lec­tion.

Słowem wstępu — notacja dużego O

Zan­im prze­jdziemy do opisu poszczegól­nych kolekcji, zatrzy­ma­jmy się na moment, żeby omówić sobie notację dużego O, która będzie nam potrzeb­na do porów­na­nia różnych kolekcji. Szczegółowe infor­ma­c­je na ten tem­at zawrze­my w odd­ziel­nym wpisie, dzisi­aj jedynie wstęp.

Notac­ja dużego O służy w infor­matyce do porówny­wa­nia klas algo­ryt­mów w sposób miar­o­da­jny — weźmy na przykład sor­towanie. Najprost­szym sposobem na porów­nanie różnych pode­jść jest zmierze­nie cza­su sor­towa­nia tych samych ele­men­tów, np. 100 liczb. Meto­da A zro­bi to w 10 jed­nos­tek cza­su a meto­da B zro­bi to w 20 jed­nos­tek cza­su. Czy znaczy to, że meto­da A jest lep­sza / wyda­jniejsza? Abso­lut­nie nie! Wykonu­jąc próbę dla 1000 liczb okaże się, że meto­da A potrze­bu­je już 100 jed­nos­tek cza­su, a meto­da B tylko 50. Aby rozwiązać ten prob­lem wprowad­zono notację dużego o, która mówi nam nie ile cza­su zajmie pew­na oper­ac­ja, ale jak ten czas się zmienia w zależnoś­ci od iloś­ci danych, na których pracu­je­my.

Brz­mi skom­p­likowanie, ale to naprawdę proste! Weźmy dla przykładu algo­rytm, który losu­je liczbę z przedzi­ału (a, b). Dla uproszczenia pomyślmy o tym jako o człowieku, który z wor­ka wszys­t­kich możli­wych liczb z tego przedzi­ału wybiera jed­ną. Czy czas potrzeb­ny na wybranie tej licz­by zmieni się w zależnoś­ci od tego czy w worku będzie 5, 50 czy 500000 liczb? Nie! Oznacza to, że algo­rytm ten dzi­ała w cza­sie stałym, który oznacza­my jako O(1). A dlaczego O(1) a nie np. O(3) ? Ponieważ intere­su­je nas jedynie sposób, w jaki ten czas rośnie, a nie sam czas. Jeśli jest stały, uży­wamy po pros­tu jed­nos­t­ki, aby pokazać, że się nie zmienia.

Jako dru­gi przykład weźmy algo­rytm, który dla każdej licz­by od zera do x wyp­isu­je ją na kon­soli. W zależnoś­ci od wejś­cia (x w tym wypad­ku) nasz algo­rytm będzie musi­ał wykon­ać różną ilość oper­acji — w tym wypad­ku dla każdej jed­nej licz­by będzie to określona, stała licz­ba oper­acji (ponown­ie, nie ma znaczenia, czy będą to 3 oper­ac­je czy 50, ważne, że jest to stała ilość). Dlat­ego algo­rytm ten ma złożoność obliczeniową O(n).

A co, jeśli poprzed­ni algo­rytm zmody­fiku­je­my tak, aby wyp­isy­wał też kwadrat tej licz­by? Nic się nie zmieni, ponieważ wyp­isanie oraz oblicze­nie kwadra­ta licz­by są oper­ac­ja­mi o stałym cza­sie wyko­na­nia, a więc złożoność nadal będzie wynosiła O(n).

Złożoność jest bard­zo waż­na ponieważ częs­to nie wiemy, ile dokład­nie danych będzie przetwarzanych w naszym sys­temie i przez to nie jesteśmy w stanie wykon­ać miar­o­da­jnych prób cza­sowych. Nawet jes­li byśmy to zro­bili, te założe­nia będą się zmieni­ać z cza­sem. Dlat­ego o ile nie jesteśmy abso­lut­nie pewni, że będziemy przetwarzać określoną, niewielką ilość infor­ma­cji (np. kilka­naś­cie) w danym miejs­cu, zawsze powin­niśmy wybier­ać algo­rytm o najm­niejszej złożonoś­ci, a nie taki, który dzi­ała szy­b­ciej (cza­sowo) pod­czas testów. Oczy­wiś­cie od tej reguły moż­na robić wyjąt­ki, ale tylko pod warunk­iem, ze naprawdę wiemy co robimy, a decyz­ja ta została zwery­fikowana i udoku­men­towana w specy­fikacji projektu.

Porów­nanie złożonoś­ci oper­acji we wszys­t­kich kolekc­jach możesz znaleźć na stron­ie http://infotechgems.blogspot.ie/2011/11/java-collections-performance-time.html .

Zachę­camy także do zapoz­na­nia się z mate­ri­ała­mi dostęp­ny­mi pod adresem https://codility.com/media/train/1‑TimeComplexity.pdf .

Rodzaje kolekcji w Javie

Poniżej omówimy poszczególne rodza­je kolekcji, dla każdej z nich podamy zas­tosowa­nia, najważniejsze cechy oraz stan­dar­d­owe implementacje.

Tablica

Dla przeko­ry pier­wszą omaw­ianą struk­turą będzie tabli­ca. Dla przeko­ry ponieważ tablice nie są stricte kolekc­ja­mi (w tym sen­sie, że nie imple­men­tu­ją inter­fe­j­su Col­lec­tion), a ele­mentem języ­ka Java. Jako jedyne mogą prze­chowywać prymi­ty­wy (we wszys­t­kich innych przy­pad­kach ma miejsce auto­box­ing — automaty­cz­na zami­ana prymi­w­ty­wu na odpowiada­jącą mu reprezen­tac­je obiek­tową — jeśli spróbu­je­my dodać prymityw).

Tabli­ca to uporząd­kowany (mają­cy kole­jność, ale niekoniecznie posor­towany!) zbiór ele­men­tów, które fizy­cznie w pamię­ci kom­put­era są umieszc­zone obok siebie. Umożli­wia­ją dostęp losowy (tzw. Ran­dom Access), czyli dostęp do ele­men­tu na dowol­nie wybranej pozy­cji. Ele­men­ty tabl­i­cy mogą mieć wartość null! Aby utworzyć tablicę sto­su­je­my poniższą konstrukcję:

String[] tablica = new String[6];

Doz­wolone jest także umieszcze­nie naw­iasów kwadra­towych za nazwą zmiennej:

String tablica[] = new String[6];

Jak pewnie zauważyłaś, nie uży­wamy tutaj naw­iasów () jak w przy­pad­ku kon­struk­torów obiektów.

Inna dopuszczal­na skład­nia, która od razu inicju­je tablicę wartoś­ci­a­mi jest poniższa:

String[] tablica = {"jeden", "dwa", "trzy", "cztery", "pięć", "sześć"};

Ist­nieje jeszcze jed­na możli­wość zadeklarowa­nia tabl­i­cy — jako ostat­ni argu­ment metody, dzię­ki czemu może one przyj­mować nieokreśloną liczbę argu­men­tów. Weźmy na przykład poniższą metodę:

public void wypiszStringiWNowychLiniach(String... tablica) { //argument ten jest tablicą
    for (i = 0; i<tablica.length; i++) {
        System.out.println(tablica[i]);
    }
}

//przykładowe wywołania
wypiszStringiWNowychLiniach("jeden", "dwa", "trzy", "cztery", "pięć");
String[] tablica = {"jeden", "dwa", "trzy", "cztery", "pięć"};
wypiszStringiWNowychLiniach(tablica);

W powyższym przykładzie widz­imy też jak odwoły­wać się do ele­men­tów tabl­i­cy — w prze­ci­wieńst­wie do kolekcji nie uży­wamy metod, a skład­ni, pisząc nazwę zmi­en­nej a następ­nie w naw­iasie kwadra­towym numer elementu.

Ostat­nia bard­zo waż­na infor­ma­c­ja na tem­at tablic jest taka, że rozmi­aru tabl­i­cy nie moż­na zmieni­ać! Jeśli utworzymy tablicę z 6 ‘miejs­ca­mi’, aby  dodać do niej 7 ele­ment, będziemy musieli utworzyć nową, więk­szą, tablicę i przepisać wcześniejsze 6 elementów.

Lista (java.util.List)

Listy są jed­ny­mi z najczęś­ciej uży­wanych kolekcji — kon­cep­cyjnie są podob­ne do tablic, moż­na jed­nak (tak jak w przy­pad­ku wszys­t­kich pozostałych kolekcji) dynam­icznie zmieni­ać ich rozmi­ar (dodawać i usuwać ele­men­ty). Ele­men­ty w liś­cie mogą się pow­tarzać (tzn. ten sam obiekt może być na liscie wielokrot­nie). Ist­nieje kil­ka stan­dar­d­owych imple­men­tacji, z których najważniejsze zostały opisane poniżej:

Imple­men­tacją inter­fe­j­su List jest także klasa Stack — będziemy jed­nak omaw­iać stos jako osob­ną struk­turę i tam omówimy tą klasę.

Aby utworzyć nową listę (do przykładów bedziemy korzys­tać z ArrayListy) wystar­czy wywołać konstruktor:

List<String> lista = new ArrayList<String>();

Do dodawa­nia ele­men­tu służy meto­da add:

lista.add("jeden");

Pobieranie ele­men­tów odby­wa się z uży­ciem metody get, poda­jąc pozy­cję ele­men­tu jako argument:

String pierwszy = lista.get(0);

Stan listy może­my sprawdz­ić korzys­ta­jąc z pomoc­niczych metod:

int iloscElementow = lista.size();
boolean listaJestPusta = lista.isEmpty();

Set / zbiór (java.util.Set)

Sety to zbio­ry ele­men­tów, w których nie może­my uzyskać dostępu do n’tego ele­men­tu, a jedynie może­my pobrac iter­a­tor (obiekt, który poz­woli nam pobrać kole­jne ele­men­ty, w zależnoś­ci od imple­men­tacji w porząd­ku posor­towanym lub losowym). Ele­men­ty w Setach nie mogą się pow­tarzać.

Aby utworzyć nowy set (do przykładów bedziemy korzys­tać z Hash­Set) wystar­czy wywołać konstruktor:

Set<String> set = new HashSet<String>();

Do dodawa­nia ele­men­tu służy meto­da add:

set.add("jeden");

Pobieranie ele­men­tów odby­wa się z uży­ciem iter­a­to­ra, np w pętli for:

for (String string : set) {
    ...
}

Stan zbioru może­my sprawdz­ić korzys­ta­jąc z pomoc­niczych metod:

int iloscElementow = set.size();
boolean zbiorJestPusty = set.isEmpty();

Map (java.util.Map)

Mapy nie imle­men­tu­ją wprawdzie inter­fe­j­su Col­lec­tion, ale są także częś­cią Java Col­lec­tions API. Prze­chowu­ją one mapowa­nia pomiędzy klucza­mi, a wartoś­ci­a­mi. Zarówno dodanie ele­men­tu, jak i jego pobranie wyma­ga poda­nia klucza. Kluczem może być dowol­ny obiekt. Ele­men­ty w Mapach mogą się pow­tarzać, pod warunk­iem, że sa one wartoś­ci­a­mi. Klucze nie mogą się pow­tarzać. Mapy mają wiele wspól­nego z omaw­iany­mi wyżej zbio­ra­mi (moż­na o nich myśleć jak o zbio­rach pow­iązań pomiędzy kluczem i wartoś­cią), przez co jak pewnie zauważysz dzielą wiele cech wspólnych.

Aby utworzyć nową mapę (do przykładów bedziemy korzys­tać z HashMap) wystar­czy wywołać konstruktor:

Map<Integer, String> map= new HashMap<Integer,String>();

Do dodawa­nia ele­men­tu służy meto­da put:

map.put(1, "jeden");

Pobieranie ele­men­tów odby­wa się z uży­ciem metody get, poda­jąc klucz jako argument:

String string = map.get(1)

Stan mapy może­my sprawdz­ić korzys­ta­jąc z pomoc­niczych metod:

int iloscElementow = map.size();
boolean mapaJestPusta = map.isEmpty();
boolean zawieraKlucz = map.containsKey(1);
boolean zawieraWartosc = map.containsValue("jeden");

Kolejki (java.util.Queue)

Kole­j­ki dzielą się na dwa typy — LIFO (last-in, first-out) oraz FIFO (first-in, first-out). Przykła­dem kole­j­ki LIFO jest stos, mówiąc o kole­jce częs­to mamy na myśli kole­jkę FIFO. Co ciekawe, w języku Java klasa Stack imple­men­tu­je inter­fe­js listy, a nie kole­j­ki. Drugą cieka­wostką jest fakt, że klasa LinkedList także imple­men­tu­je inter­fe­js Queue (ponieważ była ona już omówiona wczes­niej, nie będziemy powtarzać).

W kole­jkach wyróż­ni­amy głowę oraz ogon — stadar­d­owo inter­fe­js Queue pozwala na pracę tylko z głową, inter­fe­js Dequeue (który dziedz­iczy po Queue) pozwala na pracę zarówno z głową jak i ogonem.

Ideą kole­jek jest prze­chowywanie ‘kole­j­ki’ obiek­tów do przetworzenia w określonej kole­jnoś­ci, stanow­ią pewnego rodza­ju bufor obiektów.

Poniższy opis obe­j­mu­je jedynie inter­fe­js Queue, którego klasa Stack nie imple­men­tu­je. Aby z niej sko­rzys­tać, zapoz­naj się z doku­men­tacją API.

Aby utworzyć nową kole­jkę (do przykładów bedziemy uży­wać Array­D­e­queue) wystar­czy wywołać konstruktor:

Queue<String> kolejka = new ArrayDequeue<String>();

Do dodawa­nia ele­men­tu służą metody add oraz offer:

kolejka.add("jeden"); //jeżeli kolejka jest pełna, rzuci wyjątek
kolejka.offer("jeden"); //nie rzuci wyjątku, a jedynie zwróci false

Pobieranie ele­men­tów odby­wa się z uży­ciem metod remove i poll:

String string = kolejka.remove(); //jeżeli kolejka jest pusta, rzuci wyjątek
String string = kolejka.poll(); //jeżeli kolejka jest pusta, zwróci null

Kole­j­ka pozwala nam także ‘pode­jrzeć’ kole­jny ele­ment nie usuwa­jąc go z kole­j­ki, służą do tego metody ele­ment oraz peek:

String string = kolejka.element(); //jeżeli kolejka jest pusta, rzuci wyjątek
String string = kolejka.peek(); //jeżeli kolejka jest pusta, zwróci null

Stan kole­j­ki może­my sprawdz­ić korzys­ta­jąc z pomoc­niczych metod:

int iloscElementow = kolejka.size();
boolean kolejkaJestPusta = kolejka.isEmpty();

Podsumowanie

W ramach pod­sumowa­nia zbierze­my infor­ma­c­je o wszys­t­kich omówionych rodza­jach kolekcji w formie tabeli. Warto też zapoz­nać się z ofic­jal­ną doku­men­tacją na tem­at col­lec­tions API, dostęp­nńą pod adresem http://docs.oracle.com/javase/8/docs/technotes/guides/collections/ .