Preskoči na glavni sadržaj

Alibaba intervjuer: zašto Java priručnik za razvoj strogo zabranjuje brisanje elemenata unutar foreach?

Chenmo Wang ErJava jezgroOkvir kolekcija (kontejneri)1582 reči5 minuta

Ovaj članak takođe koristi formu u kojoj Xiao Er ide na razgovor za posao — radi malo drugačijeg ukusa.

Tog dana Xiao Er je otišao na razgovor u Alibaba, a intervjuer, stari Wang, odmah mu je bacio jedno pitanje: zašto se u Alibaba-ovom Java priručniku za razvoj strogo zabranjuje brisanje elemenata unutar foreach?

Xiao Er se nasmešio kada je to čuo. Zašto? Zato što je dan ranije tačno to pročitao u knjizi „Ergeov put ka naprednom Javom”.

Sledi sadržaj celog članka.

O fail-fast

Da bismo ojačali uvod, najpre ćemo navesti jedan odlomak na engleskom koji objašnjava fail-fast.

In systems design, a fail-fast system is one which immediately reports at its interface any condition that is likely to indicate a failure. Fail-fast systems are usually designed to stop normal operation rather than attempt to continue a possibly flawed process. Such designs often check the system's state at several points in an operation, so any failures can be detected early. The responsibility of a fail-fast module is detecting errors, then letting the next-highest level of the system handle them.

U prevodu, fail-fast je opšta ideja dizajna sistema: čim se otkrije da bi moglo doći do greške, odmah se baca izuzetak i program se ne nastavlja.

public void test(Wanger wanger) {   
    if (wanger == null) {
        throw new RuntimeException("wanger ne sme biti null");
    }
    
    System.out.println(wanger.toString());
}

Čim se otkrije da je wanger null, odmah se baca izuzetak, a pozivaocu se prepusta da odluči kako da postupi u toj situaciji; sledeći korak, wanger.toString(), se više ne izvršava — čime se izbegava pojava ozbiljnije greške.

Često fail-fast svrstavamo u mehanizme otkrivanja greški u Java okviru kolekcija, ali fail-fast nije specifičan samo za taj okvir.

Greška pri brisanju elementa unutar for-each

Razlog što fail-fast predstavljamo u okviru poglavlja o kolekcijama jeste taj što se problem lako reprodukuje.

List<String> list = new ArrayList<>();
list.add("Chenmo Wang Er");
list.add("Chenmo Wang San");
list.add("Programer čiji su članci zaista zanimljivi");

for (String str : list) {
	if ("Chenmo Wang Er".equals(str)) {
		list.remove(str);
	}
}

System.out.println(list);

Ovaj kod na prvi pogled izgleda bez problema, ali pri pokretanju prijavljuje grešku.

Na osnovu informacija iz tragova steka greške, možemo locirati liniju 901 u ArrayList.

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

Dakle, prilikom remove poziva se izvršio metod checkForComodification, koji upoređuje modCount i expectedModCount; pošto nisu jednaki, baca se izuzetak ConcurrentModificationException.

Zašto se uopšte poziva checkForComodification?

Zato što je for-each zapravo sintaksni šećer čija je osnova implementirana preko iteratora Iterator i while petlje. Pogledajmo dekompilovani bajtkod.

List<String> list = new ArrayList();
list.add("Chenmo Wang Er");
list.add("Chenmo Wang San");
list.add("Programer čiji su članci zaista zanimljivi");
Iterator var2 = list.iterator();

while(var2.hasNext()) {
    String str = (String)var2.next();
    if ("Chenmo Wang Er".equals(str)) {
        list.remove(str);
    }
}

System.out.println(list);

Pogledajmo metod iterator klase ArrayList:

public Iterator<E> iterator() {
    return new Itr();
}

Interna klasa Itr implementira interfejs Iterator. Evo njenog izvornog koda.

