Ramverk för Java-samlingar

java.util.Collection klass och gränssnittshierarki

Javas java.util.Map klass och gränssnittshierarki

Java - samlingsramverket är en uppsättning klasser och gränssnitt som implementerar vanliga återanvändbara insamlingsdatastrukturer .

Även om det kallas ett ramverk , fungerar det på ett sätt som ett bibliotek . Samlingsramverket tillhandahåller både gränssnitt som definierar olika samlingar och klasser som implementerar dem.

Skillnader från Arrays

Samlingar och arrayer liknar varandra genom att de båda innehåller referenser till objekt och att de kan hanteras som en grupp. Men till skillnad från arrayer behöver samlingar inte tilldelas en viss kapacitet när de instansieras. Samlingar kan också växa och krympa i storlek automatiskt när objekt läggs till eller tas bort. Samlingar kan inte innehålla grundläggande datatypelement (primitiva typer) som int, long eller double; istället har de Wrapper-klasser som Integer, Long eller Double.

Historia

Samlingsimplementationer i tidigare JDK 1.2- versioner av Java-plattformen inkluderade få datastrukturklasser, men innehöll inget samlingsramverk. Standardmetoderna för att gruppera Java-objekt var via klasserna array, Vector och Hashtable, som tyvärr inte var lätta att utöka och inte implementerade ett standard medlemsgränssnitt.

För att möta behovet av återanvändbara insamlingsdatastrukturer utvecklades flera oberoende ramverk, de mest använda var Doug Leas samlingspaket och ObjectSpace Generic Collection Library (JGL), vars huvudmål var överensstämmelse med C++ Standard Template Library (STL) .

Samlingsramverket designades och utvecklades främst av Joshua Bloch och introducerades i JDK 1.2 . Den återanvände många idéer och klasser från Doug Leas samlingspaket , som avskaffades som ett resultat. Sun Microsystems valde att inte använda idéerna från JGL, eftersom de ville ha ett kompakt ramverk, och överensstämmelse med C++ var inte ett av deras mål.

Doug Lea utvecklade senare ett samtidighetspaket , bestående av nya samlingsrelaterade klasser. En uppdaterad version av dessa samtidighetsverktyg inkluderades i JDK 5.0 från och med JSR 166 .

Arkitektur

Nästan alla samlingar i Java härleds från gränssnittet java.util.Collection. Samling definierar de grundläggande delarna av alla samlingar. Gränssnittet anger metoderna add() och remove() för att lägga till respektive ta bort från en samling. Också krävs är metoden toArray(), som konverterar samlingen till en enkel array av alla element i samlingen. Slutligen kontrollerar metoden contains() om ett specificerat element finns i samlingen. Samlingsgränssnittet är ett undergränssnitt till java.lang.Iterable, så vilken samling som helst kan vara målet för en för varje-sats. (Iterable-gränssnittet tillhandahåller iterator()-metoden som används av for-each-satser.) Alla samlingar har en iterator som går igenom alla element i samlingen. Dessutom är Collection en generisk. Vilken samling som helst kan skrivas för att lagra vilken klass som helst. Till exempel Collection<String> hålla strängar, och elementen från samlingen kan användas som strängar utan att någon gjutning krävs. Observera att de vinklade parenteserna < > kan innehålla ett typargument som anger vilken typ som samlingen innehåller.

Tre typer av samling

Det finns tre generiska typer av samling: ordnade listor, ordböcker/kartor och uppsättningar.

Ordnade listor tillåter programmeraren att infoga objekt i en viss ordning och hämta dessa objekt i samma ordning. Ett exempel är en väntelista. Basgränssnitten för ordnade listor kallas List och Queue.

Ordböcker/kartor lagrar referenser till objekt med en uppslagsnyckel för att komma åt objektets värden. Ett exempel på en nyckel är ett ID-kort. Basgränssnittet för ordböcker/kartor kallas Karta.

Uppsättningar är oordnade samlingar som kan itereras och innehålla varje element högst en gång. Basgränssnittet för set kallas Set.

Listgränssnitt

