Preskoči na glavni sadržaj

Razgovarajmo o Java StringBuilder i StringBuffer braći

Chenmo Wang ErJava jezgroNizovi i stringovi1593 reči5 minuta

"Brate, prethodni članak o detaljnom razumevanju String.intern() je pomenuo StringBuilder, hajde da o njima porazgovaramo u ovom odeljku!"

Razlika između StringBuffer i StringBuilder

Pošto su stringovi nepromenljivi, kada naiđemo na nadovezivanje stringova (naročito kada koristimo operator +), moramo razmotriti pitanje performansi. Ne možete bezbrižno stvarati previše String objekata i tako stvarati nepotreban pritisak na dragocenu memoriju.

Zato je Java dizajnirala klasu StringBuffer posebno za rešavanje ovog problema.

public final class StringBuffer extends AbstractStringBuilder implements Serializable, CharSequence {

    public StringBuffer() {
        super(16);
    }
    
    public synchronized StringBuffer append(String str) {
        super.append(str);
        return this;
    }

    public synchronized String toString() {
        return new String(value, 0, count);
    }

    // ostale metode
}

Međutim, pošto su metode StringBuffer-a za rad sa stringovima obeležene synchronized ključnom rečju radi sinhronizacije — prvenstveno iz sigurnosnih razloga u višenitnom okruženju — u jednonitnom okruženju brzina izvršavanja biće niža, jer se dodaju nepotrebne brave.

Zato je Java StringBuffer-u "dobila brata" po imenu StringBuilder, rekavši: "Dete, ne brini o bezbednosti niti, koristi se u jednonitnom okruženju, tu će efikasnost biti mnogo veća; ako budeš morao da menjaš string u višenitnom okruženju, tada možeš upotrebiti ThreadLocal da izbegneš višenitne sukobe."

public final class StringBuilder extends AbstractStringBuilder
    implements java.io.Serializable, CharSequence
{
    // ...

    public StringBuilder append(String str) {
        super.append(str);
        return this;
    }

    public String toString() {
        // Napravi kopiju, ne deli niz
        return new String(value, 0, count);
    }

    // ...
}

Osim što se razlikuje ime klase i što metode nemaju synchronized, u suštini su potpuno iste.

U stvarnom razvoju, StringBuilder se koristi mnogo češće nego StringBuffer — može se čak reći da je StringBuilder potpuno zamenio StringBuffer.

Upotreba StringBuilder-a

Kao što smo već razgovarali, Java je interpretirani programski jezik, tako da kada kompilator naiđe na operator +, prevodi liniju koda new String("Erge") + new String("Sanmei") u sledeći oblik:

new StringBuilder().append("Erge").append("Sanmei").toString();

Ovaj proces ne vidimo, ali upravo je u tome "pamet" Jave: ona tokom prevođenja potajno može da uradi mnoge optimizacije za nas, čime se povećava efikasnost našeg razvoja (+ se piše mnogo zgodnije nego kreiranje StringBuilder objekta), a da se pri tome ne utiče na efikasnost izvršavanja na JVM-u.

Naravno, kada bismo upotrebili javap da dekompajliramo bajtkod new String("Erge") + new String("Sanmei"), takođe bismo mogli da nazremo prisustvo StringBuilder-a.

javap i bajtkod biće detaljno objašnjeni kasnije, kada budemo govorili o JVM-u; kliknite na link za više detalja.

0: new           #2                  // class java/lang/StringBuilder
3: dup
4: invokespecial #3                  // Method java/lang/StringBuilder."<init>":()V
7: new           #4                  // class java/lang/String
10: dup
11: ldc           #5                  // String Erge
13: invokespecial #6                  // Method java/lang/String."<init>":(Ljava/lang/String;)V
16: invokevirtual #7                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
19: new           #4                  // class java/lang/String
22: dup
23: ldc           #8                  // String Sanmei
25: invokespecial #6                  // Method java/lang/String."<init>":(Ljava/lang/String;)V
28: invokevirtual #7                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
31: invokevirtual #9                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
34: areturn