private class Itr implements Iterator<E> {
    int cursor;            // indeks sledećeg elementa
    int lastRet = -1;      // indeks prethodno vraćenog elementa; -1 ako ga nema
    int expectedModCount = modCount; // brojač izmena ArrayList-a

    Itr() { }  // konstruktor

    public boolean hasNext() { // provera da li postoji sledeći element
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() { // vraća sledeći element
        checkForComodification(); // proverava da li je ArrayList izmenjen
        int i = cursor; // trenutni indeks
        Object[] elementData = ArrayList.this.elementData; // niz elemenata ArrayList-a
        if (i >= elementData.length) // van opsega niza
            throw new ConcurrentModificationException(); // baca izuzetak
        cursor = i + 1; // ažurira indeks sledećeg elementa
        return (E) elementData[lastRet = i]; // vraća sledeći element
    }
}

Dakle, prilikom new Itr() expectedModCount dobija vrednost modCount, a modCount je brojač u ArrayList koji beleži koliko je puta objekat ArrayList izmenjen. Izmena obuhvata dodavanje, brisanje, postavljanje vrednosti elementa itd. Pri svakoj izmeni ArrayList-a, modCount se uvećava za 1.

Tokom obilaska ArrayList-a, ako se u toku obilaska ustanovi da se vrednost modCount ne poklapa sa expectedModCount iteratora, to znači da je ArrayList izmenjen, pa se baca ConcurrentModificationException. Ovaj mehanizam obezbeđuje da iterator prilikom obilaska ArrayList-a ne preskoči niti ponovi elemente, a takođe omogućava detekciju konkurentnih izmena u višenitnom okruženju.

protected transient int modCount = 0;

Analiza logike izvršavanja koda

Da nastavimo sa lociranjem prethodne greške na osnovu traga steka. Evo već pomenutog koda.

List<String> list = new ArrayList<>();
list.add("Chenmo Wang Er");
list.add("Chenmo Wang San");
list.add("Programer čiji su članci zaista zanimljivi");

for (String str : list) {
	if ("Chenmo Wang Er".equals(str)) {
		list.remove(str);
	}
}

System.out.println(list);

Pošto je list prethodno tri puta pozvao metod add.

  • add poziva ensureCapacityInternal
  • ensureCapacityInternal poziva ensureExplicitCapacity
  • ensureExplicitCapacity izvršava modCount++
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
}

Dakle, nakon tri poziva add, vrednost modCount je 3, pa je i expectedModCount nakon new Itr() jednako 3 (pogledajte prethodni izvorni kod Itr-a).

Sada se izvršava for-each petlja obilaska.

U prvom prolazu petlje, „Chenmo Wang Er” je jednak str, pa se izvršava list.remove(str).

  • remove poziva fastRemove
  • fastRemove izvršava modCount++
private void fastRemove(int index) {
    modCount++;
}

Vrednost modCount postaje 4.

U drugom prolazu izvršava se metod next iz Itr-a (String str = (String) var3.next();), a next poziva checkForComodification.

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

Tada je expectedModCount 3, a modCount 4, pa mora da se baci ConcurrentModificationException.

Inače, u Alibaba-ovom Java priručniku za razvoj takođe stoji da se unutar for-each petlje ne smeju vršiti operacije remove/add nad elementima. Za brisanje elementa treba koristiti Iterator.

Razlog je upravo onaj koji smo gore analizirali — fail-fast zaštitni mehanizam.

Kako onda pravilno obrisati element?

1) break nakon remove

List<String> list = new ArrayList<>();
list.add("Chenmo Wang Er");
list.add("Chenmo Wang San");
list.add("Programer čiji su članci zaista zanimljivi");

for (String str : list) {
	if ("Chenmo Wang Er".equals(str)) {
		list.remove(str);
		break;
	}
}

Nakon break, petlja više ne obilazi, što znači da se metod next Iteratora više ne poziva, što znači da se checkForComodification više ne poziva, pa se izuzetak ne baca.

Međutim, kada u listi ima duplikata koje treba obrisati, break nije odgovarajući.