Listor implementeras i samlingsramverket via java.util.List-gränssnittet. Den definierar en lista som i huvudsak en mer flexibel version av en array. Element har en specifik ordning, och dubbletter av element är tillåtna. Element kan placeras i en specifik position. De kan också sökas i listan. Två exempel på konkreta klasser som implementerar List är:

java.util.ArrayList, som implementerar listan som en array. Närhelst funktioner specifika för en lista krävs, flyttar klassen elementen runt i arrayen för att göra det.
java.util.LinkedList. Denna klass lagrar elementen i noder som var och en har en pekare till föregående och nästa noder i listan. Listan kan passeras genom att följa pekarna, och element kan läggas till eller tas bort helt enkelt genom att ändra pekarna runt för att placera noden på rätt plats.

Stackklass

Stackar skapas med java.util.Stack. Stacken erbjuder metoder för att lägga ett nytt objekt på stacken (metod push()) och för att hämta objekt från stacken (metod pop()). En stack returnerar objektet enligt last-in-first-out (LIFO), t.ex. objektet som placerades senast på stacken returneras först. java.util.Stack är en standardimplementering av en stack som tillhandahålls av Java. Klassen Stack representerar en stack av objekt som är sist-in-först-ut (LIFO). Den utökar klassen java.util.Vector med fem operationer som gör att en vektor kan behandlas som en stack. De vanliga push- och pop-operationerna tillhandahålls, såväl som en metod för att kika på det översta objektet i stacken, en metod för att testa om stacken är tom och en metod för att söka i stacken efter ett objekt och upptäcka hur långt det är är från toppen. När en stack först skapas innehåller den inga objekt.

Kögränssnitt

Gränssnittet java.util.Queue definierar ködatastrukturen, som lagrar element i den ordning som de infogas. Nya tillägg går till slutet av raden, och element tas bort från framsidan. Det skapar ett först in först ut system. Detta gränssnitt implementeras av java.util.LinkedList, java.util.ArrayDeque och java.util.PriorityQueue. LinkedList implementerar naturligtvis också List-gränssnittet och kan också användas som ett. Men den har också Queue-metoderna. ArrayDeque implementerar kön som en array. Både LinkedList och ArrayDeque implementerar också java.util.Deque-gränssnittet, vilket ger det mer flexibilitet.

java.util.Queue kan användas mer flexibelt med dess undergränssnitt, java.util.concurrent.BlockingQueue. BlockingQueue-gränssnittet fungerar som en vanlig kö, men tillägg till och borttagningar från kön blockerar. Om remove anropas i en tom kö, kan den ställas in att vänta antingen en angiven tid eller på obestämd tid på att ett objekt ska dyka upp i kön. På liknande sätt är att lägga till ett föremål föremål för en valfri kapacitetsbegränsning på kön, och metoden kan vänta på att utrymme blir tillgängligt i kön innan den återvänder.

java.util.PriorityQueue implementerar java.util.Queue, men ändrar den också. Istället för att element ordnas i den ordning som de infogas, ordnas de efter prioritet. Metoden som används för att bestämma prioritet är antingen metoden compareTo() i elementen eller en metod som ges i konstruktorn. Klassen skapar detta genom att använda en hög för att hålla objekten sorterade.

Dubbeländade kögränssnitt (deque).

Gränssnittet java.util.Queue utökas med undergränssnittet java.util.Deque. Deque skapar en dubbelkö. Medan en vanlig kö endast tillåter insättningar på baksidan och borttagningar framtill, tillåter dequen insättningar eller borttagningar både framtill och baktill. En deque är som en kö som kan användas framåt eller bakåt, eller båda samtidigt. Dessutom kan både en framåt- och en bakåtiterator genereras. Deque-gränssnittet implementeras av java.util.ArrayDeque och java.util.LinkedList.

Gränssnittet java.util.concurrent.BlockingDeque fungerar på samma sätt som java.util.concurrent.BlockingQueue. Samma metoder för insättning och borttagning med tidsgränser för att vänta på att insättningen eller borttagningen blir möjlig tillhandahålls. Men gränssnittet ger också flexibiliteten hos en deque. Insättningar och borttagningar kan ske i båda ändar. Spärrfunktionen kombineras med deque-funktionen.

