Java collections framework

class- and interface hierarchy of java.util.Map

Java collections framework - JCF je skup klasa i interfejsova koji implementiraju često upotrebljivane kolekcije struktura podataka.[1]

Istorija

Implementacije kolekcija u verzijama Jave pre JDK 1.2 su sadržavale nekolicinu klasa struktura podataka, ali ne i .[2] Standardni načini za grupisanje Java objekata su bili pomoću nizova, Vector i Hashtable klasa, koje nije bilo lako proširiti.[3]

S obzirom na potrebu za dinamičnijim kolekcijama struktura podataka, razvijene su mnoge nezavisne biblioteke,[2] od kojih su najkorišćenije bile Dag Lijev (Doug Lea) Paket kolekcija (Collections package),[4] i ObjectSpace Generic Collection Library (JGL),[5] čija je svrha bila konzistentnost sa C++ Standard Template Library (STL).[6]

JCF je razvijen i dizajniran uglavnom od strane Džoš Bloka, i pojavio se u JDK 1.2. Koristi mnoge ideje i klase i Dag Lijevog Paketa kolekcija, koji tada biva prevaziđen.[4] Sun chose not to use the ideas of JGL, because they wanted a compact framework, and consistency with C++ was not one of their goals.[7]

Arhitektura

Skoro sve kolekcije nasle]uju od java.util.Collection interfejsa, koji definiše osnovne delove svake kolekcije. Interfejs uvodi add() i remove() metode za dodavanje i izbacivanje iz kolekcije. Neophodni su i toArray() metod, koji prevodi kolekciju u niz koji sadrži sve članove kolekcije, i contains() metod koji proverava da li kolekcija sadrži neki konkretan element. Ovaj interfejs nasleđuje od java.lang.Iterable interfejsa, čime se omogućuje obrada kolekcija pomoću for-each izraza. Sve kolekcije imaju iterator koji prolazi kroz sve elemente u kolekciji. Takođe, Collection je generički interfejs - svaka kolekcija može da bude napisana tako da može da skladišti bilo koju klasu.[8]

Lista

Liste su implementirane pomoću java.util.List interfejsa. Definiše listu koja je suštinski felksibilnija verzija niza. Elementi su uređeni u specifičnom redosledu i dozvoljeni su duplikati. Elementi se mogu umetnuti na specifičnu poziciju i moguća je pretraga. Implementirane su u klasama java.util.ArrayList i java.util.LinkedList. ArrayList implementira listu kao niz. Kada se koriste funkcije specifične za liste, klasa pomera elemente unutar niza. LinkedList skladišti elemente u čvorovima koji imaju pokazivače na prethodni i naredni element liste.[9]

Stek

Stek se implementira pomoću java.util.Stack. Stack klasa predstavlja last-in-first-out (LIFO) gomilu objekata koja proširuje Vector klasu sa pet operacija koje omogućavaju vektoru da bude tretiran kao stek. Snabdeveni su uobičajeni push i pop metodi, ali i metod za gledanje sadržaja na vrhu steka, metod koji proverava da li je stek prazan i metod koji pretražuje stek i otkriva koliko je traženi objekat daleko od vrha. Stek se kreira prazan.

Red

Red je struktura podataka koja skladišti svoje elemente u redosledu u kojem su unešeni. Implementira se koristeći interfejs java.util.Queue. Elementi se dodaju na kraj, a skidaju sa početka, ostvarujući first-in-first-out sistem. java.util.LinkedList, java.util.ArrayDeque, and java.util.PriorityQueue implementiraju ovaj interfejs. LinkedList implementira i List interfejs. ArrayDeque implicitno implementira red pomoću niza.

java.util.concurrent.BlockingQueue je podinterfejs java.util.Queue koji omogućava fleksibilnije rukovanje redovima. On dozvoljava da se pri stavljanju objekta u red proveri da li ima mesta i, ukoliko nema, da se sačeka izvesno vreme da se oslobodi prostor. Slično, ukoliko se skida element iz praznog reda, čeka se dok se ne pojavi.[10]

Kod java.util.PriorityQueue se elementi sortiraju po prioritetu koji se određuje ili pomoću compareTo() metoda, ili pomoću metoda koji se prosleđuje konstruktoru reda sa prioritetm. Ovo se implementira pomoću hipa.[11]

Red sa dva kraja

java.util.Deque interfejs omogućava kreiranje dvostrukih redova. Dok obični redovi dozvoljavaju samo dodavanje na kraju i skidanje sa početka, dvostruki red omogućava da se to vrši sa oba kraja. Mogu se kreirat iteratori za oba smera. java.util.ArrayDeque i java.util.LinkedList implementiraju ovaj interfejs.[12]

Skup