2) for petlja

List<String> list = new ArrayList<>();
list.add("Chenmo Wang Er");
list.add("Chenmo Wang San");
list.add("Programer čiji su članci zaista zanimljivi");
for (int i = 0; i < list.size(); i++) {
	String str = list.get(i);
	if ("Chenmo Wang Er".equals(str)) {
		list.remove(str);
	}
}

for petlja može da zaobilazi fail-fast zaštitni mehanizam — drugim rečima, nakon remove više ne dolazi do izuzetka. Ipak, ovaj program je načelno problematičan. Zašto?

Pri prvom prolazu, i je 0, a list.size() je 3; nakon remove, i postaje 1, ali list.size() postaje 2, jer se veličina liste nakon remove promenila — što znači da je element „Chenmo Wang San” preskočen. Jasno?

Pre remove, list.get(1) bio je „Chenmo Wang San”; ali nakon remove, list.get(1) postaje „Programer čiji su članci zaista zanimljivi”, a list.get(0) postaje „Chenmo Wang San”.

3) Korišćenje Iterator-a

List<String> list = new ArrayList<>();
list.add("Chenmo Wang Er");
list.add("Chenmo Wang San");
list.add("Programer čiji su članci zaista zanimljivi");

Iterator<String> itr = list.iterator();

while (itr.hasNext()) {
	String str = itr.next();
	if ("Chenmo Wang Er".equals(str)) {
		itr.remove();
	}
}

Zašto metoda remove Iterator-a može da zaobiđe fail-fast zaštitni mehanizam? Pogledajte izvorni kod remove i sve će biti jasno.

public void remove() {
    if (lastRet < 0) // ako nema indeksa prethodno vraćenog elementa, baca se izuzetak
        throw new IllegalStateException();
    checkForComodification(); // proverava da li je ArrayList izmenjen

    try {
        ArrayList.this.remove(lastRet); // briše prethodno vraćeni element
        cursor = lastRet; // ažurira indeks sledećeg elementa
        lastRet = -1; // poništava indeks prethodno vraćenog elementa
        expectedModCount = modCount; // ažurira brojač izmena ArrayList-a
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException(); // baca izuzetak
    }
}

Nakon brisanja izvršava se expectedModCount = modCount, čime se obezbeđuje sinhronizacija expectedModCount i modCount.

Kratak pregled

Zašto se ne sme vršiti operacija brisanja unutar foreach?

Zato što je foreach petlja zasnovana na iteratoru, a iterator prilikom obilaska kolekcije održava polje expectedModCount koje beleži broj izmena kolekcije. Ako se unutar foreach petlje izvrši brisanje, vrednost expectedModCount se neće poklapati sa stvarnom vrednošću polja modCount, zbog čega metode hasNext() i next() iteratora bacaju ConcurrentModificationException.

Da bismo izbegli ovu situaciju, treba koristiti metod remove() iteratora, koji nakon brisanja elementa ažurira stanje iteratora i osigurava ispravnost petlje. Ako je u petlji potrebno brisati elemente, koristite remove() iteratora, a ne remove() same kolekcije.

Ovako nešto.

List<String> list = new ArrayList<>();
list.add("Chenmo Wang Er");
list.add("Chenmo Wang San");
list.add("Programer čiji su članci zaista zanimljivi");

Iterator<String> itr = list.iterator();

while (itr.hasNext()) {
	String str = itr.next();
	if ("Chenmo Wang Er".equals(str)) {
		itr.remove();
	}
}

Pored toga, možemo iskoristiti i metod filter() Stream tokova da filtriramo elemente kolekcije, a zatim metodom collect() skupimo filtrirane elemente u novu kolekciju.

List<String> list = new ArrayList<>(Arrays.asList("Chenmo", "Wang Er", "Chen Qingyang"));
list = list.stream().filter(s -> !s.equals("Chen Qingyang")).collect(Collectors.toList());

To bi bilo sve o ovom pitanju — nadamo se da će vam pomoći.