Vidi se da Java kompilator prevodi operaciju nadovezivanja stringova (+) u poziv append metode StringBuilder objekta, a zatim poziva toString metodu StringBuilder objekta kako bi vratio nadovezani string.

Unutrašnja implementacija StringBuilder-a

Pogledajmo toString metodu StringBuilder-a:

public String toString() {
    return new String(value, 0, count);
}

value je niz tipa char:

/**
 * The value is used for character storage.
 */
char[] value;

Prilikom kreiranja StringBuilder objekta, za value se dodeljuje određeni memorijski prostor (početni kapacitet 16) za skladištenje stringa.

/**
 * Constructs a string builder with no characters in it and an
 * initial capacity of 16 characters.
 */
public StringBuilder() {
    super(16);
}

Kako se string nadovezuje, dužina niza value raste, pa je u implementaciji StringBuilder objekta dužina niza value dinamički proširiva, baš kao kod ArrayList-a.

Pogledajmo još jednom toString metodu StringBuilder-a:

public String toString() {
    return new String(value, 0, count);
}

value služi za skladištenje niza karaktera koje StringBuilder objekat sadrži. count je promenljiva tipa int koja označava dužinu niza karaktera. Metoda toString() poziva new String(value, 0, count), čime se kreira novi string objekat pomoću prvih count elemenata niza value počevši od indeksa 0, i zatim ga vraća.

Pogledajmo sada i append metodu:

public StringBuilder append(String str) {
    super.append(str);
    return this;
}

U stvari, ona poziva metodu append(String str) iz AbstractStringBuilder-a. U AbstractStringBuilder-u metoda append(String str) proverava da li karaktera u trenutnom nizu karaktera ima dovoljno; ako nema dovoljno, vrši se proširenje kapaciteta, a zatim se zadati string nadovezuje na kraj niza karaktera.

public AbstractStringBuilder append(String str) {
    if (str == null)
        return appendNull();
    int len = str.length();
    ensureCapacityInternal(count + len);
    str.getChars(0, len, value, count);
    count += len;
    return this;
}

Metoda append(String str) nadovezuje zadati string na trenutni niz karaktera. Ako je zadati string null, nadovezuje se string "null"; u suprotnom se proverava dužina zadatog stringa, a zatim se na osnovu broja karaktera u trenutnom nizu i dužine zadatog stringa procenjuje da li je potrebno proširenje kapaciteta.

Ako je proširenje potrebno, poziva se metoda ensureCapacityInternal(int minimumCapacity). Nakon proširenja, karakteri zadatog stringa se kopiraju u niz karaktera.

Pogledajmo metodu ensureCapacityInternal:

private void ensureCapacityInternal(int minimumCapacity) {
    // Nema dovoljno prostora, proširi kapacitet
    if (minimumCapacity - value.length > 0)
        expandCapacity(minimumCapacity);
}

void expandCapacity(int minimumCapacity) {
    // Strategija proširenja: novi kapacitet je dvostruka stara vrednost plus 2
    int newCapacity = value.length * 2 + 2;
    // Ako je novi kapacitet manji od zadatog minimalnog kapaciteta, novi kapacitet postaje jednak minimalnom
    if (newCapacity - minimumCapacity < 0)
        newCapacity = minimumCapacity;
    // Ako je novi kapacitet manji od 0, novi kapacitet postaje Integer.MAX_VALUE
    if (newCapacity < 0) {
        if (minimumCapacity < 0) // prelivanje (overflow)
            throw new OutOfMemoryError();
        newCapacity = Integer.MAX_VALUE;
    }
    // Proširuje kapacitet niza karaktera na novi kapacitet
    value = Arrays.copyOf(value, newCapacity);
}

