7.1 Records
In andere programmeertalen
De concepten in andere programmeertalen die het dichtst aanleunen bij Java records, pattern matching en sealed interfaces zijn
- structs in C en C++ (pattern matching in C++ is nog niet beschikbaar, maar er wordt gewerkt aan dit toe te voegen aan de taal)
- @dataclass en structured pattern matching in Python
- (sealed) record types en pattern matching in C#
Wat zijn records
Wanneer we object-georiënteerd programmeren, maken we gebruik van encapsulatie: we maken de velden van een klasse gewoonlijk privaat, zodat ze worden afgeschermd van andere klassen. Op die manier kunnen we de interne representatie (de velden en hun types) makkelijk aanpassen: zolang de publieke methodes hetzelfde blijven, heeft zo’n aanpassing geen effect op de rest van het systeem.
Maar soms is encapsulatie niet echt nodig: sommige klassen zijn niet meer dan een bundeling van verschillende waarden.
Welgekende voorbeelden zijn een coordinaat (bestaande uit een x- en y-attribuut), een geldbedrag (een bedrag en een munteenheid), een adres (straat, huisnummer, postcode, gemeente), etc.
Ze bevatten vaak geen complex gedrag, en objecten van deze klassen hoeven ook niet aanpasbaar te zijn; je kan makkelijk een nieuw object maken met andere waarden.
We noemen dit data-oriented programming.
Voor dergelijke klassen heeft doorgedreven encapsulatie weinig zin.
Een record in Java is een eenvoudige klasse die gebruikt kan worden voor data-oriented programming.
Een record-object dient voornamelijk als data-drager, waarbij verschillende objecten met dezelfde attribuut-waarden gewoonlijk volledig inwisselbaar (equivalent) zijn.
De attributen van een record-object mogen daarom niet veranderen doorheen de tijd (het object is dus immutable).
Als voorbeeld definiëren we een coördinaat-klasse als een record, met 2 attributen: een x- en y-coördinaat.
public record Coordinate(double x, double y) {
}
Merk het verschil op met de definitie van een gewone klasse: de attributen van de record staan hier vlak na de klassenaam, en er is geen constructor nodig.
Objecten van een record maak je gewoon aan met new, zoals elk ander object:
Coordinate coord = new Coordinate(3, 5);
System.out.println(coord);
// => Coordinate[x=3.0, y=5.0]
Twee coördinaat-objecten met dezelfde x- en y-coordinaat worden als equivalent beschouwd, ook al zijn het twee verschillende objecten:
var coordinate1 = new Coordinate(3, 5);
var coordinate2 = new Coordinate(3, 5);
assertEquals(coordinate1, coordinate2);
Wanneer gebruik je een record
Er zijn meerdere situaties waarin het aangeraden is om een record te gebruiken, bijvoorbeeld:
- wanneer je meerdere waarden (die logisch bij elkaar horen) wil bundelen:
record Address(String street,
int houseNumber,
int zipCode,
String city,
String country) {}
- wanneer je een methode meerdere waarden wil laten teruggeven
record ElementFound(int index, int value) {}
public ElementFound findMaximum(ArrayList<Integer> values) { ... }
- wanneer je een type wil definiëren dat overeenkomt met een ander, reeds bestaand datatype, maar met beperkingen.
record PositiveNumber(int number) {
public PositiveNumber {
if (number <= 0) throw new IllegalArgumentException("Number must be larger than 0");
}
}
- wanneer je een (immutable) datatype wil maken dat zonder probleem door meerdere threads gebruikt kan worden; dit komt later nog aan bod in het onderwerp Multithreading en concurrency.
Merk op dat bij records in de eerste plaats gaat over het creëren van een nieuw datatype, door (primitievere) data of andere records te bundelen, of beperkingen op te leggen aan mogelijke waarden.
Je maakt dus als het ware een nieuw ‘primitief’ datatype, zoals int, double, of String.
Dit in tegenstelling tot gewone klassen, waar encapsulatie en mogelijkheden om de toestand van een object aan te passen (mutatie-methodes) ook essentieel zijn.
Achter de schermen
Een record is eigenlijk een gewone klasse, waarbij de Java-compiler zelf enkele zaken voorziet:
- een constructor, die de velden initialiseert;
- methodes om de attributen op te vragen;
- een
toString-methode om een leesbare versie van het record uit te printen; en - een
equals- en hashCode-methode, die ervoor zorgen dat objecten met dezelfde parameters als gelijk worden beschouwd.
De klasse is ook final, zodat er geen subklassen van gemaakt kunnen worden.
De coördinaat-record van hierboven is equivalent aan volgende klasse-definitie:
public final class Coordinate {
private final double x;
private final double y;
public Coordinate(double x, double y) {
this.x = x;
this.y = y;
}
double x() { return this.x; }
double y() { return this.y; }
public boolean equals(Object other) { /* ... */ }
public int hashCode() { /* ... */ }
public String toString() { /* ... */ }
}
Met de speciale syntax voor records kan je jezelf dus heel wat typwerk (en kans op fouten) besparen.
Methodes toevoegen aan een record
Je kan zelf extra methodes toevoegen aan een record op dezelfde manier als bij een gewone Java-klasse:
public record Coordinate(double x, double y) {
public double distanceTo(Coordinate other) {
double deltaX = other.x() - this.x();
double deltaY = other.y() - this.y();
return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
}
}
Merk wel op dat, omdat de klasse immutable is, je in een methode geen nieuwe waarde kan toekennen aan de velden. Code als
in een methode van een record is dus ongeldig, en leidt tot een foutmelding van de compiler.
Constructor van een record
Als je geen enkele constructor definieert, krijgt een record een standaard constructor met de opgegeven attributen als parameters (in dezelfde volgorde).
Maar je kan ook zelf een of meerdere constructoren definiëren voor een record, net zoals bij klassen (je krijgt dan geen default-constructor meer).
Je moet in die constructoren zorgen dat alle attributen van het record geïnitialiseerd worden.
public record Coordinate(double x, double y) {
public Coordinate(double x, double y) {
this.x = x;
this.y = y;
}
public Coordinate(double x) { // constructor for points on the x-axis
this(x, 0);
}
}
Er is ook een verkorte notatie, waarbij je de parameters niet meer moet herhalen (die staan immers al achter de naam van het record).
Je hoeft met deze notatie ook de parameters niet toe te kennen aan de velden; dat gebeurt automatisch.
Het belangrijkste nut hiervan is om de geldigheid van de waarden te controleren bij het aanmaken van een object:
public record Coordinate(double x, double y) {
public Coordinate {
if (x < 0) throw new IllegalArgumentException("x must be non-negative");
if (y < 0) throw new IllegalArgumentException("y must be non-negative");
}
}
Records en overerving
Zoals eerder al vermeld werd, komt een record overeen met een final klasse.
Je kan er dus niet van overerven.
Een record zelf kan ook geen subklasse zijn van een andere klasse of record, maar kan wel interfaces implementeren.
Immutable
Een record is immutable (onveranderbaar): de attributen krijgen een waarde wanneer het object geconstrueerd wordt, en kunnen daarna nooit meer wijzigen.
Als je een object wil met andere waarden, moet je dus een nieuw object maken.
Bijvoorbeeld, als we een translate methode willen maken voor Coordinate, dan kunnen we de x- en y-coordinaten niet aanpassen.
We moeten een nieuw Coordinate-object maken, en dat teruggeven:
public record Coordinate(double x, double y) {
public Coordinate translate(double deltaX, double deltaY) {
// NIET:
// this.x += deltaX; <-- kan niet; de x-waarde mag niet meer gewijzigd worden
// WEL: een nieuw object maken
return new Coordinate(this.x + deltaX, this.y + deltaY);
}
}
Let op! Als een van de velden van het record een object is dat zelf wél gewijzigd kan worden (bijvoorbeeld een array of ArrayList), dan kan je de data die geassocieerd wordt met het record dus wel nog wijzigen.
Vermijd deze situatie!
Bijvoorbeeld:
public record Song(String title, String artist) {}
public record Playlist(ArrayList<Song> songs) {}
var songs = new ArrayList<>(List.of(new Song("Hello", "Adele")));
var playlist1 = new Playlist(songs);
var playlist2 = new Playlist(new ArrayList<>(songs));
System.out.println(playlist1.equals(playlist2)); // => true: beide playlists bevatten dezelfde liedjes
songs.add(new Song("Bye bye bye", "NSYNC"));
System.out.println(playlist1.equals(playlist2)); // => false
Hier zijn twee record-objecten eerst gelijk, maar later niet meer.
Dat schendt het principe dat, voor data-objecten, de identiteit van het object niet zou mogen uitmaken.
De objecten zijn immers niet meer dan de aggregatie van de data die ze bevatten.
Overal waar playlist1 gebruikt wordt, zou ook playlist2 gebruikt moeten kunnen worden en vice versa.
Twee record-objecten die gelijk zijn, moeten altijd gelijk blijven, onafhankelijk van wat er later nog gebeurt.
Gebruik dus bij voorkeur immutable data types in een record.
Pattern matching
Je kan records ook gebruiken in switch statements.
Dit heet pattern matching, en is vooral nuttig wanneer je meerdere record-types hebt die eenzelfde interface implementeren.
Bijvoorbeeld:
interface Shape {}
record Square(double side) implements Shape {}
record Circle(double radius) implements Shape {}
record Rectangle(Coordinate topLeft, Coordinate bottomRight) implements Shape {}
Je kan dan een switch expressie gebruiken, bijvoorbeeld om een methode te implementeren die de oppervlakte van een vorm berekent:
public double area(Shape shape) {
return switch(shape) {
case Square s -> s.side() * s.side();
case Circle(double radius) -> Math.PI * radius * radius;
case Rectangle(Coordinate(double topLeftX, double topLeftY), Coordinate bottomRight) ->
(bottomRight.x() - topLeftX) * (bottomRight.y() - topLeftY);
default -> throw new IllegalArgumentException("Unknown shape");
};
}
Merk op dat je zowel kan matchen op het object als geheel (Square s in het voorbeeld hierboven), individuele argumenten (Circle(double radius) in het voorbeeld), en zelfs geneste patronen (Rectangle(Coordinate(double topLeftX, double topLeftY), Coordinate bottomRight)).
De switch-expressie hierboven is verschillend van het (oudere) switch-statement in Java:
- er wordt
-> gebruikt in plaats van : - er is geen
break nodig op het einde van elke case - de switch-expressie geeft een waarde terug die kan toegekend worden aan een variabele, of gebruikt kan worden in een
return-statement (zoals in het voorbeeld hierboven).
Tenslotte is er in een switch-expressie de mogelijkheid om een conditie toe te voegen door middel van een when-clausule:
public double area(Shape shape) {
return switch(shape) {
case Square s -> s.side() * s.side();
case Circle(double radius) -> Math.PI * radius * radius;
case Rectangle(Coordinate(double topLeftX, double topLeftY), Coordinate bottomRight)
when topLeftX <= bottomRight.x() && topLeftY <= bottomRight.y() -> // <= when-clausule
(bottomRight.x() - topLeftX) * (bottomRight.y() - topLeftY);
default -> throw new IllegalArgumentException("Unknown or invalid shape");
};
}
Op die manier kan je extra voorwaarden toevoegen om een case te laten matchen, bovenop het type van het element.
Sealed interfaces
Wanneer je alle klassen kent die een bepaalde interface zullen implementeren (of van een abstracte klasse zullen overerven), kan je van deze interface (of klasse) een sealed interface (of klasse) maken.
Met een permits clausule kan je aangeven welke klassen de interface mogen implementeren:
public sealed interface Shape permits Square, Circle, Rectangle {}
record Square(double side) implements Shape {}
record Circle(double radius) implements Shape {}
record Rectangle(double length, double width) implements Shape {}
Indien je geen permits-clausule opgeeft, zijn enkel de klassen die in hetzelfde bestand staan toegestaan.
Omdat elk Java-bestand slechts 1 publieke top-level klasse (of interface/record) mag hebben, zal je vaak ook zien dat de records in de interface-definitie geplaatst worden:
public sealed interface Shape {
record Square(double side) implements Shape {}
record Circle(double radius) implements Shape {}
record Rectangle(double length, double width) implements Shape {}
}
Zo staan ze allemaal samen in 1 bestand, en kan je ze overal in je code gebruiken via bv. Shape.Square.
Voor een sealed klasse of interface zoals Shape zal de compiler niet toelaten dat je er ergens anders een andere klasse van laat overerven:
record Triangle(double base, double height) implements Shape {} // <- compiler error
Omdat de compiler kan nagaan wat alle mogelijkheden zijn, kan je bij pattern matching op een sealed klasse in een switch statement ook de default case weglaten:
public double area(Shape shape) {
return switch(shape) {
case Square s -> s.side() * s.side();
case Circle(double radius) -> Math.PI * radius * radius;
case Rectangle(double width, double height) -> width * height;
};
}
Omgekeerd zal de compiler je ook waarschuwen wanneer er een geval ontbreekt.
public double area(Shape shape) {
return switch(shape) {
case Square s -> s.side() * s.side();
case Circle(double radius) -> Math.PI * radius * radius;
// <= compiler error: ontbrekende case voor 'Rectangle'
};
}
Oefeningen
Zie Oefeningen
Subsections of 7.2 Generics
7.2.1 Definiëren en gebruiken
Om een klasse generisch te maken, moet je een generische parameter (meestal aangegeven met een enkele letter) toevoegen, zoals de generische parameter T bij ArrayList<T>.
In het algemeen zijn er slechts twee plaatsen in je code waar je een nieuwe generische parameter mag introduceren:
- Bij de definitie van een klasse (of interface, record, …)
- Bij de definitie van een methode (of constructor)
Een generische klasse definiëren
Om een generische klasse te definiëren (de eerste optie), zet je de type-parameter tussen < en > achter de naam van de klasse die je definieert.
Vervolgens kan je die parameter (bijna) overal in die klasse gebruiken als type:
class MyGenericClass<E> {
// je kan hier (bijna) overal E gebruiken als type
}
Bijvoorbeeld, volgende klasse is een nieuwe versie van de ArrayList-klasse van eerder, maar nu met type-parameter E (waar E staat voor ‘het type van de elementen’).
Deze E wordt vervolgens gebruikt als type voor de elements-array, de parameter van de add-method, en het resultaat-type van de get-method:
class ArrayList<E> {
private E[] elements;
public void add(E element) { /* ... */ }
public E get(int index) { /* ... */ }
}
Je zal heel vaak zien dat generische type-parameters slechts bestaan uit 1 letter (populaire letters zijn bijvoorbeeld E, R, T, U, V). Dat is geen vereiste: onderstaande code mag ook, en is volledig equivalent aan die van hierboven.
De reden waarom vaak met individuele letters gewerkt wordt, is om duidelijk te maken dat het over een type-parameter gaat, en niet over een bestaande klasse.
class ArrayList<Element> {
private Element[] elements;
public void add(Element element) { /* ... */ }
public Element get(int index) { /* ... */ }
}
Weetje
Je kan een generische klasse ook zien als een functie (soms een type constructor genoemd).
Die functie geeft geen object terug op basis van een of meerdere parameters zoals je dat gewoon bent van een functie, bijvoorbeeld getPet : (Person p) → Animal, maar geeft een nieuw type (een nieuwe klasse) terug, gebaseerd op de type-parameters.
Bijvoorbeeld, de generische klasse ArrayList<T> kan je beschouwen als een functie ArrayList : (Type T) → Type, die het type ArrayListOfStudents of ArrayListOfAnimals teruggeeft wanneer je ze oproept met respectievelijk T=Student of T=Animal.
In plaats van ArrayListOfStudents schrijven we dat type als ArrayList<Student>.
Een generische klasse gebruiken
Bij het gebruik van een generische klasse (bijvoorbeeld ArrayList<E> van hierboven) moet je een concreet type opgeven voor de type-parameter (E).
Bijvoorbeeld, op plaatsen waar je een lijst met enkel studenten verwacht, gebruik je ArrayList<Student> als type.
Je kan dan de klasse gebruiken op dezelfde manier als de ArrayListOfStudents klasse van hierboven:
ArrayList<Student> students = new ArrayList<Student>();
Student someStudent = new Student();
students.add(someStudent); // <-- OK 👍
// students.add(animal); // <-- niet toegelaten (compiler error) 👍
Student firstStudent = students.get(0); // <-- OK 👍
Merk op hoe de compiler afdwingt en garandeert dat er enkel Student-objecten in deze lijst terecht kunnen komen.
Om wat typwerk te besparen, laat Java in veel gevallen ook toe om het type weg te laten bij het instantiëren, met behulp van <>.
Dat type kan immers automatisch afgeleid worden van het type van de variabele:
ArrayList<Student> students = new ArrayList<>(); // <-- je hoeft geen tweede keer <Student> te typen
Generische parameters begrenzen (bounds)
Een type-parameter <E> zoals we die tot nu toe gezien hebben kan om het even welk type voorstellen.
Soms willen we dat niet, en willen we beperkingen opleggen.
Stel bijvoorbeeld dat we volgende klasse-hierarchie hebben:
abstract class Animal {
/* ... */
abstract void showLike();
}
class Cat extends Animal {
/* ... */
void showLike() {
System.out.println("Purring");
}
}
class Dog extends Animal {
/* ... */
void showLike() {
System.out.println("Wagging tail");
}
}
graph BT
Cat --> Animal
Dog --> Animal
We maken nu een generische klasse Food, geparametriseerd met het type dier (A) dat dat voedsel eet:
class Food<A> {
public void giveTo(A animal) {
/* ... */
animal.showLike(); // <= compiler error 🙁
}
}
Food<Cat> catFood = new Food<>(); // OK
Food<String> stringFood = new Food<>(); // ook OK? 🙁
De Food-klasse is enkel bedoeld om met Animal (en de subklassen van Animal) gebruikt te worden, bijvoorbeeld Food<Cat> en Food<Dog>.
Maar niets houdt ons op dit moment tegen om ook een Food<Student of een Food<String> te maken.
Daarenboven zal de compiler (terecht) ook een compilatiefout geven in de methode giveTo van Food: er wordt een Animal-specifieke methode opgeroepen (namelijk showLike) op de parameter animal, maar die heeft type A en dat kan eender wat zijn, bijvoorbeeld ook String.
En String biedt natuurlijk geen methode showLike() aan.
We kunnen daarom aangeven dat type A een subtype moet zijn van Animal door bij de definitie van de generische parameter <A extends Animal> te schrijven.
Je zal dan niet langer Food<String> mogen schrijven, aangezien String geen subklasse is van Animal.
We begrenzen dus de mogelijke types die gebruikt kunnen worden voor de type-parameter A tot alle types die overerven van Animal (inclusief Animal zelf).
class Food<A extends Animal> {
public void giveTo(A animal) {
/* ... */
animal.showLike(); // <= OK! 👍
}
}
Food<Cat> catFood = new Food<>(); // nog steeds OK
Food<String> stringFood = new Food<>(); // <-- compiler error 👍
Note
Wanneer je deze materie later opnieuw doorneemt, heb je naast extends ook al gehoord van super en wildcards (?) — dit wordt later besproken.
Het is belangrijk om op te merken dat je super en ? nooit kan gebruiken bij de definitie van een nieuwe generische parameter (de Java compiler laat dit niet toe).
Dat kan enkel op de plaatsen waar je een generische klasse of methode gebruikt.
Onthoud dus: op de plaatsen waar je een nieuwe parameter (een nieuwe ’letter’) introduceert, kan je enkel aangeven dat die een subtype van iets moet zijn met behulp van extends.
Een generische methode definiëren en gebruiken
In de voorbeelden hierboven hebben we steeds een hele klasse generisch gemaakt.
Naast een generische klasse was er ook een tweede plaats om een generische parameter te definiëren, namelijk eentje die enkel in één methode gebruikt kan worden.
Dat doe je door de parameter te declareren vóór het terugkeertype van die methode, opnieuw tussen < en >.
Dat kan ook in een klasse die zelf geen type-parameters heeft.
Je kan die parameter dan gebruiken in de methode zelf, en ook in de types van de parameters en het terugkeertype (dus overal na de definitie ervan).
Bijvoorbeeld, onderstaande methodes doSomething en doSomethingElse hebben beiden een generische parameter T.
Die parameter hoort enkel bij elke individuele methode; beide generische types staan dus volledig los van elkaar.
Ook NormalClass is geen generische klasse; enkel de twee methodes zijn generisch.
class NormalClass {
public <T> int doSomething(ArrayList<T> elements) {
// je kan overal in deze methode type T gebruiken
}
public static <T> ArrayList<T> doSomethingElse(ArrayList<T> elements, T element) {
// deze T is onafhankelijk van die in doSomething
}
}
Het is trouwens ook mogelijk om generische klassen en generische methodes te combineren:
class Foo<T> {
public <U> ArrayList<U> doSomething(ArrayList<T> ts, ArrayList<U> us) {
// code met T en U
}
}
Type inference
Bij het gebruik van een generische methode zal de Java-compiler zelf proberen om de juiste types te vinden; dit heet type inference. Je kan de methode meestal gewoon oproepen zoals elke andere methode, en hoeft dus (in tegenstelling tot bij klassen) niet zelf aan te geven hoe de generische parameters geïnstantieerd worden.
ArrayList<Dog> dogs = ...
Dog dog = ...
var result = NormalClass.doSomethingElse(dogs, dog);
// result heeft type ArrayList<Dog>
In de uitzonderlijke gevallen waar type inference faalt, of wanneer je het type van de generische parameter expliciet wil maken, kan je die zelf opgeven als volgt:
ArrayList<Dog> dogs = ...
Dog dog = ...
var result = NormalClass.<Dog>doSomethingElse(animals, dog);
Merk op hoe we, tussen het . en de naam van de methode, de generische parameter <Dog> toevoegen.
Voorbeeld
Als voorbeeld definiëren we (in een niet-generische klasse AnimalHelper) een generische (statische) methode findHappyAnimals.
Deze heeft 1 generische parameter T, en we leggen meteen ook op dat dat een subtype van Animal moet zijn (<T extends Animal>).
class AnimalHelper {
public static <T extends Animal> ArrayList<T> findHappyAnimals(ArrayList<T> animals) {
/* ... */
}
}
ArrayList<Cat> cats = new ArrayList<>();
/* ... */
ArrayList<Cat> happyCats = AnimalHelper.findHappyAnimals(cats);
Merk op dat we het type T zowel gebruiken bij de animals-parameter als bij het terugkeertype van de methode.
Zo kunnen we garanderen dat de teruggegeven lijst precies hetzelfde type elementen heeft als de lijst animals, zonder dat we al moeten vastleggen welk type dier (bv. Cat of Dog) dat precies is.
Dus: als we een ArrayList<Cat> meegeven aan de methode, krijgen we ook een ArrayList<Cat> terug.
Op dezelfde manier kan je ook het type van meerdere parameters (en eventueel het terugkeertype) aan elkaar vastkoppelen.
In het voorbeeld hieronder zie je een methode die paren kan maken tussen dieren; de methode kan gebruikt worden voor elk type dier, maar kan enkel paren maken van dezelfde diersoort.
Je ziet meteen ook een voorbeeld van een generisch record-type AnimalPair.
class AnimalHelper {
// voorbeeld van een generisch record
public record AnimalPair<T extends Animal>(T male, T female) {}
public static <T extends Animal> ArrayList<AnimalPair<T>> makePairs(
ArrayList<T> males, ArrayList<T> females) {
/* ... */
}
}
ArrayList<Cat> maleCats = ...
ArrayList<Cat> femaleCats = ...
ArrayList<Dog> femaleDogs = ...
ArrayList<AnimalPair<Cat>> pairedCats = makePairs(maleCats, femaleCats); // OK
ArrayList<AnimalPair<Animal>> pairedMix = makePairs(maleCats, femaleDogs); // niet OK (compiler error) 👍
Merk hierboven op hoe, door de parameter T op verschillende plaatsen te gebruiken in de methode, deze methode enkel gebruikt kan worden om twee lijsten met dezelfde diersoorten te koppelen, en er meteen ook gegarandeerd wordt dat de AnimalPair-objecten die teruggegeven worden ook hetzelfde type dier bevatten.
Als het type T niet van belang is omdat het nergens terugkomt (niet in het terugkeertype van de methode, niet bij een andere parameter, en ook niet in de body van de methode), dan heb je strikt gezien geen generische methode nodig.
Zoals we later bij het gebruik van wildcards zullen zien, kan je dan ook gewoon het wildcard-type <? extends X> gebruiken, of <?> indien het type niet begrensd moet worden.
In plaats van
public static <T extends Animal> void feedAll(ArrayList<T> animals) {
// code die T nergens vermeldt
}
kan je dus ook de generische parameter T weglaten, en hetvolgende schrijven:
public static void feedAll(ArrayList<? extends Animal> animals) { /* ... */ }
Dit is nu geen generische methode meer (er wordt geen nieuwe generische parameter geïntroduceerd); de parameter animals maakt wel gebruik van een generisch type.
Je leest deze methode-signatuur als ‘de methode feedAll neemt als parameter een lijst met elementen van een willekeurig (niet nader bepaald) subtype van Animal’.
Onthoud
Er zijn slechts 2 plaatsen waar je een nieuwe generische parameter (een ’letter’ zoals T of U) mag introduceren:
- vlak na de naam van een klasse (of record, interface, …) die je definieert (
class Foo<T> { ... }); of - vlak vóór het terugkeertype van een methode (
public <T> void doSomething(...) { }).
Op alle andere plaatsen waar je naar een generische parameter verwijst (door de letter te gebruiken), moet je ervoor zorgen dat deze eerst gedefinieerd werd op één van deze twee plaatsen.
Meerdere type-parameters
De ArrayList<E>-klasse hierboven had één generische parameter (E).
Een generische klasse of methode kan ook meerdere type-parameters hebben, bijvoorbeeld een tuple van 3 elementen van mogelijk verschillend type (we maken hier een record in plaats van een klasse):
record Tuple3<T1, T2, T3>(T1 first, T2 second, T3 third) {
/* ... */
}
Bij het gebruik van deze klasse (bijvoorbeeld bij het aanmaken van een nieuw object) moet je dan voor elke parameter (T1, T2, en T3) een concreet type opgeven:
Tuple3<String, Integer, String> tuple = new Tuple3<>("John", 2025, "CS101");
Ook hier kan je met de verkorte notatie <> werken om jezelf niet te moeten herhalen.
Note
Het lijkt erg handig om zo’n Tuple-type overal in je code te gebruiken waar je drie objecten samen wil bundelen, maar dat wordt afgeraden.
Niet omdat het drie generische parameters heeft (dat is perfect legitiem), maar wel omdat het niets zegt over de betekenis van de velden (wat zit er in ‘first’, ‘second’, ’third’?).
Gebruik in plaats van een algemene Tuple-klasse veel liever een record waar je de individuele componenten een zinvolle naam geeft.
Bijvoorbeeld: record Enrollment(String student, int year, String courseId) {} of record Point3D(double x, double y, double x) {}.
7.2.2 Generics en subtyping
Stel we hebben klassen Animal, Mammal, Cat, Dog, en Bird met volgende overervingsrelatie:
class Animal { /* ... */ }
class Mammal extends Animal { /* ... */ }
class Cat extends Mammal { /* ... */ }
class Dog extends Mammal { /* ... */ }
class Bird extends Animal { /* ... */ }
graph BT
Cat --> Mammal
Dog --> Mammal
Mammal --> Animal
Bird --> Animal
Een van de basisregels van object-georiënteerd programmeren is dat overal waar een object van type X verwacht wordt, ook een object van een subtype van X toegelaten wordt.
De Java compiler respecteert deze regel uiteraard.
Volgende toekenningen zijn bijvoorbeeld toegelaten:
Animal animal = new Cat();
Mammal mammal = new Dog();
animal = new Bird();
maar mammal = new Bird(); is bijvoorbeeld niet toegelaten, want Bird is geen subtype van Mammal.
In onderstaande code is de eerste oproep toegelaten (cat heeft type Cat, en dat is een subtype van Mammal), maar de tweede niet (cat is geen Dog) en de derde ook niet (Cat is geen subtype van Bird):
static void pet(Mammal mammal) { /* ... */ }
static void bark(Dog dog) { /* ... */ }
static void layEgg(Bird bird) { /* ... */ }
Cat cat = new Cat();
pet(cat); // <- toegelaten (voldoet aan principe)
bark(cat); // <- niet toegelaten (compiler error) 👍
layEgg(cat); // <- niet toegelaten (compiler error) 👍
Subtyping en generische lijsten
Een lijst in Java is een geordende groep van elementen van hetzelfde type.
List<E> is de interface die aan de basis ligt van alle lijsten.
ArrayList<E> is een klasse die een lijst implementeert met behulp van een array.
ArrayList<E> is een subtype van List<E>; dus overal waar een List-object verwacht wordt, mag ook een ArrayList gebruikt worden.
Later (in het hoofdstuk rond Collections) zullen we ook zien dat er een interface Collection<E> bestaat, wat een willekeurige groep van elementen voorstelt: niet enkel een lijst, maar bijvoorbeeld ook verzamelingen (Set) of wachtrijen (Queue).
List<E> is een subtype van Collection<E>. Bijgevolg (via transitiviteit) is ArrayList<E> dus ook subtype van Collection<E>.
In code ziet deze situatie er als volgt uit:
interface Collection<E> {
public void add(E element);
public int size();
/* ... */
}
interface List<E> extends Collection<E> {
public E get(int index);
/* ... */
}
class ArrayList<E> implements List<E> {
private E[] elements;
/* ... */
}
interface Set<E> extends Collection<E> { /* ... */ }
interface Queue<E> extends Collection<E> { /* ... */ }
graph BT
Y1["Set#lt;E>"] --> Z0
X0["ArrayList#lt;E>"] --> Y0["List#lt;E>"] --> Z0["Collection#lt;E>"]
Y2["Queue#lt;E>"] --> Z0
style Y1 fill:#eee,stroke:#aaa,color:#888
style Y2 fill:#eee,stroke:#aaa,color:#888
Volgende code is geldig:
List<Cat> cats = new ArrayList<Cat>();
Collection<Dog> dogs = new ArrayList<Dog>();
List<Animal> animals = new ArrayList<Animal>();
maar hetvolgende kan uiteraard niet:
Collection<Dog> dogs = new ArrayList<Cat>(); // compileert niet 👍
graph BT
X1["ArrayList#lt;Cat>"] --> Y1["List#lt;Cat>"] --> Z1["Collection#lt;Cat>"]
X2["ArrayList#lt;Dog>"] --> Y2["List#lt;Dog>"] --> Z2["Collection#lt;Dog>"]
X3["ArrayList#lt;Animal>"] --> Y3["List#lt;Animal>"] --> Z3["Collection#lt;Animal>"]
Het lijkt intuïtief misschien logisch dat ArrayList<Cat> ook een subtype moet zijn van ArrayList<Animal>.
Een lijst van katten lijkt tenslotte toch een speciaal geval te zijn van een lijst van dieren?
Maar dat is niet het geval.
ArrayList<Animal> = new ArrayList<Cat>(); // compileert niet
graph BT
id1(Niet correct)
style id1 fill:#f99,stroke:#600,stroke-width:4px
X0["ArrayList#lt;Cat>"] -- #times; --> Y0["ArrayList#lt;Animal>"]
Waarom niet?
Stel dat ArrayList<Cat> toch een subtype zou zijn van ArrayList<Animal>. Dan zou volgende code ook geldig zijn:
ArrayList<Cat> cats = new ArrayList<Cat>();
ArrayList<Animal> animals = cats; // <- dit zou geldig zijn (maar is het niet!)
Dog dog = new Dog();
animals.add(dog); // <- OOPS: er zit nu een hond in de lijst van katten 🙁
Je zou dus honden kunnen toevoegen aan je lijst van katten zonder dat de compiler je waarschuwt, en dat is niet gewenst.
Om die reden beschouwt Java ArrayList<Cat> dus niet als subtype van ArrayList<Animal>, ondanks dat Cat wél een subtype van Animal is.
Onthoud
Zelfs als klasse Sub een subtype is van klasse Super, dan is ArrayList<Sub> toch geen subtype van ArrayList<Super>.
Later zullen we zien hoe we hier met wildcards in sommige gevallen wel flexibeler mee kunnen omgaan.
Overerven van een generisch type
Hierboven gebruikten we vooral ArrayList als voorbeeld van een generische klasse.
We hebben echter ook gezien dat je zelf generische klassen kan definiëren, en daarvan kan je uiteraard ook overerven.
Bij de definitie van een subklasse moet je voor de generische parameter van de superklasse een waarde (type) meegeven. Je kan ervoor kiezen om je subklasse zelf generisch te maken (dus een nieuwe generische parameter te introduceren), of om een vooraf bepaald type mee te geven.
Bijvoorbeeld:
class Super<T> { ... }
class SubForAnimal<A extends Animal> extends Super<A> { ... }
class SubForCat extends SubAnimal<Cat> { ... }
De superklasse Super heeft een generische parameter T.
De subklasse SubForAnimal definieert zelf een generische parameter A (hier met begrenzing), en gebruikt parameter A als type voor T uit de superklasse.
De klasse SubForCat tenslotte definieert zelf geen nieuwe generische parameter, maar geeft het type Cat op als type voor parameter A uit diens superklasse.
7.2.3 Wildcards
We zagen eerder dat de types List<Dog> en List<Animal> niets met elkaar te maken hebben, ondanks het feit dat Dog een subtype is van Animal.
Dat geldt in het algemeen voor generische types.
Als beide generische parameters hetzelfde type hebben, bestaat er wel een overervingsrelatie. Bijvoorbeeld, in volgende situatie:
class Shelter<T> { }
class AnimalShelter<A extends Animal> extends Shelter<A> { ... }
is AnimalShelter<Dog> wel degelijk een subtype van Shelter<Dog>, om dezelfde reden dat ArrayList<Dog> een subtype is van List<Dog>.
Volgende toekenning en methode-oproep zijn dus toegelaten:
Shelter<Dog> shelter = new AnimalShelter<Dog>(); // OK! 👍
public void protectDog(Shelter<Dog> s) { ... }
AnimalShelter<Dog> animalShelter = new AnimalShelter<Dog>();
protectDog(animalShelter); // OK! 👍
Dat komt omdat AnimalShelter een subtype is van Shelter, en de generische parameter bij beiden hetzelfde is.
Als de generische parameters verschillend zijn, is er echter geen overervingsrelatie.
Bijvoorveeld, tussen AnimalShelter<Cat> en Shelter<Animal> is er geen overervingsrelatie.
Ook is Shelter<Cat> geen subtype van Shelter<Animal>.
Het volgende is bijgevolg niet toegelaten:
Shelter<Animal> s = new AnimalShelter<Cat>(); // NIET toegelaten
public void protectAnimal(Shelter<Animal> s) { ... }
AnimalShelter<Cat> animalShelter = new AnimalShelter<Cat>(); // wel OK!
protectAnimal(animalShelter); // NIET toegelaten
In sommige situaties willen we wel zo’n overervingsrelatie kunnen maken.
We bekijken daarvoor twee soorten relaties, namelijk covariantie en contravariantie.
Note
Opgelet: Zowel covariantie als contravariantie gaan enkel over het gebruik van generische klassen.
Meer bepaald beïnvloeden ze wanneer twee generische klassen door de compiler als subtype van elkaar beschouwd worden.
Dat staat los van de definitie van een generische klasse — die definities (en bijhorende begrenzing) blijven onveranderd!
Covariantie (extends)
Wat als we een methode copyFromTo willen schrijven die de dieren uit een gegeven (bron-)lijst toevoegt aan een andere (doel-)lijst van dieren? Bijvoorbeeld:
public static void copyFromTo(
ArrayList<Animal> source,
ArrayList<Animal> target) {
for (Animal a : source) { target.add(a); }
}
ArrayList<Animal> animals = new ArrayList<>();
ArrayList<Cat> cats = /* ... */
ArrayList<Dog> dogs = /* ... */
/* ... */
copyFromTo(dogs, animals); // niet toegelaten 🙁
copyFromTo(cats, animals); // niet toegelaten 🙁
Volgens de regels die we hierboven gezien hebben, kunnen we deze methode niet gebruiken om de dieren uit een lijst van honden (ArrayList<Dog>) of katten (ArrayList<Cat>) te kopiëren naar een lijst van dieren (ArrayList<Animal>).
Maar dat lijkt wel een zinnige operatie.
Een oplossing kan zijn om verschillende versies van de methode te schrijven:
public static void copyFromCatsTo(
ArrayList<Cat> source,
ArrayList<Animal> target) {
for (Cat cat : source) { target.add(cat); }
}
public static void copyFromDogsTo(
ArrayList<Dog> source,
ArrayList<Animal> target) {
for (Dog dog : source) { target.add(dog); }
}
public static void copyFromBirdsTo(
ArrayList<Bird> source,
ArrayList<Animal> target) {
for (Bird bird : source) { target.add(bird); }
}
Note
Merk op dat de oproep target.add(cat), alsook die met dog en bird, toegelaten is, omdat Cat, Dog en Bird subtypes zijn van Animal.
Maar dan lopen we opnieuw tegen het probleem van gedupliceerde code aan.
Een eerste oplossing daarvoor is een generische methode, met een generische parameter die begrensd is (T extends Animal):
public static <T extends Animal> void copyFromTo_generic(
ArrayList<T> source,
ArrayList<Animal> target) {
for (Animal a : source) { target.add(a); }
}
Dat werkt, maar de generische parameter T wordt slechts eenmaal gebruikt, namelijk bij de parameter ArrayList<T> source.
In zo’n situatie kunnen we ook gebruik maken van het wildcard-type <? extends X>.
We kunnen bovenstaande methode dus ook zonder generische parameter schrijven als volgt:
public static void copyFromTo_wildcard(
ArrayList<? extends Animal> source,
ArrayList<Animal> target) {
for (Animal a : source) { target.add(a); }
}
Volgende code is nu toegelaten:
copyFromTo_wildcard(dogs, animals); // OK! 👍
copyFromTo_wildcard(cats, animals); // OK! 👍
Het type ArrayList<? extends Animal> staat dus voor “elke ArrayList waar het element-type een (niet nader bepaald) subtype is van Animal”.
Je kan dit ook bekijken alsof het type ArrayList<? extends Animal> tegelijk staat voor de types ArrayList<Animal>, ArrayList<Mammal>, ArrayList<Cat>, ArrayList<Dog>, alsook een lijst van elk ander type dier.
Dit heet covariantie: omdat Cat een subtype is van Animal, is ArrayList<Cat> een subtype van ArrayList<? extends Animal>.
De ‘co’ in covariantie wijst erop dat de overervingsrelatie tussen Cat en Animal in dezelfde richting loopt als die tussen ArrayList<Cat> en ArrayList<? extends Animal> (in tegenstelling tot contravariantie, wat zodadelijk aan bod komt).
Dat zie je op de afbeelding hieronder:
graph BT
ALCat["ArrayList#lt;Cat>"]
ALextendsAnimal["ArrayList#lt;? extends Animal>"]
ALAnimal["ArrayList#lt;Animal>"]
ALAnimal --> ALextendsAnimal
ALCat --> ALextendsAnimal
Cat --> Animal
classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,Cat cat;
class ALAnimal,Animal,ALextendsAnimal animal;
Merk op dat ArrayList<Animal> ook een subtype is van ArrayList<? extends Animal>.
We kunnen ook de relatie met Mammal toevoegen aan het plaatje:
graph BT
ALCat["ArrayList#lt;Cat>"]
ALextendsAnimal["ArrayList#lt;? extends Animal>"]
ALextendsMammal["ArrayList#lt;? extends Mammal>"]
ALextendsCat["ArrayList#lt;? extends Cat>"]
ALAnimal["ArrayList#lt;Animal>"]
ALMammal["ArrayList#lt;Mammal>"]
ALAnimal --> ALextendsAnimal
ALextendsMammal --> ALextendsAnimal
ALMammal --> ALextendsMammal
ALextendsCat --> ALextendsMammal
ALCat --> ALextendsCat
Cat --> Mammal
Mammal --> Animal
classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef mammal fill:#9f9,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,Cat,ALextendsCat cat;
class ALMammal,Mammal,ALextendsMammal mammal;
class ALAnimal,Animal,ALextendsAnimal animal;
Tenslotte kan je in Java ook <?> schrijven (bijvoorbeeld ArrayList<?>); dat is een verkorte notatie voor ArrayList<? extends Object>. Je interpreteert ArrayList<?> dus als een lijst van een willekeurig maar niet gekend type. Merk op dat ArrayList<?> dus niet hetzelfde is als ArrayList<Object>. Een ArrayList<Cat> is een subtype van ArrayList<?>, maar niet van ArrayList<Object>.
Hou er ook rekening mee dat elk voorkomen van ? voor een ander type staat (of kan staan). Hetvolgende kan dus niet:
public void copyMammalsFromTo(
ArrayList<? extends Mammal> source,
ArrayList<? extends Mammal> target) {
for (Mammal m : source) { target.add(m); } // compileert niet! 🙁
}
omdat de eerste ArrayList<? extends Mammal> (source) bijvoorbeeld een ArrayList<Cat> kan zijn, en de tweede (target) een ArrayList<Dog>. Als je de types van beide parameters wil linken aan elkaar, moet je een generische methode gebruiken (zoals eerder gezien):
public <T extends Mammal> void copyMammalsFromTo(
ArrayList<T> source,
ArrayList<T> target) {
for (Mammal m : source) { target.add(m); } // OK! 👍
}
Onderstaande code is ook ongeldig. Waarom?
ArrayList<?> lijst = new ArrayList<String>();
lijst.add("Hello");
Antwoord
De lijst-variabele is gedeclareerd als een ArrayList met elementen van een ongekend type. Op basis van het type van de variabele kan de compiler niet afleiden dat er Strings toegevoegd mogen worden aan de lijst (het zou evengoed een ArrayList van Animals kunnen zijn).
Het feit dat lijst geinititialiseerd wordt met <String> doet hier niet terzake; enkel het type van de declaratie is van belang.
Onthoud
Het type ArrayList<? extends Mammal> staat tegelijk voor de types ArrayList<Mammal>, ArrayList<Cat>, ArrayList<Dog>, en elk ander type dat overerft van Mammal.
Contravariantie (super)
Wat als we een methode willen die de objecten uit een gegeven bronlijst van katten kopieert naar een doellijst van willekeurige dieren? Bijvoorbeeld:
public static void copyFromCatsTo(
ArrayList<Cat> source,
ArrayList<Animal> target) {
for (Cat cat : source) { target.add(cat); }
}
ArrayList<Cat> cats = /* ... */
ArrayList<Cat> otherCats = new ArrayList<>();
ArrayList<Mammal> mammals = new ArrayList<>();
ArrayList<Animal> animals = new ArrayList<>();
copyFromTo(cats, otherCats); // niet toegelaten 🙁
copyFromTo(cats, mammals); // niet toegelaten 🙁
copyFromTo(cats, animals); // OK 👍
De eerste twee copyFromTo-regels zijn niet toegelaten, maar zouden opnieuw erg nuttig kunnen zijn.
Co-variantie met extends helpt ook niet (target zou dan immers ook een ArrayList<Dog> kunnen zijn):
public static void copyFromCatsTo(
ArrayList<Cat> source,
ArrayList<? extends Animal> target) {
for (Cat cat : source) { target.add(cat); } // ook niet toegelaten 🙁
}
En aparte methodes schrijven leidt opnieuw tot code-duplicatie:
public static void copyFromCatsToCats(
ArrayList<Cat> source,
ArrayList<Cat> target) {
for (Cat cat : source) { target.add(a); }
}
public static void copyFromCatsToMammals(
ArrayList<Cat> source,
ArrayList<Mammal> target) {
for (Cat cat : source) { target.add(a); }
}
public static void copyFromCatsToAnimals(
ArrayList<Cat> source,
ArrayList<Animal> target) {
for (Cat cat : source) { target.add(a); }
}
Denkvraag
Zou het nuttig zijn om een methode copyFromCatsToBirds(ArrayList<Cat> source, ArrayList<Bird> target) te voorzien? Waarom (niet)?
De oplossing in dit geval is gebruik maken van het wildcard-type <? super T>.
Het type ArrayList<? super Cat> staat dus voor “elke ArrayList waar het element-type een supertype is van Cat” (inclusief het type Cat zelf).
Of nog: ArrayList<? super Cat> staat tegelijk voor de types ArrayList<Cat>, ArrayList<Mammal>, ArrayList<Animal>, en ArrayList<Object>, alsook elke andere ArrayList met een supertype van Cat als element-type.
We kunnen dus schrijven:
public static void copyFromCatsTo_wildcard(
ArrayList<Cat> source,
ArrayList<? super Cat> target) {
for (Cat cat : source) { target.add(a); }
}
en kunnen nu hetvolgende uitvoeren:
copyFromCatsTo_wildcard(cats, otherCats); // OK 👍
copyFromCatsTo_wildcard(cats, mammals); // OK 👍
copyFromCatsTo_wildcard(cats, animals); // OK 👍
Dit heet contravariantie: hoewel Cat een subtype is van Animal, is ArrayList<? super Cat> een supertype vanArrayList<Animal>.
De ‘contra’ in contravariantie wijst erop dat de overervingsrelatie tussen Cat en Animal in de omgekeerde richting loopt als die tussen ArrayList<? super Cat> en ArrayList<Animal>.
Bekijk volgende figuur aandachtig:
graph BT
ALsuperCat["ArrayList#lt;? super Cat>"]
ALAnimal["ArrayList#lt;Animal>"]
ALCat["ArrayList#lt;Cat>"]
ALAnimal --> ALsuperCat
ALCat --> ALsuperCat
Cat --> Animal
classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef mammal fill:#9f9,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,ALsuperCat,Cat cat;
class ALAnimal,Animal animal;
Als we ook ArrayList<Mammal>, ArrayList<? super Mammal>, en ArrayList<? super Animal> toevoegen aan het plaatje, ziet dat er als volgt uit:
graph BT
ALCat["ArrayList#lt;Cat>"]
ALsuperCat["ArrayList#lt;? super Cat>"]
ALsuperMammal["ArrayList#lt;? super Mammal>"]
ALsuperAnimal["ArrayList#lt;? super Animal>"]
ALMammal["ArrayList#lt;Mammal>"]
ALAnimal["ArrayList#lt;Animal>"]
ALCat --> ALsuperCat
ALAnimal --> ALsuperAnimal
ALMammal --> ALsuperMammal
ALsuperAnimal --> ALsuperMammal
ALsuperMammal --> ALsuperCat
Cat --> Mammal
Mammal --> Animal
classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef mammal fill:#9f9,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,ALsuperCat,Cat cat;
class ALMammal,Mammal,ALsuperMammal mammal;
class ALAnimal,Animal,ALsuperAnimal animal;
Aan de hand van de kleuren kan je snel zien dat de overervingsrelatie links en rechts inderdaad omgekeerd verlopen.
Onthoud
Het type ArrayList<? super Mammal> staat tegelijk voor de types ArrayList<Mammal>, ArrayList<Animal>, ArrayList<Object>, en elk ander type dat een superklasse (of interface) is van Mammal.
Covariantie of contravariantie: PECS
Als we covariantie en contravariantie combineren, krijgen we volgend beeld (we focussen op de extends- en super-relatie vanaf Mammal):
graph BT
ALAnimal["ArrayList#lt;Animal>"]
ALMammal["ArrayList#lt;Mammal>"]
ALCat["ArrayList#lt;Cat>"]
ALsuperMammal["ArrayList#lt;? super Mammal>"]
ALextendsMammal["ArrayList#lt;? extends Mammal>"]
ALMammal --> ALextendsMammal
ALCat --> ALextendsMammal
ALAnimal --> ALsuperMammal
ALMammal --> ALsuperMammal
Cat --> Mammal
Mammal --> Animal
classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef mammal fill:#9f9,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,Cat cat;
class ALMammal,Mammal,ALsuperMammal,ALextendsMammal mammal;
class ALAnimal,Animal animal;
Hier zien we dat ArrayList<? extends Mammal> (covariant) als subtypes ArrayList<Mammal> en ArrayList<Cat> heeft.
Het contravariante ArrayList<? super Mammal> heeft óók ArrayList<Mammal> als subtype, maar ook ArrayList<Animal>.
Hoe weet je nu wanneer je wat gebruikt als type voor een parameter? Wanneer kies je <? extends T>, en wanneer <? super T>?
Een goede vuistregel is het acroniem PECS, wat staat voor Producer Extends, Consumer Super.
Dus:
- Wanneer het object gebruikt wordt als een producent van
T’s (met andere woorden, het object is een levancier van T-objecten voor jouw code, die ze vervolgens gebruikt), gebruik je <? extends T>. Dat is logisch: als jouw code met aangeleverde T’s omkan, dan kan jouw code ook om met de aanlevering van een subklasse van T (basisprincipe objectgeoriënteerd programmeren). - Wanneer het object gebruikt wordt als een consument van
T’s (met andere woorden, het neemt T-objecten aan van jouw code), gebruik je <? super T>. Ook dat is logisch: een object dat beweert om te kunnen met elke superklasse van T moet zeker overweg kunnen met een T die jouw code aanlevert. - Wanneer het object zowel als consument als als producent gebruikt wordt, gebruik je gewoon
<T> (dus geen co- of contra-variantie). Er is dan weinig tot geen flexibiliteit meer in het type.
Een voorbeeld om PECS toe te passen: we willen een methode copyFromTo die zo flexibel mogelijk is, om elementen uit een lijst van zoogdieren te kopiëren naar een andere lijst.
void copyMammalsFromTo(
??? source,
??? target) {
for (Mammal m : source) {
target.add(m);
}
}
De source-lijst is de producent: daaruit halen we Mammal-objecten op. Daar gebruiken we dus extends:
void copyMammalsFromTo(
List<? extends Mammal> source,
??? target) {
for (Mammal m : source) {
target.add(m);
}
}
De target-lijst is de consument: daar sturen we Mammal-objecten naartoe. Daar gebruiken we dus super:
void copyMammalsFromTo(
List<? extends Mammal> source,
List<? super Mammal> target) {
for (Mammal m : source) {
target.add(m);
}
}
Met deze methode kunnen we nu alle zinvolle operaties uitvoeren, terwijl de zinloze operaties tegengehouden worden door de compiler:
ArrayList<Cat> cats = /* ... */
ArrayList<Dog> dogs = /* ... */
ArrayList<Bird> birds = /* ... */
ArrayList<Mammal> mammals = /* ... */
ArrayList<Animal> animals = /* ... */
copyMammalsFromTo(cats, animals); // OK 👍
copyMammalsFromTo(cats, mammals); // OK 👍
copyMammalsFromTo(cats, cats); // OK 👍
copyMammalsFromTo(mammals, animals); // OK 👍
copyMammalsFromTo(cats, dogs);
// compiler error (Dog is geen supertype van Mammal) 👍
copyMammalsFromTo(birds, animals);
// compiler error (Bird is geen subtype van Mammal) 👍
Merk op dat het type Mammal in onze laatste versie van copyMammalsFromTo hierboven eigenlijk onnodig is. We kunnen de methode nog verder veralgemenen door er een generische methode van te maken, die werkt voor alle lijsten (niet enkel lijsten van zoogdieren):
<T> void copyFromTo(
List<? extends T> source,
List<? super T> target) {
for (T element : source) {
target.add(element);
}
}
Met deze versie kunnen we nu bijvoorbeeld ook Birds kopiëren naar een lijst van dieren:
copyFromTo(birds, animals); // OK 👍
Opmerking
Wanneer een parameter zowel een producent (co-variant) als een consument (contra-variant) is, gebruik je geen wildcards.
De generische parameter heet dan invariant.
Bijvoorbeeld:
public static <T> void reverse(List<T> list) {
int left = 0;
int right = list.size() - 1;
while (left < right) {
// Producent (get)
T temp = list.get(left);
// Consumer (set)
list.set(left, list.get(right));
list.set(right, temp);
left++;
right--;
}
}
Arrays en type erasure
In tegenstelling tot ArrayLists (en andere generische types), beschouwt Java arrays wél altijd als covariant.
Dat betekent dat Cat[] een subtype is van Animal[].
Volgende code compileert dus (maar gooit een uitzondering bij het uitvoeren):
Animal[] cats = new Cat[2];
cats[0] = new Dog(); // compileert, maar faalt tijdens het uitvoeren
De reden hiervoor is, in het kort, dat informatie over generics gewist wordt bij het compileren van de code.
Dit heet type erasure.
In de gecompileerde code is een ArrayList<Animal> en ArrayList<Cat> dus exact hetzelfde.
Er kan dus, tijdens de uitvoering, niet gecontroleerd worden of je steeds het juiste type gebruikt.
Daarom moet de compiler dat doen, en die neemt het zekere voor het onzekere: alles wat mogelijk fout zou kunnen aflopen, wordt geweigerd.
Bij arrays wordt er wel type-informatie bijgehouden na het compileren, en kan dus tijdens de uitvoering nog gecontroleerd worden of je geen elementen met een ongeldig type toevoegt. De compiler hoeft het niet af te dwingen — maar het wordt wel nog steeds gecontroleerd tijdens de uitvoering, en kan leiden tot een exception.
Aandachtspunten
Enkel bij generische types!
Tenslotte nog een opmerking (op basis van vaak gemaakte fouten op examens).
Co- en contra-variantie (extends, super, en wildcards dus) zijn enkel van toepassing op generische types.
Alles wat we hierboven gezien hebben is dus enkel nuttig op plaatsen waar je een generisch type (List<T>, Food<T>, …) gebruikt voor een parameter, terugkeertype, variabele, ….
Dergelijke types kan je met behulp van co-/contra-variantie en wildcards verrijken tot bijvoorbeeld List<? extends T>, Food<? super T>, …
Maar je kan deze constructies niet gebruiken op plaatsen waar een gewoon type verwacht wordt, bijvoorbeeld bij een parameter of terugkeertype.
Onderstaande regels code zijn dus allemaal ongeldig:
public void pet(? extends Mammal mammal) { ... } // ONGELDIG! ❌
public void pet(<? extends Mammal> mammal) { ... } // ONGELDIG! ❌
public void pet(<? super Cat> mammal) { ... } // ONGELDIG! ❌
Schrijf in dat geval gewoon
public void pet(Mammal mammal) { ... }
Deze methode kan óók al opgeroepen worden met een Cat-object, Dog-object, of elk ander type Mammal als argument.
Je hebt hier geen co- of contra-variantie van generische types nodig; je maakt gewoon gebruik van overerving uit objectgeoriënteerd programmeren.
Onthoud
Wildcards (?), co-variantie (? extends) en contra-variantie (? super) zijn enkel van toepassing bij generische types! Je kan ze dus niet gebruiken als een op zichzelf staand type. Je kan ze ook niet gebruiken bij de definitie van een nieuwe generische parameter (voor een klasse of methode), maar enkel bij het gebruik ervan.
Bounds vs. co-/contravariantie en wildcards
Tot slot is het nuttig om nog eens te benadrukken dat er een verschil is tussen het begrenzen van een generische parameter (met extends) enerzijds, en het gebruik van co-variantie, contra-variantie en wildcards (? extends T, ? super T) anderzijds. Het feit dat extends in beide gevallen gebruikt wordt, kan misschien tot wat verwarring leiden.
Een begrenzing (via <T extends SomeClass>) beperkt welke types geldige waarden zijn voor de type-parameter T. Dus: elke keer wanneer je een concreet type wil meegeven in de plaats van T moet dat type voldoen aan bepaalde eisen.
Je kan zo’n begrenzing enkel aangeven op de plaats waar je een nieuwe generische parameter (T) introduceert (dus bij een nieuwe klasse-definitie of methode-definitie).
Bijvoorbeeld: class Food<T extends Animal> laat later enkel toe om Food<X> te schrijven als type wanneer X ook een subtype is van Animal.
Door co- en contra-variantie (met <? extends X> en <? super X>) te gebruiken verbreed je de toegelaten types.
Een methode-parameter met als type Food<? extends Animal> laat een Food<Animal> toe als argument, maar ook een Food<Cat> of Food<Dog>.
Omgekeerd zal een parameter met als type Food<? super Cat> een Food<Cat> toelaten, maar ook een Food<Animal>.
Er wordt in beide gevallen dus meer toegelaten, wat meer flexibiliteit biedt.
Je kan co- en contravariantie toepassen op elke plaats waar je een generisch type gebruikt (en waar dat gepast is volgens de PECS regels).
Het kan dus perfect zijn dat je de ene keer in je code eens Food<Cat> gebruikt, ergens anders Food<? extends Cat>, en nog ergens anders Food<? super Cat>.
Bij begrenzing is dat niet zo; dat legt de grenzen eenmalig vast, en die moeten overal gerespecteerd worden waar het generisch type gebruikt wordt.
Onthoud
Een begrenzing (T extends X) is een eenmalige beperking op het type dat gebruikt kan worden als waarden voor een nieuw geïntroduceerde generische parameter. Dit kan enkel voorkomen in de definitie van een nieuwe generische parameter (bij een generische klasse of methode).
Co-en contravariantie (? extends X, ? super X) met wildcard ? versoepelen de types die aanvaard worden door de compiler. Ze komen enkel voor op plaatsen waar een generisch type gebruikt wordt.
Arrays met generisch type
Als je een array wil maken van een generisch type, laat de Java-compiler dat niet toe:
class MyClass<T> {
private T[] array;
public MyClass() {
array = new T[10]; // <-- niet toegelaten ☹️
}
}
De reden is opnieuw type erasure.
Aangezien arrays covariant zijn, moet tijdens de uitvoering gecontroleerd kunnen worden of objecten die in de array terechtkomen een geschikt type hebben.
Aangezien generische parameters verwijderd worden door de compiler, kan dat niet.
Een oplossing voor bovenstaand probleem is om een cast toe te voegen. Met een @SuppressWarning annotatie kan je de waarschuwing die door de compiler gegeven wordt negeren.
class MyClass<T> {
private T[] array;
@SuppressWarning("unchecked")
public MyClass() {
array = (T[])new Object[10]; // <-- ok! 👍
}
}
Het is natuurlijk ook mogelijk om gewoon een ArrayList te gebruiken; dan heb je dit probleem niet.
class MyClass<T> {
private ArrayList<T> list;
public MyClass() {
list = new ArrayList<>(); // <-- ok! 👍
}
}
Oefeningen
Voor de tests maken we gebruik van assertJ.
Maybe-klasse
- Schrijf een generische klasse (of record)
Maybe die een object voorstelt dat nul of één waarde van een bepaald type kan bevatten.
Dat type wordt bepaald door een generische parameter. Je kan Maybe-objecten enkel aanmaken via de statische methodes some en none.
Hieronder vind je twee tests:
@Test
public void maybeWithValue() {
Maybe<String> maybe = Maybe.some("Yes");
assertThat(maybe.hasValue()).isTrue();
assertThat(maybe.getValue()).isEqualTo("Yes");
}
@Test
public void maybeWithoutValue() {
Maybe<String> maybe = Maybe.none();
assertThat(maybe.hasValue()).isFalse();
assertThat(maybe.getValue()).isNull();
}
- Maak de
print-methode hieronder ook generisch, zodat deze niet enkel werkt voor een Maybe<String> maar ook voor andere types dan String.
class MaybePrint {
public static void print(Maybe<String> maybe) {
if (maybe.hasValue()) {
System.out.println("Contains a value: " + maybe.getValue());
} else {
System.out.println("No value :(");
}
}
public static void main(String[] args) {
Maybe<String> maybeAString = Maybe.some("yes");
Maybe<String> maybeAnotherString = Maybe.none();
print(maybeAString);
print(maybeAnotherString);
}
}
- Voeg aan
Maybe een generische methode map toe die een java.util.function.Function<T, R>-object als parameter heeft, en die een nieuw Maybe-object teruggeeft, met daarin het resultaat van de functie toegepast op het element als er een element is, of een leeg Maybe-object in het andere geval.
Zie de tests hieronder voor een voorbeeld van hoe deze map-functie gebruikt wordt:
@Test
public void maybeMapWithValue() {
Maybe<String> maybe = Maybe.some("Hello");
Maybe<Integer> result = maybe.map((str) -> str.length());
assertThat(result.hasValue()).isTrue();
assertThat(result.getValue()).isEqualTo(5);
}
@Test
public void maybeMapWithValue2() {
Maybe<String> maybe = Maybe.some("Hello");
Maybe<String> result = maybe.map((str) -> str + "!");
assertThat(result.hasValue()).isTrue();
assertThat(result.getValue()).isEqualTo("Hello!");
}
@Test
public void maybeMapWithoutValue() {
Maybe<String> maybe = Maybe.none();
Maybe<Integer> result = maybe.map((str) -> str.length());
assertThat(result.hasValue()).isFalse();
}
- (optioneel) Herschrijf
Maybe als een sealed interface met twee record-subklassen None en Some.
Geef een voorbeeld van hoe je deze klasse gebruikt met pattern matching.
Kan je ervoor zorgen dat je getValue() nooit kan oproepen als er geen waarde is (compiler error)?
Info
Java bevat een ingebouwd type gelijkaardig aan de Maybe-klasse uit deze oefening, namelijk Optional<T>.
Repository
Schrijf een generische klasse Repository die een repository van objecten voorstelt. De objecten hebben ook een ID. Zowel het type van objecten als het type van de ID moeten generische parameters zijn.
Definieer en implementeer volgende methodes (maak gebruik van een ArrayList):
add(id, obj): toevoegen van een objectfindById(id): opvragen van een object aan de hand van de idfindAll(): opvragen van alle objecten in de repositoryupdate(id, obj): vervangen van een object met gegeven id door het meegegeven objectremove(id): verwijderen van een object aan de hand van een id
SuccessOrFail
Schrijf een generische klasse (of record) SuccessOrFail die een object voorstelt dat precies één element bevat.
Dat element heeft 1 van 2 mogelijke types (die types zijn generische parameters).
Het eerste type stelt het type van een succesvol resultaat voor; het tweede type is dat van een fout.
Je kan objecten enkel aanmaken via de statische methodes success en fail.
Een voorbeeld van tests voor die klasse vind je hieronder:
@Test
public void success() {
SuccessOrFail<String, Exception> result = SuccessOrFail.success("This is the result");
assertThat(result.isSuccess()).isTrue();
assertThat(result.successValue()).isEqualTo("This is the result");
}
@Test
public void failure() {
SuccessOrFail<String, Exception> result = SuccessOrFail.fail(new IllegalStateException());
assertThat(result.isSuccess()).isFalse();
assertThat(result.failValue()).isInstanceOf(IllegalStateException.class);
}
Subtyping: voertuigen
Vetrek van volgende klasse-hiërarchie en zeg van elk van volgende lijnen code of ze toegelaten worden door de Java compiler:
graph BT
Bike --> Vehicle
Motorized --> Vehicle
Car --> Motorized
Plane --> Motorized
/* 1 */ Motorized myCar = new Car();
/* 2 */ Vehicle yourPlane = new Plane();
/* 3 */ Collection<Vehicle> vehicles = new ArrayList<Vehicle>();
/* 4 */ vehicles.add(myCar);
/* 5 */ List<Car> cars = new ArrayList<Car>();
/* 6 */ List<Vehicle> carsAsVehicles = cars;
Antwoord
Alles behalve lijn 6 is toegelaten.
Covariantie
Maak een schema met de overervingsrelaties tussen
List<Cat>List<? extends Cat>ArrayList<Cat>ArrayList<? extends Cat>List<Animal>List<? extends Animal>ArrayList<Animal>ArrayList<? extends Animal>
Antwoord
graph BT
ALC["ArrayList#lt;Cat>"] --> LC["List#lt;Cat>"]
ALC --> ALeC["ArrayList#lt;? extends Cat>"]
LC --> LeC["List#lt;? extends Cat>"]
ALeC --> LeC
ALeC --> ALeA["ArrayList#lt;? extends Animal>"]
ALA["ArrayList#lt;Animal>"] --> ALeA
ALA --> LA["List#lt;Animal>"]
LeC --> LeA["List#lt;? extends Animal>"]
ALeA --> LeA
LA --> LeA
ArrayList<Cat> is een subtype van List<Cat> en van ArrayList<? extends Cat>.List<Cat> is een subtype van List<? extends Cat>ArrayList<? extends Cat> is een subtype van List<? extends Cat> en van ArrayList<? extends Animal>ArrayList<Animal> is een subtype van ArrayList<? extends Animal> en List<Animal>List<? extends Cat>, ArrayList<? extends Animal> en List<Animal> zijn alledrie subtypes van List<? extends Animal>
Shop
Maak een klasse Shop die een winkel voorstelt die items (subklasse van StockItem) aankoopt.
Een Shop-object wordt geparametriseerd met het type items dat aangekocht kan worden. We beschouwen hier Fruit en Electronics; daarmee kunnen we dus een fruitwinkel (Shop<Fruit>) en elektronica-winkel (Shop<Electronics>) maken.
Shop heeft twee methodes:
buy, die een lijst van items toevoegt aan de stock;addStockToInventory, die de lijst van items in stock toevoegt aan de meegegeven inventaris-lijst.
Voor het fruit maak je een abstracte klasse Fruit, en subklassen Apple en Orange.
Maak daarnaast nog een abstracte klasse Electronics, met als subklasse Smartphone.
Zorg dat onderstaande code (ongewijzigd) compileert en dat de test slaagt:
@Test
public void testGenerics() {
Shop<Fruit> fruitShop = new Shop<>();
Shop<Electronics> electronicsShop = new Shop<>();
List<Apple> apples = List.of(new Apple(), new Apple());
List<Fruit> oranges = List.of(new Orange(), new Orange(), new Orange());
List<Smartphone> phones = List.of(new Smartphone(), new Smartphone());
fruitShop.buy(apples);
fruitShop.buy(oranges);
electronicsShop.buy(phones);
List<StockItem> inventory = new ArrayList<>();
fruitShop.addStockToInventory(inventory);
Assertions.assertThat(inventory).hasSize(5);
electronicsShop.addStockToInventory(inventory);
Assertions.assertThat(inventory).hasSize(7);
}
Functie compositie
Java bevat een ingebouwde interface java.util.function.Function<T, R>, wat een functie voorstelt met één parameter van type T, en een resultaat van type R. Deze interface voorziet 1 methode R apply(T value) om de functie uit te voeren.
Schrijf nu een generische methode compose die twee functie-objecten als parameters heeft, en als resultaat een nieuwe functie teruggeeft die de compositie voorstelt: eerst wordt de eerste functie uitgevoerd, en dan wordt de tweede functie uitgevoerd op het resultaat van de eerste.
Dus: voor functies
Function<A, B> f1 = ...
Function<B, C> f2 = ...
moet compose(f1, f2) een Function<A, C> teruggeven, die als resultaat f2.apply(f1.apply(a)) teruggeeft.
Pas de PECS-regel toe om ook functies te kunnen samenstellen die niet exact overeenkomen qua type.
Bijvoorbeeld, volgende code moet compileren en de test moet slagen:
interface Ingredient {}
record Fruit() implements Ingredient {}
record PeeledFruit(Fruit fruit) implements Ingredient {}
record Chopped(Ingredient food) implements Ingredient {}
@Test
public void testCompose() {
Function<Fruit, PeeledFruit> peelFruit = (var fruit) -> new PeeledFruit(fruit);
Function<Ingredient, Chopped> chopIngredient = (var food) -> new Chopped(food);
var makeFruitSalad = compose(peelFruit, chopIngredient);
assertThat(makeFruitSalad.apply(new Fruit())).isEqualTo(new Chopped(new PeeledFruit(new Fruit())));
}
Game engine
Oud-examenvraag
Dit is een oud-examenvraag.
Vul de types en generische parameters aan op de 7 genummerde plaatsen zodat onderstaande code en main-methode compileert (behalve de laatste regel van de main-methode) en voldaan is aan volgende voorwaarden:
- Elk actie-type kan enkel uitgevoerd worden door een bepaald karakter-type. Bijvoorbeeld: een FightAction kan enkel uitgevoerd worden door een karakter dat CanFight implementeert.
- doAction mag enkel opgeroepen worden met een actie die uitgevoerd kan worden door alle karakters in de meegegeven lijst.
Als er op een bepaalde plaats geen type of generische parameter nodig is, vul je $\emptyset$ in.
- Verklaar je keuze voor de combinatie van (5), (6), en (7).
interface Character {}
interface CanFight extends Character {}
record Warrior() implements CanFight {}
record Knight() implements CanFight {}
record Wizard() implements Character {}
interface Action<___/* 1 */___> {
void execute(___/* 2 */____ character);
}
class FightAction implements Action<___/* 3 */_____> {
@Override
public void execute(___/* 4 */______ character) {
System.out.println(character + " fights!");
}
}
class GameEngine {
public <___/* 5 */______> void doAction(
List<___/* 6 */____> characters,
Action<___/* 7 */____> action) {
for (var character : characters) {
action.execute(character);
}
}
}
public static void main(String[] args) {
var engine = new GameEngine();
Action<CanFight> fight = new FightAction();
List<Warrior> warriors = List.of(new Warrior(), new Warrior());
engine.doAction(warriors, fight);
List<Wizard> wizards = List.of(new Wizard());
engine.doAction(wizards, fight); // deze regel mag NIET compileren
}
Antwoord
- 1:
C extends Character : acties kunnen enkel uitgevoerd worden door subtypes van Character - 2:
C: C is het type van Character dat de actie zal uitvoeren - 3:
CanFight: FightAction is enkel mogelijk voor characters die CanFight implementeren - 4:
CanFight: aangezien de generische paremeter C van superinterface Action geinitialiseerd werd met CanFight, moet hier ook CanFight gebruikt worden. - 5:
T extends Character: we noemen T het type van de objecten in de meegeven lijst; we hebben hier een begrenzing nodig (want we willen enkel subtypes van Character toelaten) - 6:
T: lijst van T’s, zoals verondersteld in 5 - 7:
? super T: de meegegeven actie moet een actie zijn die door alle T’s uitgevoerd kan worden (dus door T of een van de supertypes van T).
Redenering met behulp van PECS: de meegegeven actie gebruikt/consumeert het character, dus super.
Alternatieve keuze voor 5/6/7:
- 5:
T extends Character: we noemen T het type dat bij de actie hoort; we hebben hier een begrenzing nodig (want we willen enkel subtypes van Character toelaten) - 6:
? extends T: lijst van T’s of subtypes ervan.
Redenering met behulp van PECS: de lijst levert/produceert de characters, dus extends. - 7:
T: het type van de actie, zoals verondersteld in 5
Animal food
Dit is een uitdagende oefening, voor als je je kennis over generics echt wil testen.
Voeg generics (met grenzen/bounds) toe aan de code hieronder, zodat de code (behalve de laatste regel) compileert,
en de compiler enkel toelaat om kattenvoer te geven aan katten, en hondenvoer aan honden:
public class AnimalFood {
static class Animal {
public void eat(Food food) {
System.out.println(this.getClass().getSimpleName() + " says 'Yummie!'");
}
}
static class Mammal extends Animal {
public void drink(Milk milk) {
this.eat(milk);
}
}
static class Cat extends Mammal {}
static class Kitten extends Cat {}
static class Dog extends Mammal {}
static class Food {}
static class Milk extends Food {}
static class Main {
public static void main(String[] args) {
Food catFood = new Food();
Milk catMilk = new Milk();
Food dogFood = new Food();
Milk dogMilk = new Milk();
Cat cat = new Cat();
Dog dog = new Dog();
Kitten kitten = new Kitten();
cat.eat(catFood); // OK 👍
cat.drink(catMilk); // OK 👍
dog.eat(dogFood); // OK 👍
dog.drink(dogMilk); // OK 👍
kitten.eat(catFood); // OK 👍
kitten.drink(catMilk); // OK 👍
cat.eat(dogFood); // <- moet een compiler error geven! ❌
kitten.eat(dogFood); // <- moet een compiler error geven! ❌
kitten.drink(dogMilk); // <- moet een compiler error geven! ❌
}
}
}
(Hint: Begin met het type Food te parametriseren met een generische parameter die het Animal-type voorstelt dat dit voedsel eet.)
Self-type
Dit is een uitdagende oefening, voor als je je kennis over generics echt wil testen.
Heb je je al eens afgevraagd hoe assertThat(obj) uit AssertJ werkt?
Afhankelijk van het type van obj dat je meegeeft, worden er andere assertions beschikbaar die door de compiler aanvaard worden:
// een List<String>
List<String> someListOfStrings = List.of("hello", "there", "how", "are", "you");
assertThat(someListOfStrings).isNotNull().hasSize(5).containsItem("hello");
// een String
String someString = "hello";
assertThat(someString).isNotNull().isEqualToIgnoringCase("hello");
// een Integer
int someInteger = 4;
assertThat(someInteger).isNotNull().isGreaterThan(4);
assertThat(someInteger).isNotNull().isEqualToIgnoringCase("hello"); // <= compileert niet ❌
Sommige assertions (zoals isNotNull) zijn echter generiek, en wil je slechts op 1 plaats implementeren.
Probeer zelf een assertThat-methode te schrijven die werkt zoals bovenstaande, maar waar isNotNull slechts op 1 plaats geïmplementeerd is.
De assertThat-methode moet een Assertion-object teruggeven, waarop de verschillende methodes gedefinieerd zijn afhankelijk van het type dat meegegeven wordt aan assertThat.
Hint 1: maak verschillende klassen, bijvoorbeeld ListAssertion, StringAssertion, IntegerAssertion die de type-specifieke methodes bevatten. Begin met isNotNull toe te voegen aan elk van die klassen (dus door de implementatie te kopiëren).
Hint 2: in een zogenaamde ‘fluent interface’ geeft elke operatie zoals isNotNull en hasSize het this-object op het einde terug (return this), zodat je oproepen na elkaar kan doen. Bijvoorbeeld .isNotNull().hasSize(5).
Hint 3: maak nu een abstracte klasse GenericAssertion die isNotNull bevat, en waarvan de andere assertions overerven. Verwijder de andere implementaties van isNotNull.
Hint 4: In isNotNull is geen informatie beschikbaar over het type dat gebruikt moet worden als terugkeertype van isNotNull. assertThat(someString).isNotNull() moet bijvoorbeeld opnieuw een StringAssertion teruggeven. Dat kan je oplossen met generics, en een abstracte methode die het juiste object teruggeeft.
Hint 5: Je zal een zogenaamd ‘self-type’ moeten gebruiken. Dat is een generische parameter die wijst naar de (sub)klasse zelf.
Hint 6: op deze pagina wordt uitgelegd hoe AssertJ dit doet. Probeer eerst zelf, zonder dit te lezen!
Subsections of 7.3 Collections
7.3.1 Tijdscomplexiteit
Tijdscomplexiteit is een essentieel begrip bij de analyse van algoritmes (en bijhorende gegevensstructuren).
Met tijdscomplexiteit wordt gekwantificeerd hoe snel een algoritme zijn invoer verwerkt.
Het is dus een eigenschap van een (implementatie van een) algoritme, naast bijvoorbeeld de correctheid en leesbaarheid van dat algoritme.
In tegenstelling tot wat je misschien zou denken, wordt er bij tijdscomplexiteit niet gekeken naar de tijd (in seconden).
In plaats daarvan wordt het totale aantal operaties dat uitgevoerd wordt geteld.
Daarenboven worden niet alle operaties geteld; er wordt een keuze gemaakt voor een verzameling basisoperaties.
Het voordeel hiervan is dat, in tegenstelling tot de reële tijd, het aantal operaties niet afhankelijk is van de snelheid van de processor.
Bijvoorbeeld, bij sorteeralgoritmes wordt soms de vergelijking tussen twee elementen als (enige) basisoperatie gebruikt, of soms elke operatie die een element uit de te sorteren rij opvraagt of aanpast.
Het totale aantal uitgevoerde basisoperaties is dan (bij benadering) een maat voor de uitvoeringstijd van het algoritme, aangezien elke basisoperatie een bepaalde reële uitvoeringstijd heeft op een machine.
Voor de meeste algoritmes zal een grotere invoer leiden tot meer uit te voeren operaties (denk aan een lus die vaker herhaald wordt).
Grotere invoer leidt dus tot meer operaties, en daardoor tot een langere uitvoeringstijd.
Zo is het bijvoorbeeld niet meer dan logisch dat een hele lange lijst sorteren langer duurt dan een heel korte lijst sorteren.
De grootte van de invoer wordt met \(n\) aangeduid; de tijdscomplexiteit van het algoritme in functie van de invoergrootte met de functie \(T(n)\).
Best, worst, average case
We maken bij tijdscomplexiteit onderscheid tussen:
- Best case: een invoer (van een bepaalde grootte \( n \)) die leidt tot de best mogelijke (kortste) uitvoeringstijd. Bijvoorbeeld, sommige sorteeralgoritmes doen minder werk (en zijn dus snel klaar) als de lijst al gesorteerd blijkt te zijn.
- Worst case: een invoer (van een bepaalde grootte \( n \)) die leidt tot de slechtst mogelijke (langste) uitvoeringstijd. Bijvoorbeeld, sommige sorteeralgoritmes hebben erg veel last met een omgekeerd gesorteerde lijst: ze moeten dan heel veel operaties uitvoeren om de lijst gesorteerd te krijgen.
- Average case: een invoer (van een bepaalde grootte \( n \)) waarover we niets weten en geen veronderstellingen kunnen of willen maken. Bijvoorbeeld, voor sorteeralgoritmes kan dit een willekeurige volgorde (permutatie) van de elementen zijn, zonder speciale structuur. De uitvoeringstijd in de average case zal ergens tussen die van de worst case en best case liggen.
Worst- en best-case zijn in veel gevallen redelijk eenvoudig te bepalen. De average case wordt vaak complexer.
Belangrijk om te onthouden is dat worst/best/average case dus niet gaan over een kleinere of grotere invoer, maar wel over hoe die invoer eruit ziet of gestructureerd is.
Bijvoorbeeld, de best case voor een sorteeralgoritme is niet een lege lijst. Hoewel er in dat geval amper operaties uitgevoerd moeten worden, zegt dat niet veel: het is immers niet meer dan logisch dat een kleinere invoer ook minder tijd vraagt.
Wat we wel willen weten is bijvoorbeeld wélke lijst (van alle mogelijke lijsten van lengte \(n=1000\), bijvoorbeeld) het langst duurt om te sorteren met dat bepaald algoritme.
Voorbeeld: selection sort
Hieronder vind je een voorbeeld-implementatie van selection sort, een eenvoudig sorteeralgoritme.
In elke iteratie van de lus wordt het reeds gesorteerde deel van de lijst (dat is het deel vóór index startUnsorted) uitgebreid met 1 element, namelijk het kleinste nog niet gesorteerde element. Dat element wordt gezocht met de hulpfunctie indexOfSmallest, dewelke de index van het kleinste element in de lijst teruggeeft vanaf een bepaalde index start.
Dat kleinste element wordt vervolgens omgewisseld met het element op plaats startUnsorted.
Dat zoeken en omwisselen blijven we doen tot de hele lijst gesorteerd is.
Bijvoorbeeld, in de vierde iteratie van de lus ziet de situatie er als volgt uit net voordat de swap-operatie uitgevoerd wordt:
block-beta
columns 1
block:before
columns 8
e0["A"] e1["B"] e2["C"] e3["H"] e4["F"] e5["G"] e6["E"] e7["D"]
idx0["0"] idx1["1"] idx2["2"] idx3["startUnsorted=3"] idx4["4"] idx5["5"] idx6["6"] idx7["indexSmallest=7"]
end
classDef ok fill:#6c6,stroke:#393,color:#fff
classDef min fill:#66c,stroke:#339,color:#fff
classDef curr stroke-width:3
classDef index fill:none,stroke:none,color:black,font-size:0.7rem
class e0,e1,e2 ok
class e7 min
class e3 curr
class idx0,idx1,idx2,idx3,idx4,idx5,idx6,idx7 indexEn in de vijfde iteratie als volgt:
block-beta
columns 1
block:before
columns 8
e0["A"] e1["B"] e2["C"] e3["D"] e4["F"] e5["G"] e6["E"] e7["H"]
idx0["0"] idx1["1"] idx2["2"] idx3["3"] idx4["startUnsorted=4"] idx5["5"] idx6["indexSmallest=6"] idx7["7"]
end
classDef ok fill:#6c6,stroke:#393,color:#fff
classDef min fill:#66c,stroke:#339,color:#fff
classDef curr stroke-width:3
classDef index fill:none,stroke:none,color:black,font-size:0.7rem
class e0,e1,e2,e3 ok
class e6 min
class e4 curr
class idx0,idx1,idx2,idx3,idx4,idx5,idx6,idx7 indexpublic static <E extends Comparable<E>> void selectionSort(ArrayList<E> list) {
for (int startUnsorted = 0; startUnsorted < list.size(); startUnsorted++) {
int indexSmallest = indexOfSmallest(list, startUnsorted);
Collections.swap(list, startUnsorted, indexSmallest);
}
}
private static <E extends Comparable<E>> int indexOfSmallest(List<E> list, int start) {
if (start >= list.size()) return -1;
int indexSmallestSoFar = start;
E smallestSoFar = list.get(start);
for (int i = start+1; i < list.size(); i++) {
E candidate = list.get(i);
if (candidate.compareTo(smallestSoFar) < 0) {
indexSmallestSoFar = i;
smallestSoFar = candidate;
}
}
return indexSmallestSoFar;
}
Note
Merk op hoe de functie het generische type <E extends Comparable<E>> gebruikt.
Dat legt op dat de elementen (aangeduid met generische type E) bovendien de interface Comparable<E> moeten implementeren, waardoor ze met elkaar vergeleken kunnen worden via de compareTo-methode (gebruikt in indexOfSmallest).
Ingebouwde Java-klassen zoals String, Integer, etc. implementeren Comparable, waardoor deze methode gebruikt kan worden om lijsten van Strings te sorteren.
Als je deze methode wil gebruiken om objecten van je eigen klasse (bijvoorbeeld Person) te sorteren, zal je Person-klasse ook de interface Comparable moeten implementeren om aan te geven hoe personen met elkaar vergeleken moeten worden.
Basisoperaties tellen
Afhankelijk van het type algoritme kunnen we verschillende operaties als basisoperatie kiezen.
Als we voor selection sort als enige basisoperatie de methode compareTo nemen, dan zal voor een lijst van lengte \(n\):
- tijdens de eerste iteratie het element op index 0 vergeleken worden met alle volgende \(n-1\) elementen;
- tijdens de tweede iteratie het element op index 1 vergeleken worden met alle volgende \(n-2\) elementen;
- etc.
- tijdens iteratie \(n-1\) het element op index \(n-2\) vergeleken worden met het laatste element;
- tijdens iteratie \(n\) het element op index \(n-1\) met geen enkel element vergeleken worden.
Er gebeuren in totaal dus
\( T(n) = (n-1) + (n-2) + \ldots + 1 + 0 = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \) vergelijkingen van elementen via compareTo.
Daaruit kunnen we ook afleiden dat, als we de invoer 10 keer groter maken, we
\( \frac{T(10n)}{T(n)} = \frac{(10n)^2/2-10n/2}{n^2/2-n/2} = 100 + 90/(n-1) \)
keer zoveel operaties uitvoeren. Als \( n \) voldoende groot is, zal de lijst 10 keer langer maken dus neerkomen op ongeveer 100 keer zoveel werk, en zal selection sort dus 100 keer trager zijn.
In de rest van dit hoofdstuk over datastructuren gaan we verder voornamelijk werken met één specifieke basisoperatie, namelijk het aantal keer dat een element uit het geheugen (of uit een array) bezocht (uitgelezen) worden.
Grote O-notatie
We kunnen het aantal basisoperaties exact berekenen, zoals hierboven voor selection sort.
Dat is echter veel werk, en vaak hebben we dergelijke precisie niet nodig.
Voor tijdscomplexiteit wordt er daarom veelal gebruik gemaakt van grote O-notatie.
Dat is, informeel gezegd, de snelst stijgende term, zonder constanten.
In het voorbeeld van selection sort hierboven is de snelst stijgende term van \( T(n) \) de kwadratische term. We noteren dat als
\( T(n) \in \mathcal{O}(n^2) \)
of soms gewoon
\( T(n) = \mathcal{O}(n^2) \)
Formeel betekent \( T(n) \in \mathcal{O}(f(n)) \) dat \( \exists c, n_0.\ \forall n > n_0.\ T(n)/f(n) \leq c \). Met andere woorden, zodra \( n \) groot genoeg is (groter dan een bepaalde \(n_0\)), is de verhouding \(T(n)/f(n)\) begrensd door een constante, wat uitdrukt dat \(T(n)\) niet sneller stijgt dan \(f(n)\).
\( \mathcal{O}(n^2) \) is de complexiteitsklasse (de verzameling van alle functies die niet sneller dan kwadratisch stijgen), en we zeggen dat selection sort een kwadratische tijdscomplexiteit heeft.
Note
Er zijn nog andere notaties die vaak gebruikt worden in de context van tijdscomplexiteit, waaronder grote theta (\( \Theta \)), grote omega (\( \Omega \)), en tilde (~). Deze hebben allen een andere formele definitie.
In de dagelijkse (informele) praktijk wordt vaak grote O gebruikt, zelfs als eigenlijk een van deze andere bedoeld wordt.
Vaak voorkomende complexiteitsklassen
Hieronder vind je een tabel met vaak voorkomende complexiteitsklassen.
In de laatste kolom vind je de tijd die zo’n algoritme doet over een invoer van grootte \(n=1000\), in de veronderstelling dat het een probleem van grootte \(n=100\) kan oplossen in 1 milliseconde.
| Klasse | Naam | \( T(1000) \) (als \( T(100) = 1 \textrm{ms} \)) |
|---|
| \( \mathcal{O}(1) \) | Constant | \(1\ \textrm{ms} \) |
| \( \mathcal{O}(\log n) \) | Logaritmisch | \(1.5\ \textrm{ms} \) |
| \( \mathcal{O}(n) \) | Lineair | \(10\ \textrm{ms} \) |
| \( \mathcal{O}(n \log n) \) | Linearitmisch | \(15\ \textrm{ms} \) |
| \( \mathcal{O}(n^2) \) | Kwadratisch | \(100\ \textrm{ms} \) |
| \( \mathcal{O}(n^3) \) | Kubisch | \(1000\ \textrm{ms} \) |
| \( \mathcal{O}(2^n) \) | Exponentieel | \( 2^{900}\ \textrm{ms} \) = \( 2.7 \times 10^{260}\ \textrm{jaar}\) |
| \( \mathcal{O}(n!) \) | Factorieel | \( \frac{1000!}{100!}\ \textrm{ms} \) = \( 1.4 \times 10^{2399}\ \textrm{jaar}\) |
Je ziet dat de constante tot en met linearitmische complexiteitsklassen zeer gunstig zijn.
Kwadratisch en kubisch zijn te vermijden, omdat de tijd veel sneller toeneemt dan de grootte van de invoer.
Exponentiële en factoriële algoritmes tenslotte zijn dramatisch en schalen bijzonder slecht naar grotere problemen.
Backtracking-algoritmes (zie later) vallen vaak in deze laatste klassen, en kunnen dus zeer inefficiënt zijn voor grotere problemen.
We zullen deze tijdscomplexiteitsklassen gebruiken om (operaties op) datastructuren te vergelijken.
Onthoud
Tijdscomplexiteit met grote O geeft bij benadering aan hoe het aantal operaties dat een algoritme moet uitvoeren stijgt wanneer de grootte van de invoer stijgt.
7.3.2 Java Collections API
We kunnen nu de Java Collections-API verkennen.
Deze API bestaat uit
- interfaces (bv.
Iterable, Collection, List, Set, SortedSet, Queue, Deque, Map, SortedMap, en NavigableMap) - implementaties van die interface (bv.
ArrayList, LinkedList, Vector, Stack, ArrayDeque, PriorityQueue, HashSet, LinkedHashSet, TreeSet, en TreeMap) - algoritmes voor veel voorkomende operaties (bv.
shuffle, sort, swap, reverse, …)
Je vindt een overzicht van de hele API op deze pagina.
We beginnen bij de basisinterface: Iterable.
Iterable en Iterator
Iterable maakt eigenlijk geen deel uit van de Java Collections API, maar is er wel sterk aan verwant.
Een Iterable is namelijk een object dat meerdere objecten van hetzelfde type één voor één kan teruggeven.
Er moet slechts 1 methode geïmplementeerd worden, namelijk iterator(), die een Iterator-object teruggeeft.
Een Iterator is een object met twee methodes:
hasNext(), wat aangeeft of er nog objecten zijn om terug te geven, ennext(), wat (als er nog objecten zijn) het volgende object teruggeeft.
Elke keer je next() oproept krijg je dus een ander object, tot hasNext() false teruggeeft. Vanaf dan krijg je een exception (NoSuchElementException).
Een Iterator moet dus een toestand bijhouden, om te bepalen welke objecten al teruggegeven zijn en welke nog niet.
Eens alle elementen teruggegeven zijn, en hasNext dus false teruggeeft, is de iterator ‘opgebruikt’.
Als je daarna nog eens over de elementen wil itereren, moet je een nieuwe iterator aanmaken.
Elke klasse die Iterable implementeert, kan gebruikt worden in een ’enhanced for-statement’:
Iterable<E> iterable = ...
for (var element : iterable) {
... // code die element gebruikt
}
Achter de schermen wordt hierbij de iterator gebruikt. Het enhanced for-statement van hierboven is equivalent aan:
Iterable<E> iterable = ...
Iterator<E> iterator = iterable.iterator();
while (iterator.hasNext()) {
E element = iterator.next();
... // code die element gebruikt
}
Alle collectie-types die een verzameling elementen voorstellen (dus alles behalve Map), implementeren deze interface.
Dat betekent dus dat je elk van die collecties in een enhanced for-lus kan gebruiken.
Je kan daarenboven ook zelf een nieuwe klasse maken die deze interface implementeert, en die vervolgens gebruikt kan worden in een enhanced for-loop.
Dat doen we in deze oefening.
Collection
classDiagram
Iterable <|-- Collection
class Iterable["Iterable#lt;E>"] {
<<interface>>
iterator()
}
class Collection["Collection#lt;E>"] {
<<interface>>
size()
isEmpty()
contains()
containsAll()
add()
addAll()
remove()
removeAll()
clear()
toArray()
}
style Collection fill:#cdf,stroke:#99fZoals je hierboven zag, kan een Iterable dus enkel elementen opsommen.
De basisinterface Collection erft hiervan over maar is uitgebreider: het stelt een groep objecten voor.
Er zit nog steeds bitter weinig structuur in een Collection:
- de volgorde van de elementen in een Collection ligt niet vast
- er kunnen wel of geen dubbels in een Collection zitten
De belangrijkste operaties die je op een Collection-object kan uitvoeren zijn
iterator(), geërfd van Iterablesize(): de grootte opvragenisEmpty(): nagaan of de collectie leeg iscontains en containsAll: nakijken of een of meerdere elementen in de collectie zittenadd en addAll: een of meerdere elementen toevoegenremove en removeAll: een of meerdere elementen verwijderenclear: de collectie volledig leegmakentoArray: alle elementen uit de collectie in een array plaatsen
Alle operaties die een collectie aanpassen (bv. add, addAll, remove, clear, …) zijn optioneel.
Dat betekent dat sommige implementaties een UnsupportedOperationException kunnen gooien als je die methode oproept.
Niet elke collectie hoeft dus alle operaties te ondersteunen.
7.3.3 Lijsten
classDiagram
Iterable <|-- Collection
Collection <|-- List
class Iterable["Iterable#lt;E>"] { <<interface>> }
class Collection["Collection#lt;E>"] { <<interface>> }
class List["List#lt;E>"] {
<<interface>>
get(int index)
add(int index, E element)
set(int index, E element)
remove(int index)
indexOf(E element)
lastIndexOf(E element)
reversed()
subList(int from, int to)
}
style List fill:#cdf,stroke:#99fList
Een lijst is een collectie waar alle elementen een vaste plaats hebben.
De elementen in een lijst zijn dus geordend (maar niet noodzakelijk gesorteerd).
Een lijst wordt voorgesteld door de List interface, die Collection uitbreidt met operaties die kunnen werken met de plaats (index) van een object.
Bijvoorbeeld:
get(int index): het element op een specifieke plaats opvragenadd(int index, E element): een element invoegen op een specifieke plaats (en de latere elementen opschuiven)set(int index, E element): het element op een specifieke plaats wijzigenremove(int index): het element op de gegeven index verwijderen (en de latere elementen opschuiven)indexOf(E element) en lastIndexOf(E): de eerste en laatste index zoeken waarop het gegeven element voorkomtreversed(): geeft een lijst terug in de omgekeerde volgordesubList(int from, int to): geeft een lijst terug die een deel (slice) van de oorspronkelijke lijst voorstelt
Merk op dat de laatste twee methodes (reversed en subList) een zogenaamde view teruggeven op de oorspronkelijke lijst.
Het is dus geen nieuwe lijst, maar gewoon een andere manier om naar de oorspronkelijke lijst te kijken.
Bijvoorbeeld, in onderstaande code:
List<String> alphabet = new ArrayList<>(List.of("A", "B", "C", "D", "E", "F"));
// alphabet = [A, B, C, D, E, F]
List<String> rev = alphabet.reversed(); // rev = [F, E, D, C, B, A]
alphabet.set(5, "X"); // alphabet = [A, B, C, D, E, X]
System.out.println(rev); // rev = [X, E, D, C, B, A]
List<String> cde = alphabet.subList(2, 5); // cde = [C, D, E]
cde.clear(); // cde = [ ]
System.out.println(alphabet); // alphabet = [A, B, X]
System.out.println(rev); // rev = [X, B, A]
zie je dat
- de lijst
rev de aanpassing (het laatste element veranderen in X) in de oorspronkelijke lijst weerspiegelt - de sublist
cde leegmaken deze elementen verwijdert uit de oorspronkelijke lijst, en ook uit de omgekeerde view op de lijst (rev)
De reden is dat zowel rev als cde enkel verwijzen naar de onderliggende lijst alphabet, en zelf geen elementen bevatten:
block-beta
block:brev
space:1
rev
end
space
block:alphabet
columns 6
A B C D E F
end
space
block:bcde
cde
space:1
end
rev --> alphabet
cde --> alphabet
classDef node fill:#faa,stroke:#f00
classDef ptr fill:#ddd,stroke:black
classDef empty fill:none,stroke:none
classDef val fill:#ffc,stroke:#f90
class brev,bcde empty
class alphabet node
class rev,cde ptr
class A,B,C,D,E,F valIndien je wat Python kent: subList is dus een manier om functionaliteit gelijkaardig aan slices te verkrijgen in Java. Maar, in tegenstelling tot slices in Python, maakt subList geen kopie!
ArrayList
ArrayList is de eerste concrete implementatie van de List-interface die we bekijken.
In een ArrayList wordt een array gebruikt om de elementen bij te houden.
Aangezien arrays in Java een vaste grootte hebben, kan je niet zomaar elementen toevoegen als de lijst vol is.
Daarom wordt er een onderscheid gemaakt tussen de de grootte van de lijst (het aantal elementen dat er effectief inzit), en de capaciteit van de lijst (de lengte van de onderliggende array).
Zolang de grootte kleiner is dan de capaciteit, gebeurt er niets speciaals. Op het moment dat de volledige capaciteit benut is, en er nog een element toegevoegd wordt, wordt een nieuwe (grotere) array gemaakt en worden alle huidige elementen daarin gekopieerd.
Het kopiëren van een lijst is een \( \mathcal{O}(n) \) operatie, met \( n\) het huidige aantal elementen in de lijst.
Stel dat we kiezen om, elke keer wanneer we een element toevoegen, de array één extra plaats te geven.
We moeten dan telkens alle vorige elementen kopiëren, en dat wordt al snel erg inefficiënt.
Bijvoorbeeld, stel dat we met een lege array beginnen:
- om het eerste element toe te voegen, moeten we niets kopiëren
- om het tweede element toe te voegen, moeten we één element kopiëren (het eerste element uit de vorige array van lengte 1)
- om het derde element toe te voegen, moeten we twee elementen kopieëren (het eerste en tweede element uit de vorige array van lengte 2)
- om het vierde element toe te voegen 3 kopieën, enzovoort.
Eén voor één \(n\) elementen toevoegen aan een initieel lege lijst zou dus neerkomen op \(0+1+…+(n-1) = n(n-1)/2 = \mathcal{O}(n^2)\) kopieën (operaties).
Dat is erg veel werk als \(n\) groot wordt.
Om die reden wordt de lengte van de array niet telkens met 1 verhoogd, maar meteen vermenigvuldigd met een constante (meestal 2, zodat de lengte van de array verdubbelt).
Bijvoorbeeld, voor een lijst met capaciteit 3 en twee elementen:
block-beta
columns 1
block:before
columns 12
e0["A"] e1["B"] e2[" "] space:9
end
space
block:after1
columns 12
ee0["A"] ee1["B"] ee2["C"] space:9
end
space
block:after2
columns 12
eee0["A"] eee1["B"] eee2["C"] eee3["D"] eee4[" "] eee5[" "] space:6
end
space
block:after3
columns 12
eeee0["A"] eeee1["B"] eeee2["C"] eeee3["D"] eeee4["E"] eeee5["F"] eeee6["G"] eeee7[" "] eeee8[" "] eeee9[" "] eeee10[" "] eeee11[" "]
end
before --"C toevoegen (behoud capaciteit)"--> after1
after1 --"D toevoegen (verdubbel capaciteit)"--> after2
after2 --"E, F, G toevoegen (verdubbel capaciteit)"--> after3
classDef ok fill:#6c6,stroke:#393,color:#fff
class e0,e1 ok
class ee0,ee1,ee2 ok
class eee0,eee1,eee2,eee3 ok
class eeee0,eeee1,eeee2,eeee3,eeee4,eeee5,eeee6 okDe meeste toevoegingen gebeuren dus in \(\mathcal{O}(1)\), maar af en toe kost een toevoeging \(\mathcal{O}(n)\) omdat alle elementen gekopieerd moeten worden naar de grotere array.
Als de lijst op een gegeven moment \(n\) elementen bevat, en de capaciteit telkens verdubbeld werd wanneer de vorige capaciteit bereikt werd, zijn er dus in totaal \(n/2 + n/4 + … \leq n = \mathcal{O}(n)\) elementen gekopieerd. Gemiddeld werd elk van de \(n\) elementen dus met tijdscomplexiteit \(\mathcal{O}(n)/n = \mathcal{O}(1)\) toegevoegd.
| Operatie | Complexiteit (best case) | Complexiteit (worst case) |
|---|
| Opvragen | \(\mathcal{O}(1)\) | \(\mathcal{O}(1)\) |
| Invoegen | \(\mathcal{O}(1)\) (einde van lijst), of \(\mathcal{O}(n)\) bij uitbreiden capaciteit | \(\mathcal{O}(n)\) (begin van lijst) |
| Verwijderen | \(\mathcal{O}(1)\) (laatste element) | \(\mathcal{O}(n)\) (eerste element) |
| Zoeken | \(\mathcal{O}(1)\) (gezochte element is eerste element) | \(\mathcal{O}(n)\) (gezochte element is laatste) |
LinkedList
Een gelinkte lijst (LinkedList) is een andere implementatie van de List interface.
Hier wordt geen array gebruikt, maar wordt de lijst opgebouwd uit knopen (nodes).
Elke knoop bevat
- een waarde (
value) - een verwijzing (
next) naar de volgende knoop - (in een dubbel gelinkte lijst) een verwijzing (
prev) naar de vorige knoop.
De LinkedList zelf bevat enkel een verwijzing naar de eerste knoop (first), en voor een dubbel gelinkte lijst ook nog een verwijzing naar de laatste knoop van de lijst (last).
Vaak wordt ook het aantal elementen (size) bijgehouden.
Hieronder zie je een grafische voorstelling van een dubbel gelinkte lijst met 3 knopen:
block-beta
block:bf
columns 1
space
first
space
end
space
block:n0
columns 1
e0["A"]
p0["next"]
pp0["prev"]
end
space
block:n1
columns 1
e1["B"]
p1["next"]
pp1["prev"]
end
space
block:n2
columns 1
e2["C"]
p2["next"]
pp2["prev"]
end
space
block:bl
columns 1
space
last
space
end
first --> n0
last --> n2
p0 --> n1
p1 --> n2
pp1 --> n0
pp2 --> n1
classDef node fill:#faa,stroke:#f00
classDef ptr fill:#ddd,stroke:black
classDef empty fill:none,stroke:none
classDef val fill:#ffc,stroke:#f90
class bf,bl empty
class n0,n1,n2 node
class pp0,p0,pp1,p1,pp2,p2,first,last ptr
class e0,e1,e2 valDe tijdscomplexiteit van een (dubbel) gelinkte lijst is anders dan die van een ArrayList:
| Operatie | Complexiteit (best case) | Complexiteit (worst case) |
|---|
| Opvragen | \(\mathcal{O}(1)\) (begin of einde van de lijst) | \(\mathcal{O}(n)\) (midden van de lijst) |
| Invoegen | \(\mathcal{O}(1)\) (begin of einde van de lijst) | \(\mathcal{O}(n)\) (midden van de lijst) |
| Verwijderen | \(\mathcal{O}(1)\) (begin of einde van de lijst) | \(\mathcal{O}(n)\) (midden van de lijst) |
| Zoeken | \(\mathcal{O}(1)\) (begin of einde van de lijst) | \(\mathcal{O}(n)\) (midden van de lijst) |
Merk op dat we nooit elementen moeten kopiëren of verplaatsen in een gelinkte lijst, enkel referenties aanpassen.
Het aanpassen van een referentie is steeds \(\mathcal{O}(1)\).
Maar: we moeten eerst op de juiste plaats (knoop) geraken in de lijst, en dat kost mogelijk \(\mathcal{O}(n)\) werk: in een dubbel gelinkte lijst moeten we tot \(n/2\) referenties volgen (beginnend bij first of last).
Vandaar de \(\mathcal{O}(n)\) in de laatste kolom in de tabel hierboven.
Een gelinkte lijst is dus de juiste keuze wanneer je verwacht dat je veel aanpassingen aan je lijst zal doen, en die aanpassingen vooral voor- of achteraan zullen plaatsvinden.
Lijsten aanmaken
Je kan natuurlijk steeds een lijst aanmaken door een nieuwe, lege lijst te maken en daaraan je elementen toe te voegen:
List<String> anArrayList = new ArrayList<>();
anArrayList.add("first");
anArrayList.add("second");
...
List<String> aLinkedList = new LinkedList<>();
aLinkedList.add("first");
...
Als je een lijst wil maken met gekende elementen (constanten), dan kan je ook de List.of()-methode gebruiken:
List<String> lst = List.of("first", "second", "third");
Hierbij moet je wel opletten dat de lijst die je zo maakt immutable is. Je kan aan de lijst die je zo gemaakt hebt dus later geen wijzigingen meer aanbrengen via add, remove, etc.:
List<String> lst = List.of("first", "second", "third");
lst.add("fourth"); // gooit UnsupportedOperationException
Als je toch een wijzigbare lijst wil maken, kan je een constructor gebruiken die de meegegeven lijst kopieert:
List<String> mutable = new ArrayList<>(List.of("first", "second", "third"));
mutable.add("fourth"); // OK
Meer operaties op lijsten
De List-interface zelf bevat al enkele nuttige operaties op lijsten.
In de Collections-klasse (niet hetzelfde als de Collection-interface!) vind je nog een heleboel extra operaties die je kan uitvoeren op lijsten (of soms op collecties), bijvoorbeeld:
disjoint om na te gaan of twee collecties geen overlappende elementen hebbensort om een lijst te sorterenshuffle om een lijst willekeurig te permuterenswap om twee elementen van plaats te verwisselenfrequency om te tellen hoe vaak een element voorkomt in een lijstmin en max om het grootste element in een collectie te zoekenindexOfSubList om te zoeken of en waar een lijst voorkomt in een langere lijstnCopies om een lijst te maken die bestaat uit een aantal keer hetzelfde elementfill om alle elementen in een lijst te vervangen door eenzelfde elementrotate om de elementen in een lijst cyclisch te roteren
Unmodifiable list
Soms wil je een gewone (wijzigbare) lijst teruggeven maar er zeker van zijn dat de lijst niet aangepast kan worden.
Bijvoorbeeld, als je een lijst teruggeeft als resultaat van een methode:
class Library {
private List<Book> borrowedBooks;
public void borrow(Book book) { ... }
public List<Book> getBorrowedBooks() {
return this.borrowedBooks;
}
}
We willen niet dat een gebruiker van de klasse die lijst zomaar kan aanpassen — dat moet via de borrow-methode gaan.
We kunnen natuurlijk een nieuwe lijst teruggeven met een kopie van de elementen:
public List<Book> getBorrowedBooks() {
return new ArrayList<>(this.borrowedBooks);
}
Maar dat kost \(\mathcal{O}(n)\) werk om die elementen te kopiëren.
Een alternatief is gebruik maken van Collections.unmodifiableList:
public List<Book> getBorrowedBooks() {
return Collections.unmodifiableList(this.borrowedBooks);
}
Er wordt dan geen nieuwe lijst gemaakt, maar wel een ‘view’ op de originele lijst (net zoals we eerder gezien hebben bij reversed en subList).
Het verschil is dat deze view nu geen wijzigingen toelaat; alle operaties die de lijst wijzigen, gooien een UnsupportedOperationException.
7.3.4 Wachtrijen
classDiagram
Iterable <|-- Collection
Collection <|-- Queue
Queue <|-- Deque
Deque <|-- LinkedList
Queue <|-- PriorityQueue
class Iterable["Iterable#lt;E>"] { <<interface>> }
class Collection["Collection#lt;E>"] { <<interface>> }
class Queue["Queue#lt;E>"] {
<<interface>>
add(E e)
E element()
offer(E e)
E peek()
E poll()
E remove()
}
class Deque["Deque#lt;E>"] {
<<interface>>
addFirst(E e)
addLast(E e)
offerFirst(E e)
offerLast(E e)
E removeFirst()
E removeLast()
E pollFirst()
E pollLast()
E getFirst()
E getLast()
E peekFirst()
E peekLast()
}
style Queue fill:#cdf,stroke:#99f
style Deque fill:#cdf,stroke:#99fQueue, Deque
Een Queue is een collectie die lijkt op een lijst.
Het voornaamste verschil met een lijst is dat een queue specifiek dient om elk toegevoegd elementen er later terug uit te halen, en dat een queue niet toelaat om te werken met de positie (index) van een element.
Het volgende element dat teruggegeven wordt uit de queue wordt het hoofd (head) van de queue genoemd, de andere elementen de staart (tail).
Er bestaan operaties om het element aan het hoofd van de queue terug te geven en meteen te verwijderen (poll), alsook een andere operatie om het hoofd op te vragen zonder het meteen te verwijderen (peek). Als er geen elementen in de queue zitten, geven beiden null terug.
Sommige subtypes van Queue kunnen begrensd zijn qua capaciteit. Je kan dan geen elementen toevoegen als de queue vol is.
Elementen toevoegen aan een queue kan met add of offer. De add-methode gooit een exception als de queue vol is; offer geeft gewoon false terug.
Ook voor poll en peek bestaan varianten (namelijk remove en element) die een exception gooien in plaats van null terug te geven als de queue leeg is.
De volgorde waarin elementen teruggegeven worden uit de queue bepaalt het soort queue:
- een FIFO (first-in-first-out) queue geeft de elementen terug in de volgorde dat ze toegevoegd zijn: het eerst toegevoegde element wordt eerst teruggegeven
- een LIFO (last-in-first-out) queue geeft steeds het laatst toegevoegde element als eerste terug. Dit wordt ook een stack genoemd.
- een priority queue laat toe om aan elk toegevoegd element een prioriteit toe te kennen, en geeft de elementen terug volgens die prioriteit
Java voorziet ook een Deque interface.
Dit staat voor double-ended queue en laat toe om elementen vooraan en achteraan toe te voegen aan en te verwijderen uit de deque.
Deze interface erft over van Queue.
Bovenop de methodes uit Queue worden methodes toegevoegd met suffix -First en -Last, bijvoorbeeld pollFirst() en offerLast().
De methodes uit Queue om elementen toe te voegen (offer(), add()) komen overeen met offerLast() en addLast().
De methodes uit Queue om elementen op te vragen (peek(), poll(), etc.) komen overeen met peekFirst(), pollFirst(), etc.
De basisimplementatie in Java, zowel voor de Queue als Deque interface, is de klasse LinkedList (een dubbel gelinkte lijst).
In een (dubbel) gelinkte lijst is het immers heel eenvoudig en efficiënt (\(\mathcal{O}(1)\)) om een element vooraan of achteraan toe te voegen en te verwijderen.
Afhankelijk van welke methodes je gebruikt, gebruik je een LinkedList dus als FIFO of LIFO queue.
FIFO queue
In een FIFO queue worden de elementen teruggegeven in de volgorde dat ze toegevoegd zijn:
block-beta
columns 1
block:before0
AA["A"] BB["B"] space:1
end
space
block:before
A B C
end
space
block:after
BBB["B"] CCC["C"] space:1
end
before0 --> before
before --> after
Note
Welke operaties gebruik je om een Deque (of LinkedList) als FIFO queue te gebruiken?
LIFO queue (stack)
In een LIFO queue, vaak ook stack genoemd, worden het laatst toegevoegde element eerst teruggegeven:
block-beta
columns 1
block:before0
AA["A"] BB["B"] space:1
end
space
block:before
A B C
end
space
block:after
AAA["A"] BBB["B"] space:1
end
before0 --> before
before --> after
Note
Welke operaties gebruik je om een Deque (of LinkedList) als LIFO/stack te gebruiken?
PriorityQueue
De PriorityQueue klasse implementeert een priority queue.
De prioriteit van elementen wordt bepaald door:
- ofwel de natuurlijke ordening indien de elementen de
Comparable-interface implementeren; - ofwel door een
Comparator-object dat meegegeven wordt bij het aanmaken van de priority queue.
Deze implementatie is zeer efficiënt voor de vaak voorkomende operaties. De worst-case tijdscomplexiteit om
- het hoofd van de queue op te vragen is \(\mathcal{O}(1)\)
- het hoofd van de queue te verwijderen uit de queue is \(\mathcal{O}(\log n)\)
- een element aan de queue toe te voegen is \(\mathcal{O}(\log n)\)
Nagaan of de queue een element bevat, alsook een willekeurig element verwijderen, is \(\mathcal{O}(n)\) — maar beiden zijn geen typisch gebruik van een queue.
7.3.5 Verzamelingen
classDiagram
Iterable <|-- Collection
Collection <|-- List
Collection <|-- Queue
Collection <|-- Set
class Iterable["Iterable#lt;E>"] { <<interface>> }
class Collection["Collection#lt;E>"] { <<interface>> }
class List["List#lt;E>"] { <<interface>> }
class Queue["Queue#lt;E>"] { <<interface>> }
class Set["Set#lt;E>"] {
<<interface>>
}
style Set fill:#cdf,stroke:#99fSet
Alle collecties die we totnogtoe gezien hebben, kunnen dubbels bevatten.
Bij een Set is dat niet het geval. Het is een abstractie voor een wiskundige verzameling: elk element komt hoogstens één keer voor.
In een wiskundige verzameling is ook de volgorde van de elementen niet van belang.
De Set interface legt geen volgorde van elementen vast, maar er bestaan sub-interfaces van Set (bijvoorbeeld SequencedSet en SortedSet) die wél toelaten dat de elementen een bepaalde volgorde hebben.
De Set interface voegt in feite geen nieuwe operaties toe aan de Collection-interface. Je kan elementen toevoegen, verwijderen, en nagaan of een element in de verzameling zit.
Het is leerrijk om even stil te staan bij hoe een set efficiënt geïmplementeerd kan worden.
Immers, verzekeren dat er geen duplicaten inzitten vereist dat we gaan zoeken tussen de huidige elementen, en dat wordt al gauw een \(\mathcal{O}(n)\) operatie.
We bekijken twee implementaties van hoe dat efficiënter kan: HashSet en TreeSet.
HashSet
Een HashSet kan gebruikt worden om willekeurige objecten in een set bij te houden.
De objecten worden bijgehouden in een hashtable (in essentie een gewone array).
Om te voorkomen dat we een reeds bestaand element een tweede keer toevoegen, moeten we echter snel kunnen nagaan of het toe te voegen element al in de set voorkomt.
De hele hashtable overlopen kost teveel tijd (\(\mathcal{O}(n)\) met \(n\) het aantal objecten in de set), dus dat moeten we verbeteren.
Een HashSet kan nagaan of een element bestaat, alsook een element toevoegen en verwijderen, in \(\mathcal{O}(1)\).
De sleutel om dat te doen is de hashCode() methode die ieder object in Java heeft.
Die methode moet, voor elk object, een hashCode (een int) teruggeven, zodanig dat als twee objecten gelijk zijn volgens hun equals-methode, ook hun hashcodes gelijk zijn.
Gewoonlijk zal je, als je equals zelf implementeert, ook hashCode moeten implementeren en omgekeerd.
De hashCode moet niet uniek zijn: meerdere objecten mogen dezelfde hashCode hebben, ook al zijn ze niet gelijk (al kan dat tot een tragere werking van een HashSet leiden; zie verder). Hoe uniformer de hashCode verdeeld is over alle objecten, hoe beter.
Note
Java records voorzien standaard een zinvolle equals- en hashCode-methode die afhangt van de attributen van het record.
Deze hoef je dus normaliter niet zelf te voorzien.
De hashCode wordt gebruikt om een index te bepalen in de onderliggende hashtable (array).
De plaats in die hashtable is een bucket.
Het element wordt opgeslagen in de bucket op die index.
Als we later willen nagaan of een element al voorkomt in de hashtable, berekenen we opnieuw de index aan de hand van de hashCode en kijken we of het element zich effectief in de overeenkomstige bucket bevindt.
Idealiter geeft elk object dus een unieke hashCode, en zorgen die voor perfecte spreiding van alle objecten in de hashtable.
Er zijn echter twee problemen in de praktijk:
- twee verschillende objecten kunnen dezelfde hashCode hebben. Dat is een collision. Hiermee moeten we kunnen omgaan.
- als er teveel elementen toegevoegd worden, moet de onderliggende hashtable dynamisch kunnen uitbreiden. Dat maakt dat elementen plots op een andere plaats (index) terecht kunnen komen als voorheen. Uitbreiden vraagt vaak rehashing, oftwel het opnieuw berekenen van de index (nu in een grotere hashtable) aan de hand van de hashcodes. De load factor van de hash table geeft aan hoe vol de hashtable mag zijn voor ze uitgebreid wordt. Bijvoorbeeld, een load factor van 0.75 betekent dat het aantal elementen in de hashtable tot 75% van het aantal buckets mag gaan.
Beide problemen zijn al goed onderzocht in de computerwetenschappen.
We overlopen twee technieken voor het eerste probleem (collisions): chaining en probing.
Chaining
Bij chaining houden we in de hashtable niet rechtstreeks de elementen bij, maar wijzen we in elke bucket naar een afzonderlijke gelinkte lijst.
Elke keer wanneer we een element toevoegen, voegen we een knoop toe aan de gelinkte lijst in de bucket.
Wanneer we een element opvragen, doorlopen we de gelinkte lijst om na te gaan of het element daarin voorkomt.
Als er veel collisions zijn, verliezen we zo natuurlijk het performantie-voordeel van de hashtable.
Inderdaad, in extremis hebben alle objecten dezelfde hashcode, en bevat de hashtable slechts één gelinkte lijst met daarin alle elementen.
Een goede hashfunctie, die elementen goed verspreidt over de verschillende buckets, is dus essentieel voor de performantie.
block-beta
columns 5
block:tab
columns 1
i0["0"]
i1["1"]
i2["2"]
end
space
block:lls:3
columns 1
block:ll0
columns 3
block:ll00
columns 2
ll00v["obj1"]
ll00p[" "]
end
space
block:ll01
columns 2
ll01v["obj2"]
ll01p[" "]
end
end
space
block:ll2
columns 3
block:ll20
columns 2
ll20v["obj3"]
ll20p[" "]
end
space:2
end
end
i0 --> ll00
ll00p --> ll01
i2 --> ll20
classDef none fill:none,stroke:none
class lls noneProbing (open addressing)
Een andere techniek om om te gaan met collisions is probing.
Als we een element willen toevoegen op een index, en er al een (ander) element op die index staat, berekenen we (volgens een deterministische formule) een volgende index, en proberen we daar opnieuw.
Dat doen we tot we een lege plaats tegenkomen, waar we het element kunnen bijhouden.
Die volgende index kan bijvoorbeeld (heel eenvoudig) index+1 zijn, maar we kunnen ook complexere formules bedenken waarmee we naar een heel andere plaats in de lijst springen.
Bij het opzoeken volgen we hetzelfde stramien: blijven zoeken tot we het element terugvinden, of een lege plaats tegenkomen.
Een element verwijderen wordt nu wel wat complexer: we moeten ervoor zorgen dat we geen lege plaats veroorzaken in de sequentie van indices.
SortedSet en TreeSet
Naast Set bestaat ook de interface SortedSet.
In tegenstelling tot een Set, kan een SortedSet geen willekeurige objecten bevatten.
De objecten moeten een volgorde hebben (hetzij door Comparable te implementeren, hetzij door een Comparator-object mee te geven).
De elementen worden steeds in gesorteerde volgorde opgeslagen en teruggegeven.
De TreeSet klasse is een implementatie van SortedSet die gebruik maakt van een gebalanceerde boomstructuur (een red-black tree — de werking daarvan is hier niet van belang).
Alle basisoperaties (add, remove, contains) hebben worst-case tijdscomplexiteit \(\mathcal{O}(\log n)\); invoegen en verwijderen zijn best-case \(\mathcal{O}(1)\).
De oorsprong van het logaritme wordt duidelijk aan de hand van deze oefening.
7.3.6 Maps
Map (Dictionary)
De collecties hierboven stellen allemaal een groep elementen voor, en erven over van de Collection-interface.
Een Map is iets anders.
Hier worden sleutels bijgehouden, en bij elke sleutel hoort een waarde (een object).
Denk aan een telefoonboek, waar bij elke naam (de sleutel) een telefoonnummer (de waarde) hoort, of een woordenboek waar bij elk woord (de sleutel) een definitie hoort (de waarde).
Een andere naam voor een map is dan ook een dictionary.
Sleutels mogen slechts één keer voorkomen; eenzelfde waarde mag wel onder meerdere sleutels opgeslagen worden.
De interface Map<K, V> heeft twee generische parameters: een (K) voor het type van de sleutels, een een (V) voor het type van de waarden.
Elementen toevoegen aan een Map<K, V> gaat via de put(K key, V value)-methode.
De waarde opvragen kan via de methode V get(K key).
Verder zijn er methodes om na te gaan of een map een bepaalde sleutel of waarde bevat.
Een Map is vaak geoptimaliseerd voor deze operaties; deze hebben vaak tijdscomplexiteit \(\mathcal{O}(1)\) (hashtable-gebaseerde implementaties) of \(\mathcal{O}(\log n)\) (boom-gebaseerde implementaties).
Er zijn verder ook drie manieren om een Map<K, V> als Collection te beschouwen:
- de
keySet: de verzameling sleutels (een Set<K>) - de
values: de collectie waarden (een Collection<V>, want dubbels zijn mogelijk) - de
entrySet: een verzameling (Set<Entry<K, V>>) van sleutel-waarde paren (de entries).
Belangrijk om te onthouden is dat een Map geoptimaliseerd is om waardes op te vragen aan de hand van hun sleutels.
HashMap
Net zoals bij Set kunnen we de Map-interface implementeren met een hashtable.
Dat gebeurt in de HashMap klasse.
Entries in een hashmap worden in een niet-gespecifieerde volgorde bijgehouden.
De werking van een hashmap is zeer gelijkaardig aan wat we besproken hebben bij HashSet hierboven.
Meer zelfs, de implementatie van HashSet in Java maakt gebruik van een HashMap.
Het belangrijkste verschil met de HashSet is dat we in een HashMap, naast de waarde, ook de sleutel moeten bewaren.
SortedMap en TreeMap
Een SortedMap is een map waarbij de sleutels (dus niet de waarden) gesorteerd worden bijgehouden (zoals bij een SortedSet).
De TreeMap klasse implementeert een SortedMap aan de hand van een boomstructuur.
Oefeningen
De Collections API
IntRange
- Schrijf eerst een klasse
IntRangeIterator die Iterator<Integer> implementeert, en alle getallen teruggeeft tussen twee grensgetallen lowest en highest (beiden inclusief) die je meegeeft aan de constructor. Je houdt hiervoor enkel de onder- en bovengrens bij, alsook het volgende terug te geven getal. - Schrijf nu ook een record
IntRange die Iterable<Integer> implementeert, en die een IntRangeIterator-object aanmaakt en teruggeeft.
Je moet deze klasse nu als volgt kunnen gebruiken:
IntRange range = new IntRange(3, 6);
for (int x : range) {
System.out.println(x);
}
// Uitvoer:
// 3
// 4
// 5
// 6
Note
Java laat niet toe om primitieve types als generische parameters te gebruiken.
Voor elk primitief type bestaat er een wrapper-klasse, bijvoorbeeld Integer voor int.
Daarom gebruiken we hierboven bijvoorbeeld Iterator<Integer> in plaats van Iterator<int>.
Achter de schermen worden int-waarden automatisch omgezet in Integer-objecten en omgekeerd.
Dat heet auto-boxing en -unboxing.
Je kan beide types in je code grotendeels door elkaar gebruiken zonder problemen.
Lijsten
MyArrayList
Schrijf zelf een simpele klasse MyArrayList<E> die werkt zoals de ArrayList uit Java.
Voorzie in je lijst een initiële capaciteit van 4, maar zonder elementen.
Implementeer volgende operaties:
int size() die de grootte (het huidig aantal elementen in de lijst) teruggeeftint capacity() die de huidige capaciteit (het aantal plaatsen in de array) van de lijst teruggeeftE get(int index) om het element op positie index op te vragen (of een IndexOutOfBoundsException indien de index ongeldig is)void add(E element) om een element achteraan toe te voegen (en de onderliggende array dubbel zo groot te maken indien nodig)void remove(int index) om het element op plaats index te verwijderen (of een IndexOutOfBoundsException indien de index ongeldig is). De capaciteit moet niet terug dalen als er veel elementen verwijderd werden (dat gebeurt in Java ook niet).E last() om het laatste element terug te krijgen (of een NoSuchElementException indien de lijst leeg is)
Hier vind je een test die een deel van dit gedrag controleert:
Testcode
@Test
public void test_my_arraylist() {
MyArrayList<String> lst = new MyArrayList<>();
// initial capacity and size
assertThat(lst.capacity()).isEqualTo(4);
assertThat(lst.size()).isEqualTo(0);
// adding elements
for (int i = 0; i < 4; i++) {
lst.add("item" + i);
}
assertThat(lst.size()).isEqualTo(4);
assertThat(lst.capacity()).isEqualTo(4);
assertThat(lst.last()).isEqualTo("item3");
// adding more elements
for (int i = 4; i < 10; i++) {
lst.add("item" + i);
}
assertThat(lst.size()).isEqualTo(10);
assertThat(lst.capacity()).isEqualTo(16);
assertThat(lst.last()).isEqualTo("item9");
// remove an element
lst.remove(3);
assertThat(lst.size()).isEqualTo(9);
assertThat(lst.capacity()).isEqualTo(16);
assertThat(lst.get(3)).isEqualTo("item4");
assertThatThrownBy(() -> lst.get(10)).isInstanceOf(IndexOutOfBoundsException.class);
}
Linked list
Schrijf zelf een klasse MyLinkedList<E> om een dubbel gelinkte lijst voor te stellen. Voorzie volgende operaties:
int size() om het aantal elementen terug te gevenvoid add(E element) om het gegeven element achteraan toe te voegenE get(int index) om het element op positie index op te vragenvoid remove(int index) om het element op positie index te verwijderen
Hieronder vind je enkele tests voor je klasse. Je zal misschien merken dat je implementatie helemaal juist krijgen niet zo eenvoudig is als het op het eerste zicht lijkt, zeker bij de remove-methode.
Gebruik de visuele voorstelling van eerder, en ga na wat je moet doen om elk van de getekende knopen te verwijderen.
Testcode
@Test
public void add_first_element() {
MyLinkedList<String> lst = new MyLinkedList<>();
lst.add("element0");
assertThat(lst.size()).isEqualTo(1);
assertThat(lst.get(0)).isEqualTo("element0");
}
@Test
public void add_more_elements() {
MyLinkedList<String> lst = new MyLinkedList<>();
lst.add("element0");
lst.add("element1");
assertThat(lst.size()).isEqualTo(2);
assertThat(lst.get(0)).isEqualTo("element0");
assertThat(lst.get(1)).isEqualTo("element1");
lst.add("element2");
assertThat(lst.size()).isEqualTo(3);
assertThat(lst.get(0)).isEqualTo("element0");
assertThat(lst.get(1)).isEqualTo("element1");
assertThat(lst.get(2)).isEqualTo("element2");
}
@Test
public void remove_elements() {
MyLinkedList<String> lst = new MyLinkedList<>();
lst.add("element0");
lst.add("element1");
lst.add("element2");
lst.remove(1);
assertThat(lst.size()).isEqualTo(2);
assertThat(lst.get(0)).isEqualTo("element0");
assertThat(lst.get(1)).isEqualTo("element2");
lst.remove(1);
assertThat(lst.size()).isEqualTo(1);
assertThat(lst.get(0)).isEqualTo("element0");
}
@Test
public void get_from_empty() {
MyLinkedList<String> lst = new MyLinkedList<>();
assertThatIndexOutOfBoundsException().isThrownBy(() -> lst.get(0));
}
@Test
public void remove_from_empty() {
MyLinkedList<String> lst = new MyLinkedList<>();
assertThatIndexOutOfBoundsException().isThrownBy(() -> lst.remove(0));
}
@Test
public void get_from_single() {
MyLinkedList<String> lst = new MyLinkedList<>();
lst.add("element0");
assertThat(lst.get(0)).isEqualTo("element0");
}
@Test
public void remove_from_single() {
MyLinkedList<String> lst = new MyLinkedList<>();
lst.add("element0");
lst.remove(0);
assertThat(lst.size()).isEqualTo(0);
}
Wachtrijen
MyFIFO
Implementeer zelf een klasse MyFIFO<E> die een FIFO queue voorstelt met beperkte capaciteit, en die gebruik maakt van een array om de elementen te bewaren.
De capaciteit wordt opgegeven bij het aanmaken.
Invoegen en terug verwijderen van elementen moet zeer efficiënt zijn (\(\mathcal{O}(1)\)).
Implementeer volgende operaties:
size(): het aantal elementen in je queueE poll(): het hoofd van je FIFO queue opvragen en verwijderen; geeft null terug indien de queue leeg isboolean add(E): een element (niet-null) toevoegen aan je queue; geeft false terug indien er niet voldoende capaciteit is
Hieronder vind je enkele tests.
Testcode
@Test
public void empty_fifo_size_0() {
MyFIFO<String> fifo = new MyFIFO<>(5);
assertThat(fifo.size()).isEqualTo(0);
}
@Test
public void fifo_one_element() {
MyFIFO<String> fifo = new MyFIFO<>(5);
fifo.add("first");
assertThat(fifo.size()).isEqualTo(1);
assertThat(fifo.poll()).isEqualTo("first");
}
@Test
public void fifo_maximum_capacity() {
MyFIFO<String> fifo = new MyFIFO<>(5);
for (var e : List.of("first", "second", "third", "fourth", "fifth")) {
assertThat(fifo.add(e)).isTrue();
}
assertThat(fifo.size()).isEqualTo(5);
assertThat(fifo.add("sixth")).isFalse();
assertThat(fifo.size()).isEqualTo(5);
}
@Test
public void fifo_poll_correct_order() {
MyFIFO<String> fifo = new MyFIFO<>(5);
for (var e : List.of("first", "second", "third", "fourth", "fifth")) {
assertThat(fifo.add(e)).isTrue();
}
assertThat(fifo.poll()).isEqualTo("first");
assertThat(fifo.poll()).isEqualTo("second");
assertThat(fifo.poll()).isEqualTo("third");
assertThat(fifo.size()).isEqualTo(2);
assertThat(fifo.poll()).isEqualTo("fourth");
assertThat(fifo.poll()).isEqualTo("fifth");
assertThat(fifo.size()).isEqualTo(0);
}
Denkvraag
Wat zou je moeten doen om je MyFIFO-klasse dynamisch te laten groeien als er meer elementen aan toegevoegd worden?
Priority boarding
Hieronder is een record die een vliegtuigpassagier voorstelt.
record Passenger(String name, int priority) { }
Maak een klasse PriorityBoarding waar je een PriorityQueue gebruikt om passagiers te laten boarden.
Passagiers mogen het vliegtuig betreden volgens oplopende prioriteit (prioriteit 1 mag voor 2), en bij gelijke prioriteit, in alfabetische volgorde (A mag voor B).
Maak daarvoor twee operaties in je klasse:
checkin(Passenger p) om een passagier toe te voegen aan de lijst van passagiers die kunnen instappenPassenger nextPassenger() die de volgende passagier teruggeeft die mag instappen, of null indien er geen passagiers meer zijn.
Hieronder vind je een test.
Hint: schrijf een Comparator. Je kan daarbij gebruik maken van de statische methodes uit de Comparator-interface.
Testcode
@Test
public void priority_example() {
var p1 = new Passenger("Bob", 1);
var p2 = new Passenger("Alex", 2);
var p3 = new Passenger("Charlie", 3);
var p4 = new Passenger("Donald", 3);
var prio = new PriorityBoarding();
prio.checkin(p4);
prio.checkin(p1);
prio.checkin(p3);
prio.checkin(p2);
assertThat(prio.nextPassenger()).isEqualTo(p1);
assertThat(prio.nextPassenger()).isEqualTo(p2);
assertThat(prio.nextPassenger()).isEqualTo(p3);
assertThat(prio.nextPassenger()).isEqualTo(p4);
}
Sets
Unieke hashcode
Test uit hoe belangrijk het is dat de hashcodes van verschillende objecten in een HashSet goed verdeeld zijn aan de hand van de code hieronder.
Deze code meet hoelang het duurt om een HashSet te vullen met 50000 objecten; de eerste keer met goed verspreide hashcodes, en de tweede keer een keer met steeds dezelfde hashcode. Voer uit; merk je een verschil?
import java.util.HashSet;
import java.util.concurrent.TimeUnit;
import java.util.function.Function;
public class Timing {
record DefaultHashcode(int i) {}
record CustomHashcode(int i) {
@Override
public int hashCode() {
return 4;
}
}
public static void main(String[] args) {
System.out.print("With default hashcode: ");
test(DefaultHashcode::new);
System.gc();
System.out.print("With identical hashcode: ");
test(CustomHashcode::new);
}
private static <T> void test(Function<Integer, T> ctor) {
var set = new HashSet<T>();
var start = System.nanoTime();
for (int i = 0; i < 50_000; i++) {
set.add(ctor.apply(i));
}
var end = System.nanoTime();
System.out.println(set.size() + " elements added in " + TimeUnit.NANOSECONDS.toMillis(end - start) + "ms");
}
}
Veranderende hashcode
Is het nodig dat de hashCode van een object hetzelfde blijft doorheen de levensduur van het object, of mag deze veranderen?
Verklaar je antwoord.
Antwoord
Nee, deze mag niet veranderen. Mocht die wel veranderen, kan het zijn dat je een object niet meer terugvindt in een set, omdat er (door de veranderde hashcode) in een andere bucket gezocht wordt dan waar het object zich bevindt.
Voorbeeldcode
import java.util.HashSet;
import java.util.Set;
public class Demo {
static class MyObject {
public int hashCode = 1;
@Override
public int hashCode() {
return hashCode;
}
}
public static void main(String[] args) {
Set<MyObject> set = new HashSet<>();
MyObject obj = new MyObject();
set.add(obj);
System.out.println("Before changing hashcode");
System.out.println("Contains: " + set.contains(obj));
obj.hashCode++;
System.out.println("After changing hashcode");
System.out.println("Contains: " + set.contains(obj));
}
}
Boomstructuur
flowchart TB
subgraph s0 ["d=0"]
direction LR
R
end
subgraph s1 ["d=1"]
direction LR
A
X10[" "]
X11[" "]
B
end
subgraph s2 ["d=2"]
direction LR
C
D
X20[" "]
X21[" "]
X22[" "]
end
subgraph s3 ["d=3"]
direction LR
X30[" "]
X31[" "]
E
X32[" "]
X33[" "]
X34[" "]
end
R --> A
R --> B
A --> C
A --> D
D --> E
classDef empty fill:none,stroke:none
classDef depth stroke:none
class X10,X11,X20,X21,X22,X30,X31,X32,X33,X34 empty
class s0,s1,s2,s3 depth
Stel dat je een binaire boom hebt: een boomstructuur hebt waar elke knoop in de boom maximaal 2 kinderen heeft, zoals het voorbeeld hierboven.
- De diepte van een knoop is de afstand van die knoop tot de wortelknoop (bv. in de boom hierboven heeft knoop A diepte 1, knoop E diepte 3, en knoop R diepte 0).
- De hoogte van de boom is de maximale diepte van alle knopen in de boom (of dus: de diepte van de knoop die het verst van de wortel ligt). In het voorbeeld ligt knoop E het verst (met diepte 3), dus de hoogte van deze boom is 3.
- wat is de maximale hoogte van een binaire boom met \(n\) knopen?
- wat is het maximaal aantal elementen met diepte gelijk aan \(d\) in een binaire boom?
- wanneer heeft een binaire boom met \(n\) knopen een minimale hoogte? Wat is die hoogte?
Antwoord
- Om de maximale hoogte te bekomen, geven we elke knoop slechts 1 kind. We krijgen dan gewoon een lineaire ketting van \(n\) knopen, en de hoogte daarvan is \(n-1\).
- Op diepte \(d\) kunnen zich in totaal maximaal \(2^d\) knopen bevinden.
- De minimale hoogte bekomen we wanneer alle knopen precies 2 kinderen hebben (behalve de knopen op het diepste niveau).
Veronderstellen we dus dat de boom \(n\) elementen bevat en elke laag volledig opgevuld is, dan bevat die
$$n = 2^0 + 2^1 + ... + 2^h = 2^{h+1} - 1 $$ knopen, met \(h\) de hoogte van de boom.
Daaruit leiden we af dat \( h = \log_2(n+1) - 1 \in \mathcal{O}(\log_2 n) \).
Met andere woorden, de hoogte van de boom groeit logaritmisch in functie van het aantal elementen.
Scheduler
Maak een record Job met attributen time (je kan gewoon een double gebruiken) en een description (String).
Maak ook een klasse Scheduler die een TreeSet gebruikt om volgende methodes te implementeren:
schedule(Job job) om de gegeven job toe te voegen aan de schedulerList<Job> allJobs() om alle jobs (in volgorde van hun tijd) terug te krijgenJob nextJob(double after) om de eerstvolgende job op of na het gegeven tijdstip terug te vinden. (Hint: bekijk eerst of er bruikbare methodes zijn in de klasse TreeSet.)
Hieronder vind je een test die deze methodes gebruikt.
@Test
public void test_scheduler() {
var scheduler = new Scheduler();
var job1 = new Job(1, "First job");
var job2 = new Job(2, "Second job");
var job3 = new Job(3, "Third job");
scheduler.schedule(job3);
scheduler.schedule(job1);
scheduler.schedule(job2);
assertThat(scheduler.allJobs()).containsExactly(job1, job2, job3);
assertThat(scheduler.nextJob(2)).isEqualTo(job2);
assertThat(scheduler.nextJob(2.5)).isEqualTo(job3);
}
Maps
Set implementeren met Map
Leg uit hoe je een HashSet zou kunnen implementeren gebruik makend van een HashMap.
(Dit is ook wat Java (en Python) doen in de praktijk.)
Antwoord
Je gebruikt de elementen die je in de set wil opslaan als sleutel (key), en als waarde (value) neem je een willekeurig object.
Als het element in de HashMap een geassocieerde waarde heeft, zit het in de set; anders niet.
Parking
Maak een klasse Parking die gebruikt wordt voor betalend parkeren.
Kies een of meerdere datastructuren om volgende methodes te implementeren:
enterParking(String licensePlate): een auto rijdt de parking binnendouble amountToPay(String licensePlate): bereken het te betalen bedrag voor de gegeven auto (nummerplaat). De parking kost 2 euro per begonnen uur.pay(String licensePlate): markeer dat de auto met de gegeven nummerplaat betaald heeftboolean leaveParking(String licensePlate): geef terug of de gegeven auto de parking mag verlaten (betaald heeft), en verwijder de auto uit het systeem indien betaald werd.
Om te werken met huidige tijd en intervallen tussen twee tijdstippen, kan je gebruik maken van java.time.Instant.
@Test
public void test_parking() throws InterruptedException {
Parking parking = new Parking();
parking.enterParking("ABC123");
Thread.sleep(Duration.ofSeconds(1));
var amount = parking.amountToPay("ABC123");
assertThat(amount).isEqualTo(2.0);
assertThat(parking.leaveParking("ABC123")).isFalse();
parking.pay("ABC123");
assertThat(parking.leaveParking("ABC123")).isTrue();
}
MultiMap
Schrijf een klasse MultiMap die een map voorstelt, maar waar bij elke key een verzameling (Set) van waarden hoort in plaats van slechts één waarde.
Gebruik een Map in je implementatie.
Hieronder vind je enkele tests, die ook aangeven welke methodes je moet voorzien.
public class MultiMapTest {
@Test
public void empty_multimap() {
var mm = new MultiMap<Integer, String>();
assertThat(mm.size()).isEqualTo(0);
}
@Test
public void add_one_element() {
var mm = new MultiMap<Integer, String>();
mm.put(1, "first");
assertThat(mm.size()).isEqualTo(1);
assertThat(mm.get(1)).containsExactly("first");
}
@Test
public void add_multiple_with_same_key() {
var mm = new MultiMap<Integer, String>();
mm.put(1, "first");
mm.put(1, "second");
mm.put(1, "third");
mm.put(2, "fourth");
mm.put(2, "fifth");
assertThat(mm.size()).isEqualTo(2);
assertThat(mm.get(1)).containsExactlyInAnyOrder("first", "second", "third");
assertThat(mm.get(2)).containsExactlyInAnyOrder("fourth", "fifth");
}
@Test
public void remove_one_value() {
var mm = new MultiMap<Integer, String>();
mm.put(1, "first");
mm.put(1, "second");
mm.put(1, "third");
assertThat(mm.size()).isEqualTo(1);
mm.remove(1, "second");
assertThat(mm.size()).isEqualTo(1);
assertThat(mm.get(1)).containsExactlyInAnyOrder("first", "third");
}
}
7.4 Multithreading en concurrency
In andere programmeertalen
De concepten in andere programmeertalen die het dichtst aanleunen bij Java’s multithreading en concurrency primitieven zijn
- pthreads in C
std::thread en aanverwanten in C++- de
threading en multiprocessing modules in Python - de
System.Threading namespace in C#
Wat en waarom?
We maken eerst onderscheid tussen de begrippen parallellisme en concurrency.
Bij parallellisme (soms ook multiprocessing genoemd) worden meerdere instructies gelijktijdig uitgevoerd.
Dit vereist meerdere verwerkingseenheden (machines, CPU’s, CPU cores, …) waarop die instructies uitgevoerd kunnen worden.
Parallellisme wordt interessant wanneer er veel instructies uitgevoerd moeten worden die onafhankelijk van elkaar kunnen gebeuren.
Hoe meer afhankelijkheden er zijn, hoe meer er gecoördineerd moet worden, wat leidt tot meer overhead.
Bij concurrency (soms ook multitasking genoemd) zijn meerdere taken actief op een bepaald moment.
Dat betekent dat een tweede taak al kan starten voordat de eerste afgelopen is.
Het hoeft echter niet zo te zijn dat er ook gelijktijdig instructies voor elk van die taken uitgevoerd worden.
Concurrency impliceert dus geen parallelisme: je kan concurrency hebben met slechts 1 single-core CPU.
Er zijn meerdere mogelijkheden om concurrency te bereiken met slechts één CPU:
- pre-emption: een externe scheduler (bijvoorbeeld in het besturingssysteem) beslist wanneer en voor hoelang een bepaalde taak de processor ter beschikking krijgt. Een voorbeeld hiervan is time slicing: het besturingssysteem onderbreekt elke taak na een bepaalde vaste tijd (of aantal instructies), om de controle vervolgens aan een andere taak te geven.
- cooperative multitasking: een taak beslist zelf wanneer die de controle teruggeeft, bijvoorbeeld wanneer er gewacht moet worden op een ’trage’ operatie zoals het lezen van een bestand, het ontvangen van een inkomend netwerkpakket, …. Veel programmeertalen (maar niet Java) ondersteunen coöperatieve multitasking via coroutines en async/await keywords.
Het spreekt voor zich dat, op moderne (multi-core) machines, concurrency en parallelisme vaak gecombineerd worden. Er zijn dus meerdere taken actief, waarvan sommige ook tegelijkertijd uitgevoerd worden.
Multithreading tenslotte is een specifiek concurrency-mechanisme: er worden, binnen eenzelfde proces van het besturingssysteem, meerdere ’threads’ gestart om taken uit te voeren.
Deze threads delen hetzelfde geheugen (namelijk dat van het proces), en kunnen daardoor dus efficiënter data uitwisselen dan wanneer elke taak als apart proces gestart zou worden.
Op elk moment kunnen er dus meerdere threads bestaan, die (afhankelijk van of er ook parallellisme is in het systeem) al dan niet gelijktijdig instructies uitvoeren.
Binnen een Java-programma is multithreading de voornaamste manier om zowel parallelisme als concurrency te bereiken.
IO-bound vs CPU-bound tasks
De taken die al dan niet gelijktijdig uitgevoerd moeten worden, kunnen onderverdeeld worden in zogenaamde CPU-bound en IO-bound taken.
Bij een CPU-bound taak wordt de uitvoeringstijd voornamelijk gedomineerd door de uitvoering van instructies (berekeningen), bijvoorbeeld algoritmes, beeldverwerking, simulaties, ….
Hoe sneller de CPU, hoe sneller de taak dus afgewerkt kan worden.
Een IO-bound task daarentegen is vaak aan het wachten op externe gebeurtenissen (interrupts), zoals netwerk- of schijf-toegang, timers, gebruikersinvoer, …
Een snellere CPU zal deze taak niet sneller doen gaan.
In het algemeen is parallellisme vooral nuttig wanneer er veel CPU-bound taken zijn.
De totale tijd die nodig is om alle taken uit te voeren kan op die manier geminimaliseerd worden.
Voor IO-bound tasks is parallelisme niet noodzakelijk een goede oplossing: de verschillende CPU’s zouden gelijktijdig aan het wachten zijn op externe interrupts.
Het gebruik van concurrency kan hier wel soelaas bieden: terwijl één taak wacht op een externe gebeurtenis, kan een andere verder uitgevoerd worden.
Threads in Java
De basisklasse in Java om te werken met multithreading is de Thread-klasse.
Typisch geef je een Runnable mee die uitgevoerd moet worden.
Dat kan een object zijn, een lambda, of een method reference.
Een aangemaakte thread start niet automatisch; om de uitvoering van de thread te starten, moet je de start-methode oproepen.
Als je wil wachten tot de thread afgelopen is, kan dat via de join-methode. Deze blokkeert de uitvoering tot de uitvoering van de thread afloopt.
Je kan ook een timeout meegeven aan join, met de maximale tijdsduur dat je wilt wachten. Als deze tijd voorbij is vooraleer de thread afloopt, wordt een InterruptedException gegooid.
Bijvoorbeeld: onderstaande code start een nieuwe thread, die een regel uitprint.
Er zijn in het programma dus twee threads actief: (1) de thread die de nieuwe thread aanmaakt, start, en er vervolgens (maximaal 2 seconden) op wacht; en (2) de thread die de boodschap uitprint.
Note
Een exception in een thread komt niet terug terecht in de originele thread; deze kan dus ‘verloren’ gaan.
var t1 = new Thread(() -> {
System.out.println("Hello from a new thread");
});
t1.start();
...
t1.join(Duration.ofSeconds(2));
Een standaard Java thread wordt uitgevoerd met een thread van het besturingssysteem (een platform thread, die typisch overeenkomt met een kernel thread).
Zo krijg je dus, op machines die het ondersteunen, ook automatisch parallellisme in Java: meerdere threads kunnen effectief tegelijkertijd instructies uitvoeren.
Een nadeel hiervan is dat het aantal threads beperkt is: elke platform-thread komt met een zekere overhead.
Sinds Java 21 beschikt Java ook over virtual threads.
Dat zijn threads die beheerd worden door de Java Virtual Machine (JVM) zelf, en dus niet 1-1 overeenkomen met een platform thread.
Je JVM zal een virtuele thread koppelen aan een platform thread, en deze terug ontkoppelen op het moment dat de virtuele thread moet wachten op een trage operatie.
De platform thread is dan terug vrij, en kan gebruikt worden om een andere virtuele thread uit te voeren.
Virtual threads zijn het Java-alternatief voor cooperative multitasking.
Het teruggeven van de controle wordt echter afgehandeld door de onderliggende bibliotheken, dus als programmeur word je niet geconfronteerd met wachten op blokkerende operaties, of async/await keywords. Je schrijft je code dus gewoon zoals sequentiële code zonder rekening te houden met mogelijk blokkerende operaties.
Virtuele threads hebben ook weinig overhead; je kan er zonder probleem duizenden van aanmaken zonder significante impact op de performantie.
We gaan het in de rest van dit hoofdstuk enkel hebben over de gewone (platform) threads, dus niet over virtual threads.
Synchronisatie
Wanneer meerdere threads (of processen) met gedeelde data werken, ontstaat er een nood aan synchronisatie.
Het kan immers zijn dat beide threads dezelfde data lezen en/of aanpassen, waardoor de data inconsistent wordt.
Dat wordt een race-conditie genoemd.
Race-conditie
Neem het voorbeeld hieronder: één thread verhoogt de waarde van een teller 10.000 keer, de andere verlaagt die 10.000 keer.
Welke waarde van de teller verwacht je op het einde van de code?
class Counter {
private int count = 0;
public void increment() { count++; }
public void decrement() { count--; }
public int getCount() { return count; }
}
var counter = new Counter();
var inc = new Thread(() -> {
for (int i = 0; i < 10_000; i++) counter.increment();
});
var dec = new Thread(() -> {
for (int i = 0; i < 10_000; i++) counter.decrement();
});
inc.start(); dec.start();
inc.join(); dec.join();
System.out.println(counter.getCount());
Op mijn machine gaven drie uitvoeringen van dit programma achtereenvolgens de waarden -803, -5134, en 3041.
Hoe kan dat? Er worden toch evenveel increments uitgevoerd als decrements, waardoor de teller terug op 0 moet uitkomen?
De reden is dat het lezen en terug wegschrijven van de (verhoogde of verlaagde) variabele (i.e., count++ en count--) twee afzonderlijke operaties zijn,
die door het onderlinge verschil in timing tussen de threads op verschillende momenten kunnen plaatsvinden.
Bijvoorbeeld, stel dat count op een bepaald moment gelijk is aan 40; de inc-thread verhoogt de teller 2 keer, en de dec-thread verlaagt de teller 1 keer,
in onderstaande volgorde:
Thread inc | Thread dec |
|---|
| lees count=40 | |
| lees count=40 |
| zet count=41 | |
| lees count=41 | |
| zet count=42 | |
| zet count=39 |
De teller is nu niet 41 (wat de correcte waarde zou zijn na 2 verhogingen en 1 verlaging), maar 39.
De twee verhogingen hebben dus geen enkel effect gehad.
Door andere volgordes (interleavings) van beide threads kan je zo verschillende resultaten krijgen: count kan (in theorie) elke waarde tussen -10.000 en 10.000 hebben op het einde van het programma.
We zeggen dat de Counter-klasse niet thread-safe is: ze kan niet correct gebruikt worden door meerdere threads zonder extra maatregelen.
Volatile variabelen
Bovenstaande code heeft ook nog een ander probleem: wanneer de code uitgevoerd wordt op meerdere CPU’s of cores, kan het kan zijn de count variabele enkel in het lokale geheugen van één CPU aangepast wordt (bv. een register, L1 cache, …), en nog niet meteen naar het (gedeelde) geheugen teruggeschreven wordt.
Zelfs als de tweede thread de waarde van count pas uitleest nadat deze aangepast is door de eerste thread, kan het zijn dat die nog een oude waarde ziet:
Thread inc | Thread dec |
|---|
| lees count=40 | |
| zet count=41 | |
| lees count=41 | |
| zet count=42 | |
| lees count=40 |
| zet count=39 |
| schrijf count naar geheugen | |
| schrijf count naar geheugen |
Om dit op te lossen, kan je in Java een variabele als volatile markeren.
Dat garandeert dat alle aanpassingen aan die variabele meteen naar het centrale geheugen geschreven worden, en vermijdt bovenstaande situatie.
class Counter {
private volatile int count = 0;
public void increment() { count++; }
public void decrement() { count--; }
public int getCount() { return count; }
}
Een volatile variabele is dus een variabele waarvan alle threads steeds de laatste waarde zien.
Technisch gezien komt volatile eigenlijk met een nog sterkere garantie: als thread B een volatile variabele leest die door thread A geschreven werd, zullen ook alle andere (niet-volatile) variabelen die B daarna leest, de waarde hebben die ze in thread A hadden voordat die thread de volatile variabele aanpaste. Met andere woorden, thread B ziet consistente waarden voor alle variabelen die een invloed gehad zouden kunnen hebben op de huidige waarde van de volatile variabele.
Het schrijven en vervolgens lezen van een volatile variabele is dus een synchronisatie-punt tussen threads.
Bijvoorbeeld, stel dat t, u, v, en w vier variabelen zijn, waarvan enkel v als volatile gemarkeerd is. Alle variabelen hebben oorspronkelijk 0 als waarde.
In de tabel hieronder is met een * aangegeven welke waarden in thread B gegarandeerd de meest recente waarden zijn.
In het bijzonder zal variabele w niet noodzakelijk de laatste waarde hebben, omdat die door thread A na variabele v geschreven werd.
Ook variabele u zal, vooraleer v gelezen wordt, niet noodzakelijk de meest recente waarde bevatten.
| Thread A | Thread B |
|---|
| schrijf t=1 | |
| schrijf u=1 | |
| schrijf v=1 (volatile) | |
| schrijf w=1 | |
| lees u=? |
| lees v=1 (volatile) * |
| lees t=1 * |
| lees u=1 * |
| lees w=? |
Merk wel op dat het gebruik van volatile de race-conditie van hierboven nog steeds niet oplost!
Een variabele als volatile markeren heeft immers enkel invloed op de zichtbaarheid van die variabele. Het biedt geen garanties bij gelijktijdige aanpassingen door meerdere threads.
Daarvoor hebben we synchronisatie nodig.
Synchronizatie-primitieven
Om race condities te voorkomen, moet je toegang tot gedeeld geheugen op een of andere manier synchroniseren.
Meer specifiek wil je een sequentie van operaties atomisch kunnen maken: ze moeten worden uitgevoerd alsof ze één primitieve operatie zijn, die niet onderbroken kan worden door een andere thread.
In het voorbeeld van hierboven wil je dus dat het lezen, verhogen, en wegschrijven van de teller steeds als één geheel uitgevoerd wordt, in plaats van als twee aparte operaties.
Java biedt meerdere synchronizatie-primitieven aan. Sommigen zitten ingebouwd in de taal (bv. volatile en synchronized; zie later), andere zitten in de packages java.util.concurrent en java.util.concurrent.locks.
We bespreken er hier enkele.
Semafoor
Een Semaphore deelt een gegeven maximum aantal toestemmingen uit aan threads (via acquire()). Alle volgende threads die toestemming willen, moeten wachten tot een van de vorige toestemmingen terug ingeleverd wordt (via release()). Een binaire semafoor (met maximaal 1 toestemming) kan dienen als mutual exclusion lock (mutex). Een semafoor houdt (conceptueel) enkel een teller bij van het resterend aantal toestemmingen, en niet welke thread al toestemming heeft. Er is dan ook geen enkele garantie of verificatie dat een thread die release() oproept effectief zo’n toestemming verkregen had; het aantal beschikbare toestemmingen wordt gewoon terug verhoogd.
Een voorbeeld van het gebruik van een semafoor voor de implementatie van Counter:
class Counter {
private volatile int count = 0;
private final Semaphore sem = new Semaphore(1);
public void increment() throws InterruptedException {
sem.acquire();
try {
count++;
} finally {
sem.release();
}
}
public void decrement() throws InterruptedException {
sem.acquire();
try {
count--;
} finally {
sem.release();
}
}
public int getCount() {
return count;
}
}
Met het gebruik van een semafoor voor synchronisatie krijg je ook automatisch zichtbaarheids-garanties; je kan het vrijgeven van de semafoor beschouwen als het schrijven naar een volatile variabele, en het verkrijgen van een toestemming als het lezen van een volatile variabele.
Alle wijzigingen die gedaan worden voor het vrijgeven van de semafoor zijn dus zichtbaar voor alle threads die nadien een toestemming verkrijgen.
Lock
De Lock interface, en de implementaties ReentrantLock, stellen een mechanisme voor waarbij een thread de lock kan verkrijgen (lock()) en terug vrijgeven (unlock()). Hierbij wordt wél nagegaan dat enkel de thread die de lock verkregen heeft, de lock terug kan vrijgeven. ‘Re-entrant’ betekent dat een thread die reeds een lock heeft, verder mag gaan wanneer die een tweede keer lock() oproept (op hetzelfde lock-object).
Een voorbeeld van het gebruik van een ReentrantLock voor de implementatie van Counter:
class Counter {
private volatile int count = 0;
private final Lock lock = new ReentrantLock();
public void increment() {
lock.lock();
try {
count++;
} finally {
lock.unlock();
}
}
public void decrement() {
lock.lock();
try {
count--;
} finally {
lock.unlock();
}
}
public int getCount() {
return count;
}
}
Net zoals bij een semafoor krijg je bij het gebruik van een lock ook automatisch zichtbaarheids-garanties; je kan ‘unlock()’ beschouwen als het schrijven naar een volatile variabele, en ’lock()’ als het lezen van een volatile variabele.
Alle wijzigingen die gedaan worden voor het unlocken zijn dus zichtbaar voor alle threads die nadien lock uitvoeren.
AtomicInteger
Specifiek voor primitieve types biedt Java ook een verzameling atomische objecten aan, bijvoorbeeld AtomicInteger. Daarop zijn operaties gedefinieerd zoals incrementAndGet, updateAndGet, getAndAdd, …. Bovenstaande counter kan dus ook eenvoudig als volgt geïmplementeerd worden:
class Counter {
private final AtomicInteger count = new AtomicInteger(0);
public void increment() { count.incrementAndGet(); }
public void decrement() { count.decrementAndGet(); }
public int getCount() { return count.get(); }
}
Er zijn ook andere klassen, bijvoorbeeld AtomicLong, AtomicBoolean, AtomicIntegerArray, AtomicReferenceArray, …
Deze klassen zijn efficiënt geïmplementeerd, en hebben dus de voorkeur wanneer er enkel gesynchroniseerd moet worden om een primitieve variabele of array aan te passen.
Synchronized
Het gebruiken van een lock is zo alomtegenwoordig dat, in Java, elk object als een lock gebruikt kan worden door middel van het synchronized keyword.
Bijvoorbeeld:
class Counter {
private volatile int count = 0;
private final Object lock = new Object();
public void increment() {
synchronized (lock) {
count++;
}
}
public void decrement() {
synchronized (lock) {
count--;
}
}
public int getCount() {
return count;
}
}
Op deze manier beschikt elk Counter-object over een eigen object dat als lock gebruikt wordt. Het synchronized-block geeft aan dat dat lock nodig is om de code in het bijhorende blok uit te voeren, en de lock wordt automatisch terug vrijgegeven op het einde van dat block.
Omdat elk object in Java zo als lock gebruikt kan worden, hoeven we geen apart object aan te maken; we kunnen ook gewoon this gebruiken:
class Counter {
private volatile int count = 0;
public void increment() {
synchronized (this) {
count++;
}
}
public void decrement() {
synchronized (this) {
count--;
}
}
public int getCount() {
return count;
}
}
Tenslotte laat Java ook toe om een hele methode als synchronized te definiëren.
Dat heeft hetzelfde effect als de code met synchronized(this) hierboven:
class Counter {
private volatile int count = 0;
public synchronized void increment() {
count++;
}
public synchronized void decrement() {
count--;
}
public int getCount() {
return count;
}
}
Code die gebruik maakt van synchronized heeft ook zichtbaarheids-garanties; je kan het einde van een synchronized-block beschouwen als het schrijven naar een volatile variabele (die hoort bij het object waarop gesynchroniseerd wordt), en het begin ervan als het lezen van die volatile variabele.
Alle wijzigingen die gedaan worden voor of in een synchronized-blok of methode zijn dus zichtbaar voor alle threads die nadien een synchronized-blok of methode uitvoeren, tenminste als er gesynchroniseerd wordt op hetzelfde object.
In onderstaande code is er dus geen garantie dat thread B de acties van thread A ziet:
Object lock1 = new Object();
Object lock2 = new Object();
// in thread A
synchronized(lock1) {
// acties van A
}
// later...
// in thread B
synchronized(lock2) {
// acties van B
}
Deadlocks
Threads die werken met locks kunnen in een deadlock geraken wanneer ze op elkaar wachten.
Geen enkele thread kan dan vooruitgang maken.
Bijvoorbeeld, in onderstaande code heeft de counter een apart read- en write-lock.
Beide threads proberen om de twee locks te verkrijgen, maar in omgekeerde volgorde.
class Counter {
public final Object readLock = new Object();
public final Object writeLock = new Object();
public volatile int value;
}
var counter = new Counter();
var inc = new Thread(() -> {
for (int i = 0; i < 10_000; i++) {
synchronized (counter.readLock) {
synchronized (counter.writeLock) {
counter.value++;
}
}
}
});
var dec = new Thread(() -> {
for (int i = 0; i < 10_000; i++) {
synchronized (counter.writeLock) {
synchronized (counter.readLock) {
counter.value--;
}
}
}
});
inc.start(); dec.start();
inc.join(); dec.join();
System.out.println(counter.value);
In sommige gevallen kan dat leiden tot een deadlock, namelijk wanneer een thread onderbroken wordt tussen het verkrijgen van beide locks:
Thread inc | Thread dec |
|---|
| acquire readLock | |
| acquire writeLock |
| wait (forever) for readLock … |
| wait (forever) for writeLock… | |
Er is geen eenvoudige manier om deadlocks te vermijden, behalve de applicatie erg zorgvuldig te ontwerpen.
Enkele technieken die hierbij kunnen helpen zijn:
- niet meer locken dan strikt noodzakelijk
- locks altijd in een welbepaalde volgorde verkrijgen
- timeouts gebruiken
Immutability
Wanneer we praten over concurrency, is het een goed idee om ook immutability te vermelden.
Een immutable object kan nooit van waarde wijzigen: eens aangemaakt blijven alle waardes hetzelfde.
In de praktijk betekent dat dat alle velden van het object als final gedeclareerd worden.
Wanneer meerdere threads eenzelfde immutable object gebruiken, kunnen er per definitie geen race condities optreden; ook beschikt elke thread altijd over de laatste waarde (volatile is dus niet nodig).
Wanneer mogelijk, gebruik je dus best immutable objecten in een applicatie met concurrency.
Records zijn uiterst geschikt om eenvoudig dergelijke immutable objecten te maken, en gaan dus goed samen met concurrency!
Concurrent data structures
Zoals we hierboven gezien hebben, is niet elke klasse automatisch geschikt om (correct) door meerdere threads tegelijk gebruikt te worden.
Ook de ingebouwde collectie-types (bv. ArrayList, LinkedList) zijn niet thread-safe.
Je kan een thread-safe collectie verkrijgen door hulpfuncties in de Collections-klasse, bijvoorbeeld Collections.synchronizedList(unsafeList).
Dat geeft een view op de gegeven collectie terug waarvan alle methodes synchronized zijn.
Dat houdt in de praktijk dus in dat de collectie op elk moment slechts door 1 thread gebruikt kan worden.
Bovendien, wanneer je itereert over de elementen in de collectie, bijvoorbeeld via een iterator of stream (zie later), moet het gebruik van die iterator ook in een sycnhronized blok staan (met de collectie als object), zodat de lijst niet aangepast kan worden tijdens het itereren.
Omdat ook een foreach-lus een iterator gebruikt, moet die lus ook in een synchronized-blok staan:
List myList = Collections.synchronizedList(new ArrayList<E>());
...
synchronized(myList) {
var it = myList.iterator();
while (it.hasNext()) {
...
}
}
...
synchronized(myList) {
for (var element : myList) {
...
}
}
Bovenop die manier om ‘gewone’ collecties thread-safe te maken, zijn er ook implementaties die specifiek ontworpen zijn voor concurrency.
Bijvoorbeeld, een CopyOnWriteArrayList is een thread-safe lijst, geschikt voor wanneer er veel vaker gelezen wordt uit de lijst dan dat er naar geschreven wordt.
Deze implementatie dan is efficiënter dan een gewone ArrayList die gesynchroniseerd wordt via de synchronizedList-hulpfunctie.
Zoals de naam zegt wordt de onderliggende array nooit aangepast, maar wel volledig gekopieerd elke keer ernaar geschreven wordt.
Het voordeel is dat lezen kan zonder enige synchronizatie, omdat de inhoud van de array zelf nooit meer aangepast wordt.
Er bestaat ook een ConcurrentHashMap, die een thread-safe Map implementeert.
Ook hier is deze efficiënter dan een gesynchroniseerde Map, omdat nooit de hele datastructuur gelockt wordt.
High-level concurrency abstractions
Totnogtoe hebben we steeds zelf threads aangemaakt.
Zoals eerder vermeld komt elke thread echter met een redelijk grote overhead, en wordt het al snel complex om bij te houden welke threads we hebben en hoeveel er zijn.
We willen daarom de gebruikte threads makkelijk kunnen beheren.
Executor
Java biedt enkele hoog-niveau abstracties aan om te werken met threads.
De basisklasse daarvoor is een Executor.
Deze ontkoppelt de taak die uitgevoerd moet worden van de thread waarin die uitgevoerd wordt.
Aan een Executor kan je dus Runnable’s (of lambda’s of method references) geven die uitgevoerd moeten worden, zonder zelf de threads te beheren.
Er is ook een subinterface ExecutorService die enkele methodes toevoegt, bijvoorbeeld het afsluiten van een executor.
Tenslotte is er de ScheduledExecutorService die methodes toevoegt om taken te plannen (bijvoorbeeld uitvoeren na een bepaalde tijd, eenmalig of herhaald).
Vaak willen we het aantal threads dat gebruikt wordt beperken, bijvoorbeeld tot ongeveer het aantal aanwezige processoren of cores.
Dat kan met een ThreadPool: een verzameling van threads die, eenmaal aangemaakt, herbruikt kunnen worden.
Er is een ThreadPoolExecutor die exact dat doet.
Je kan die zelf aanmaken, maar dat kan makkelijker via hulpmethodes in de Executors klasse.
Bijvoorbeeld:
var pool = Executors.newFixedThreadPool(5);
pool.submit(() -> someTask());
pool.submit(() -> someOtherTask());
...
pool.close(); // wacht tot alle taken afgelopen zijn.
maakt een ExecutorService aan met ten hoogste vijf threads.
Nieuwe taken die aangeboden worden wanneer alle vijf threads bezig zijn met andere taken, belanden in een wachtrij tot ze aan de beurt zijn.
Met de close-methode zorg je ervoor dat er geen nieuwe taken meer kunnen bijkomen, en wacht je tot alle bestaande taken afgelopen zijn.
Er zijn ook andere varianten die je kan aanmaken via de Executors-klasse, bijvoorbeeld
newCachedThreadPool: herbruikt threads indien voorhanden, en maakt anders een nieuwe thread aan. Threads zonder werk worden na een bepaalde tijd beëindigd.newSingleThreadExecutor: een executor met slechts één thread die al het aangeboden werk (na elkaar) uitvoert.newSingleThreadScheduledExecutor: zelf de als hierboven, maar dan met een ScheduledExecutor als resultaat. Hiermee kan je dus bijvoorbeeld taken op regelmatige tijdstippen uitvoeren.
Het aanmaken en vervolgens wachten op alle taken kan ook via een zogenaamd try-with-resources statement.
Dat is een eenvoudige manier om te wachten op alle taken en ervoor te zorgen dat de pool altijd afgesloten wordt, ook als er exceptions gegooid worden.
(Een try-with-resource statement kan in Java ook voor andere zaken gebruikt worden, in het bijzonder met resources die na gebruik terug gesloten moeten worden, bijvoorbeeld een bestand.)
try (var pool = Executors.newFixedThreadPool(5)) {
pool.submit(() -> someTask());
pool.submit(() -> someOtherTask());
}
// de pool is hier gesloten, en alle taken zijn uitgevoerd.
Fork-Join pool
Een fork-join pool is een specifiek type Executor voor taken die (recursief) nieuwe subtaken genereren.
Deze subtaken worden dan mee opgenomen in de lijst van uit te voeren taken.
Een fork-join pool is vooral nuttig wanneer de taken onafhankelijk van elkaar zijn, en achteraf gecombineerd worden.
Er wordt gebruik gemaakt van work stealing: threads in de pool die niets meer te doen hebben, kunnen subtaken beginnen uitvoeren die gegenereerd werden door een andere thread.
We gaan hier niet verder in op het gebruik van een fork-join pool.
Testen van concurrent code
Het testen of bepaalde code thread-safe is, is allesbehalve eenvoudig.
Ten eerste moeten we de tests uitvoeren met meerdere threads; concurrency-problemen zijn immers veelal onzichtbaar als er maar één thread in het spel is.
Bovendien is een correct resultaat na één uitvoering van de test geen garantie dat de code ook correct is.
Er kan immers een probleem zijn dat niet tot uiting kwam bij die specifieke uitvoering (met andere woorden, bij die specifieke interleaving van de threads), maar dat zich wel zou manifesteren bij een andere uitvoeringsvolgorde.
De test meerdere keren herhalen kan in zo’n gevallen soelaas bieden.
In Java kunnen we gebruik maken van een library zoals jcstress.
Deze library laat toe om testcode te schrijven die onder verschillende regimes uitgevoerd wordt, om zo de kans te vergroten dat thread safety problemen (bv. race-condities) aan het licht komen.
De jcstress library wordt ook gebruikt om de concurrency-aspecten van de implementatie van de Java Virtual Machine zelf te testen.
jcstress toevoegen aan je project
Voeg volgende regel toe aan de plugins sectie van je build.gradle:
plugins {
...
id 'io.github.reyerizo.gradle.jcstress' version '0.8.15'
}
Zorg ervoor dat IntelliJ je nieuwe Gradle-configuratie verwerkt (klik op het olifantje dat verschijnt).
In je project maak je nu een extra folder onder src, namelijk src/jcstress, en daaronder een folder src/jcstress/java.
Voeg deze java folder toe als ‘Sources root’: rechtsklik op de java folder > Mark Directory As > Sources root.
IntelliJ zou de folder nu blauw moeten kleuren.
Anatomie van een jcstress test
Een test in jcstress maakt geen gebruik van JUnit-annotaties (@Test etc), maar van een eigen set van annotaties.
Hier vind je een voorbeeld en wat meer uitleg over de betekenis annotaties.
We bespreken de belangrijkste annotaties ook hieronder, met als voorbeeld het testen van onze originele Counter-klasse.
package demo;
import org.openjdk.jcstress.annotations.*;
import org.openjdk.jcstress.infra.results.I_Result;
@JCStressTest
@Outcome(id="0", expect = Expect.ACCEPTABLE, desc = "Incremented and decremented atomically")
@Outcome(id="", expect = Expect.FORBIDDEN, desc = "Unexpected counter value")
@State
public class CounterTest {
private final Counter counter = new Counter();
private final int N = 5;
@Actor
public void incrementer() {
for (int i = 0; i < N; i++) {
counter.increment();
}
}
@Actor
public void decrementer() {
for (int i = 0; i < N; i++) {
counter.decrement();
}
}
@Arbiter
public void arbiter(I_Result result) {
result.r1 = counter.getCount();
}
}
We zien in de test hetvolgende:
- De annotatie
@JCStressTest duidt aan dat het om een jcstress-test gaat - De annotatie
@State geeft aan in welke klasse we de te testen state-variabelen vinden; hier is dat de variabele counter, in de CounterTest klasse zelf. Het object met @State zal erg vaak aangemaakt worden, en moet voldoen aan bepaalde voorwaarden (bv. publieke constructor zonder argumenten).
We negeren @Outcome nog even, en kijken naar de actoren en arbiter:
- Elke methode met
@Actor staat voor de code die door één thread uitgevoerd wordt. Hier hebben we 2 verschillende actoren: eentje die de teller N keer verhoogt, en een andere die de teller N keer verlaagt. Het jcstress framework zal de actoren uitvoeren met zoveel mogelijk verschillende interleavings, in de hoop zo eventuele problemen bloot te leggen. - De methode met
@Arbiter (gewoonlijk 1 per test) wordt uitgevoerd nadat alle actoren helemaal klaar zijn. De arbiter bezorgt de data waaraan we kunnen zien of er zich een probleem voorgedaan heeft. In dit geval kijken we naar de waarde van de counter na afloop van de verhogingen en verlagingen. We kennen die counter-waarde toe aan attribuut r1 van het resultaat-object. Dat heeft type I_Result, wat staat voor een resultaat met 1 integer (I). Er zijn ook andere types beschikbaar in de library, bv. II_Result (2 integers), DBI_Result (een double, een byte, en een integer), etc.
Letters in Result-type
Volgende letters worden gebruikt in de types van de Result-objecten:
I: intZ: booleanF: floatJ: longS: shortB: byteC: charD: doubleL: object
Opmerking
Het is niet strikt noodzakelijk om een @Arbiter-methode te hebben.
Je kan ook één van de @Actor-methodes een result-parameter geven en zonder arbiter werken.
Tenslotte bespreken we de @Outcome-annotaties. Die geven aan welke resultaat-objecten verwacht/acceptabel zijn en welke niet.
In het voorbeeld hierboven:
- Een resultaat met
r1=0 is acceptabel; dat is wat we verwachten van een thread-safe counter. Dat geven we aan met @Outcome(id="0", expect = Expect.ACCEPTABLE, ...). Merk op dat de id parameter het verwachte resultaat (uit de I_Result parameter) voorstelt. - Elk ander resultaat is niet toegelaten:
@Outcome(id="", expect = Expect.FORBIDDEN, ...).
Als we een resultaat met meerdere waarden zouden hebben (bv. een II_Result) dan specifiëren we de outcome bijvoorbeeld als @Outcome(id="0, 1", ...), wat overeenkomt met r1=0 en r1=1.
Tests uitvoeren
Je kan de tests uitvoeren via de jcstress taak in Gradle: ./gradlew jcstress.
Dit genereert uitvoer op de console, en ook een html-bestand in build/reports/jcstress.
Daarin vinden we een tabel zoals onderstaande, die aangeeft hoe vaak elk resultaat bekomen werd:
We zien hieruit duidelijk dat onze counter niet thread-safe is: alle waarden van -5 tot 5 werden bekomen in sommige tests.
Oefeningen
Zie oefeningen.