Java collections framework
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Map_Classes.jpg/220px-Map_Classes.jpg)
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
- ^ „Lesson: Introduction to Collections”. Oracle Corporation. Приступљено 22. 12. 2010.
- ^ а б „Java Collections Framework” (PDF). IBM. Архивирано из оригинала (PDF) 7. 08. 2011. г. Приступљено 01. 01. 2011.
- ^ „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
andput
methods.'” - ^ а б 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'”
- ^ „Generic Collection Library for Java™”. Архивирано из оригинала 12. 03. 2009. г. Приступљено 1. 01. 2011.
- ^ „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.'”
- ^ „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. '”
- ^ „Iterable (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013.
- ^ „List (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013.
- ^ „BlockingQueue (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013.
- ^ „PriorityQueue (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013.
- ^ „Deque (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013.
- ^ „Set (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013.
- ^ „Map (Java Platform SE 7 )”. Docs.oracle.com. 6. 06. 2013. Приступљено 16. 08. 2013.
- ^ „Collections - Home”. Commons.apache.org. 4. 07. 2013. Приступљено 16. 08. 2013.
Spoljašnje veze
- Collections Lessons
- CollectionSpy — A profiler for Java's Collections Framework.
- Generic Types
- Java 6 Collection Tutorial — By Jakob Jenkov, Kadafi Kamphulusa
- Java Generics and Collections
- Taming Tiger: The Collections Framework
- 'The Collections Framework' (Oracle Java SE 7 documentation)
- 'The Java Tutorials - Collections' by Josh Bloch
- 'Which Java Collection to use?' — by Janeve George