java.util.Set interfejs definiše skup objekata. Skup ne može da sadrži duplikate i nema konkretan poredak objekata. Elementima se ne može pristupati pomoću indeksa. java.util.HashSet, java.util.LinkedHashSet, i java.util.TreeSet implementiraju java.util.Set. HashSet koristi java.util.HashMap za skladištenje elemenata i heševa radi sprečavanja nastanka duplikata. java.util.LinkedHashSet ovo proširuje kreiranjem dvostruko povezane liste koja povezuje elemente u redosledu kojim su uneti u skup, čime se postiže to da je redosled iteriranja kroz skup predvidiv. java.util.TreeSet koristi crveno-crno stablo implementirano pomoću java.util.TreeMap. Crveno-crno stablo se stara o tome da nema duplikata i omogućava TreeSet-u da implementira java.util.SortedSet.[13] java.util.SortedSet interfejs implementira java.util.Set interfejs, ali za razliku od običnog skupa njegovi elementi su sortirani ili uz pomoć compareTo() metode elementa, ili pomoću metode koja je prosleđena konstruktoru sortiranog skupa. Mogu se povratiti prvi i poslednji elementi sortiranog skupa, i mogu se kreirati podskupovi skupa pomoću minimalnih i maksimalnih vrednosti.

Mapa

Mape su proste strukture podataka koje asociraju vrednosti sa ključevima. Ako je ključ heš vrednost elementa mapa je suštinski skup, a ako je samo rastući broj postaje lista. U Javi su mape definisane pomoću java.util.Map interfejsa. java.util.HashMap koristi heš tabelu. Heševi ključeva se koriste za pronalaženje vrednosti. java.util.LinkedHashMap ovo proširuje heš mapu povezivanjem elemenata u dvostruko povezanu listu, što omogućava da se elementima pristupa i po redosledu kojim su dodati u mapu. java.util.TreeMap za razliku od prethodne dve implementacije koristi crno-crveno stablo gde se ključevi koriste kao vrednosti čvorova u stablu, dok čvorovi pokazuju na vrednosti mape.[14]


Proširenja za JCF

Apache Commons Collections biblioteka dodaje tipove kolekcija kao što su džak (multiskup) i dvosmerna mapa. Takođe omogućava kreiranje unija u preseka. .[15]

Gugl je objavio svoje biblioteke kolekcija kao deo guava biblioteka.

Reference

  1. ^ „Lesson: Introduction to Collections”. Oracle Corporation. Приступљено 22. 12. 2010. 
  2. ^ а б „Java Collections Framework” (PDF). IBM. Архивирано из оригинала (PDF) 7. 08. 2011. г. Приступљено 01. 01. 2011. 
  3. ^ „Get started with the Java Collections Framework”. JavaWorld. 11. 01. 1998. Архивирано из оригинала 30. 03. 2010. г. Приступљено 1. 01. 2011. „'Before Collections made its most welcome debut, the standard methods for grouping Java objects were via the array, the Vector, and the Hashtable. All three of these collections have different methods and syntax for accessing members: arrays use the square bracket ([]) symbols, Vector uses the elementAt method, and Hashtable uses get and put methods.' 
  4. ^ а б Doug Lea. „Overview of the collections Package”. Приступљено 1. 01. 2011. „'The Sun Java Development Kit JDK1.2 finally includes a standard set of collection classes. While there are some design and implementation differences, the JDK1.2 package contains most of the same basic abstractions, structure, and functionality as this package. For this reason, this collections package will NOT be further updated' 
  5. ^ „Generic Collection Library for Java™”. Архивирано из оригинала 12. 03. 2009. г. Приступљено 1. 01. 2011. 
  6. ^ „Need a good set of abstract data structures? ObjectSpace's JGL packs a punch!”. JavaWorld. 6. 01. 1997. Архивирано из оригинала 02. 03. 2012. г. Приступљено 1. 01. 2011. „'As with Java itself, the Java Generic Library borrows heavily from the C++ camp: It takes the best from C++'s STL, while leaving the C++ warts behind. Most C++ programmers today will know of their STL, but few are managing to exploit its potential.' 
  7. ^ „The battle of the container frameworks: which should you use?”. JavaWorld. 1. 01. 1999. Архивирано из оригинала 12. 04. 2010. г. Приступљено 1. 01. 2011. „'Comparing ObjectSpace Inc.'s JGL and Sun's Collections Framework turns out to be like comparing apples and kiwi fruits. At first sight, the two frameworks seem to be competing for the same developers, but after a closer inspection it is clear that the two cannot be compared fairly without acknowledging first that the two frameworks have different goals. If, like Sun's documentation states, Collections is going to homogenize Sun's own APIs (core API, extensions, etc.), then clearly Collections has to be great news, and a good thing, even to the most fanatic JGL addict. Provided Sun doesn't break its promise in this area, I'll be happy to invest my resources in adopting Collections in earnest. ' 
  8. ^ „Iterable (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013. 
  9. ^ „List (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013. 
  10. ^ „BlockingQueue (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013. 
  11. ^ „PriorityQueue (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013. 
  12. ^ „Deque (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013. 
  13. ^ „Set (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013. 
  14. ^ „Map (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013. 
  15. ^ „Collections - Home”. Commons.apache.org. 4. 07. 2013. Приступљено 16. 08. 2013. 

Spoljašnje veze