Ställ in gränssnitt

Javas java.util.Set-gränssnitt definierar uppsättningen. En uppsättning kan inte ha några dubbletter av element. Dessutom har uppsättningen ingen fast ordning. Som sådana kan element inte hittas av index. Set implementeras av java.util.HashSet, java.util.LinkedHashSet och java.util.TreeSet. HashSet använder en hashtabell. Mer specifikt använder den en java.util.HashMap för att lagra hasharna och elementen och för att förhindra dubbletter. java.util.LinkedHashSet utökar detta genom att skapa en dubbellänkad lista som länkar alla element efter deras insättningsordning. Detta säkerställer att iterationsordningen över uppsättningen är förutsägbar. java.util.TreeSet använder ett rött-svart träd implementerat av en java.util.TreeMap. Det rödsvarta trädet ser till att det inte finns några dubbletter. Dessutom tillåter det TreeSet att implementera java.util.SortedSet.

Java.util.Set-gränssnittet utökas med java.util.SortedSet-gränssnittet. Till skillnad från en vanlig uppsättning sorteras elementen i en sorterad uppsättning, antingen med elementets compareTo()-metod eller en metod som tillhandahålls till konstruktören av den sorterade uppsättningen. De första och sista elementen i den sorterade uppsättningen kan hämtas, och delmängder kan skapas via minimi- och maximivärden, såväl som början eller slutar i början eller slutet av den sorterade uppsättningen. SortedSet-gränssnittet implementeras av java.util.TreeSet.

java.util.SortedSet utökas ytterligare via java.util.NavigableSet-gränssnittet. Det liknar SortedSet, men det finns några ytterligare metoder. Metoderna floor(), ceiling(), lower() och higher() hittar ett element i uppsättningen som är nära parametern. Dessutom tillhandahålls en fallande iterator över objekten i uppsättningen. Precis som med SortedSet implementerar java.util.TreeSet NavigableSet.

Kartgränssnitt

Kartor definieras av java.util.Map-gränssnittet i Java. Kartor är enkla datastrukturer som associerar en nyckel med ett element. Detta gör att kartan är mycket flexibel. Om nyckeln är elementets hash-kod är kartan i huvudsak en uppsättning. Om det bara är ett ökande antal blir det en lista. Kartor implementeras av java.util.HashMap, java.util.LinkedHashMap och java.util.TreeMap. HashMap använder en hashtabell . Nycklarnas hash används för att hitta elementen i olika hinkar. LinkedHashMap utökar detta genom att skapa en dubbellänkad lista mellan elementen, vilket gör att de kan nås i den ordning som de infogades i kartan. TreeMap, till skillnad från HashMap och LinkedHashMap, använder ett rött-svart träd. Nycklarna används som värden för noderna i trädet, och noderna pekar på elementen i kartan.

Gränssnittet java.util.Map utökas med dess undergränssnitt, java.util.SortedMap. Det här gränssnittet definierar en karta som sorteras efter de medföljande nycklarna. Genom att återigen använda metoden compareTo() eller en metod som tillhandahålls i konstruktorn till den sorterade kartan, sorteras nyckel-elementparen efter nycklarna. Den första och sista nycklarna på kartan kan anropas. Dessutom kan underkartor skapas från minimum- och maximumnycklar. SortedMap implementeras av java.util.TreeMap.

Gränssnittet java.util.NavigableMap utökar java.util.SortedMap på olika sätt. Metoder kan kallas som hittar nyckeln eller kartposten som är närmast den givna nyckeln i endera riktningen. Kartan kan också vändas och en iterator i omvänd ordning kan genereras från den. Det är implementerat av java.util.TreeMap.

Tillägg till Java-samlingsramverket

Java-samlingsramverket utökas med Apache Commons Collections-biblioteket, som lägger till samlingstyper som en väska och dubbelriktad karta, samt verktyg för att skapa fackföreningar och korsningar.

Google har släppt sina egna samlingsbibliotek som en del av guavabiblioteken .

Se även