Metoda ensureCapacityInternal(int minimumCapacity) osigurava da kapacitet trenutnog niza karaktera bude barem jednak zadatom minimalnom kapacitetu minimumCapacity. Ako je trenutni kapacitet manji od zadatog, dodeljuje se novi unutrašnji niz za niz karaktera. Novi kapacitet se izračunava na sledeći način:

  • Ako je zadati minimalni kapacitet veći od trenutnog kapaciteta, novi kapacitet iznosi dvostruku staru vrednost plus 2. Zašto plus 2? Za veoma male stringove (na primer prazan StringBuilder ili onaj sa samo jednim karakterom), puko udvostručavanje kapaciteta možda i dalje neće biti dovoljno da primi više karaktera. U takvim slučajevima, + 2 daje minimalnu granu rasta, osiguravajući da čak i za vrlo mali početni kapacitet, nakon proširenja bude moguće dodati barem još nekoliko karaktera bez potrebe za trenutnim ponovnim proširenjem.
  • Ako je zadati minimalni kapacitet manji ili jednak trenutnom kapacitetu, ne vrši se proširenje; jednostavno se vraća trenutni objekat.

Pre nego što izvrši proširenje, metoda ensureCapacityInternal(int minimumCapacity) prvo proverava da li je kapacitet trenutnog niza karaktera dovoljan; ako nije, poziva metodu expandCapacity(int minimumCapacity) radi proširenja. Metoda expandCapacity(int minimumCapacity) prvo izračunava novi kapacitet, a zatim koristi metodu Arrays.copyOf(char[] original, int newLength) da proširi originalni niz karaktera na veličinu novog kapaciteta.

  • Arrays je pomoćna klasa u Javi za rad sa nizovima; o njoj će takođe biti reči kasnije.
  • Što se tiče proširenja kapaciteta, ponovo će biti reči kada budemo govorili o ArrayList-u; tada možete pogledati nazad i uporediti, jer je i donja implementacija ArrayList-a zasnovana na nizu.

Metoda reverse StringBuilder-a

StringBuilder takođe nudi metodu reverse kojom se preokreću karakteri u trenutnom nizu karaktera.

public StringBuilder reverse() {
    super.reverse();
    return this;
}

I ona poziva metodu reverse() iz roditeljske klase AbstractStringBuilder; izostavio sam deo nekarakternog koda.

public AbstractStringBuilder reverse() {
    int n = count - 1; // indeks poslednjeg karaktera u nizu karaktera
    // prolazi kroz prednju polovinu stringa
    for (int j = (n-1) >> 1; j >= 0; j--) {
        int k = n - j; // izračunava indeks karaktera simetričnog u odnosu na j
        char cj = value[j]; // uzima karakter sa trenutne pozicije
        char ck = value[k]; // uzima karakter sa simetrične pozicije
        value[j] = ck; // razmenjuje karaktere
        value[k] = cj; // razmenjuje karaktere
    }
    return this; // vraća objekat graditelja stringa sa preokrenutim redosledom
}
  1. Inicijalizacija: n je indeks poslednjeg karaktera u stringu.
  2. Preokretanje stringa:
    • Metoda pomoću for petlje prolazi kroz prednju i zadnju polovinu stringa — ovo je veoma domišljat detalj koji u poređenju s prolaskom od početka do kraja štedi polovinu vremena. (n-1) >> 1 je bitska reprezentacija izraza (n-1) / 2, odnosno indeks poslednjeg karaktera prednje polovine stringa.
    • U svakoj iteraciji izračunava se indeks k simetričan trenutnom indeksu j, i razmenjuju se karakteri na tim dvema pozicijama.

Sedmi zadatak na LeetCode-u, "007. Preokretanje celog broja", zahteva od nas da preokrenemo celi broj; zapravo se tu može iskoristiti reverse metoda StringBuilder-a.

Rešenje je objavljeno na Tech Pai-u, možete pogledati.

Kratak pregled

"Mislim da si sada razjasnio/la razlike između StringBuilder-a i StringBuffer-a?" upitao sam.

"Ako ti je jasno, znanje možeš proveriti kroz šesti zadatak na LeetCode-u, '006. Cik-cak transformacija'; rešenje sam objavio na Tech Pai-u, može ti poslužiti kao referenca."

"Naravno; zapravo, za sada ti je dovoljno da znaš kako se StringBuilder koristi." Posle gutljaja koka-kole (bez šećera) s desne strane, osetio sam se sjajno.