Detaljno čitanje izvornog koda String klase

Upravo sam sedeo na kauču i sa zadovoljstvom čitao poglavlje jack";

— koristi se Latin-1 kodiranje i dovoljna su 4 bajta.

Ali za:

```java
String name = "Miloš";

— nema pomoći, mora se koristiti UTF16 kodiranje.

U izvornom kodu Stringa za JDK 9, kako bi se razlikovali načini kodiranja, dodato je polje coder kojim se to razlikuje.

/**
 * The identifier of the encoding used to encode the bytes in
 * {@code value}. The supported values in this implementation are
 *
 * LATIN1
 * UTF16
 *
 * @implNote This field is trusted by the VM, and is a subject to
 * constant folding if String instance is constant. Overwriting this
 * field after construction will cause problems.
 */
private final byte coder;

Java automatski postavlja odgovarajuće kodiranje na osnovu sadržaja stringa — bilo Latin-1 bilo UTF16.

To znači da je, pri prelasku sa char[] na byte[], kineski znak i dalje dva bajta, a čisti engleski znak sada jedan bajt — dok je pre toga i kineski i engleski znak bio po dva bajta.

U UTF-8 kodiranju, znakovi sa brojevima 0–127 predstavljaju se jednim bajtom, koristeći isto kodiranje kao i ASCII. Samo znakovi sa brojem 128 i više koriste 2, 3 ili 4 bajta.

• Ako postoji samo jedan bajt, najviši bit je 0;
• Ako postoji više bajtova, prvi bajt počevši od najvišeg bita ima onoliko uzastopnih bita postavljenih na 1, koliko se bajtova koristi za kodiranje, dok preostali bajtovi svi počinju sa 10.

Konkretan oblik je:

• 0xxxxxxx: jedan bajt;
• 110xxxxx 10xxxxxx: oblik dvobajtnog kodiranja (počinje sa dve jedinice);
• 1110xxxx 10xxxxxx 10xxxxxx: oblik trobajtnog kodiranja (počinje sa tri jedinice);
• 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx: oblik četvorobajtnog kodiranja (počinje sa četiri jedinice).

Drugim rečima, UTF-8 je promenljive dužine, što je veoma nepogodno za klasu poput String koja ima metode za nasumični pristup. Pod nasumičnim pristupom podrazumevamo metode poput charAt i subString — zadaš bilo koji broj, a String mora da vrati rezultat. Ako svaki karakter u stringu zauzima različito memorije, pri nasumičnom pristupu je potrebno krenuti od početka i brojati dužinu svakog znaka kako bi se pronašao željeni karakter.

Možda će te onda pitati: „Pa UTF-16 je takođe promenljive dužine? Jedan znak može zauzeti i 4 bajta?”

Zaista, UTF-16 koristi 2 ili 4 bajta za skladištenje znakova.

• Za znakove sa Unicode brojem u opsegu 0 ~ FFFF, UTF-16 koristi dva bajta.
• Za znakove sa Unicode brojem u opsegu 10000 ~ 10FFFF, UTF-16 koristi četiri bajta; konkretno, svi bitovi broja znaka se dele u dva dela — viši bitovi se smeštaju u dvobajtnu vrednost u opsegu D800~DBFF, dok se niži bitovi (preostali) smeštaju u dvobajtnu vrednost u opsegu DC00~DFFF.

Međutim, u Javi jedan karakter (char) jeste 2 bajta, pa se znak od 4 bajta u Javi skladišti pomoću dva char-a, a sve operacije nad Stringom se vrše u jedinicama Java karaktera (char): charAt vraća neki po redu char, subString vraća podstring od nekog do nekog char-a, čak i length vraća broj char-ova.

Zato se UTF-16 u svetu Jave može smatrati kodiranjem fiksne dužine.

Referentni link: https://www.zhihu.com/question/447224628

Metod hashCode klase String

„Šesto, svaki string ima svoju hash vrednost, koja se sa velikom verovatnoćom ne ponavlja, pa je String veoma pogodan da bude ključ u HashMap-i (o njoj će biti detaljno reči kasnije).”

Pogledajmo metod hashCode klase String.

private int hash; // kešira heš kod stringa

public int hashCode() {
    int h = hash; // preuzmi heš kod iz keša
    // ako heš kod još nije izračunat (jednak je 0) i string nije prazan, izračunaj ga
    if (h == 0 && value.length > 0) {
        char val[] = value; // preuzmi niz karaktera stringa

        // iteriraj kroz svaki karakter stringa i izračunaj heš kod
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i]; // koristi 31 kao multiplikativni faktor
        }
        hash = h; // keširaj izračunati heš kod
    }
    return h; // vrati heš kod
}

Metod hashCode prvo proverava da li je heš kod već izračunat; ako jeste, direktno vraća keširanu vrednost. U suprotnom, metod u petlji prolazi kroz sve karaktere stringa i koristi kombinaciju množenja i sabiranja da izračuna heš kod.

Ovaj način proračuna se naziva „heš metoda 31”. Pošto izračunavanje završi, dobijena heš vrednost se skladišti u članu hash, kako bi pri sledećem pozivu metoda hashCode mogla direktno da je vrati, bez ponovnog računanja. To je optimizacija putem keširanja, poznata kao „lenjo računanje” (lazy computation).

Heš metoda 31 (31-Hash) je jednostavan i efikasan algoritam za heširanje stringova, koji se često koristi za obradu stringova. Osnovna ideja algoritma je da se svaki karakter u stringu pomnoži sa stepenom fiksnog prostog broja 31 i zatim saberu, čime se dobija heš vrednost. Konkretno, ako je string s dužine n, formula za izračunavanje heša metodom 31 glasi:

H(s) = (s[0] * 31^(n-1)) + (s[1] * 31^(n-2)) + ... + (s[n-1] * 31^0)

Gde s[i] označava ASCII vrednost i-tog karaktera u stringu s, a ^ označava operaciju stepenovanja.

Prednost heš metode 31 je u tome što je jednostavna za implementaciju, da brzo računa i da prilično ravnomerno raspoređuje vrednosti u heš tabeli.

O metodu hashCode ćemo detaljno pričati u posebnom poglavlju — klikni na prethodni link za više.

Metod hashCode klase String možemo simulirati na sledeći način:

public class HashCodeExample {
    public static void main(String[] args) {
        String text = "Chenmo Wang Er";
        int hashCode = computeHashCode(text);
        System.out.println("Heš kod stringa \"" + text + "\" je: " + hashCode);

        System.out.println("String-ov hashCode: " + text.hashCode());
    }

    public static int computeHashCode(String text) {
        int h = 0;
        for (int i = 0; i < text.length(); i++) {
            h = 31 * h + text.charAt(i);
        }
        return h;
    }
}

Pogledajmo rezultat:

Heš kod stringa "Chenmo Wang Er" je: (rezultat metodom 31)
String-ov hashCode: (rezultat ugrađenog metoda)

Rezultati se poklapaju — opet nešto naučio si, zar ne?

Metod substring klase String

U klasi String postoji i jedan često korišćen metod — substring, koji služi za izdvajanje podstringa. Pogledajmo izvorni kod.

public String substring(int beginIndex) {
    // proveri da li je početni indeks manji od 0; ako jeste, baci izuzetak StringIndexOutOfBoundsException
    if (beginIndex < 0) {
        throw new StringIndexOutOfBoundsException(beginIndex);
    }
    // izračunaj dužinu podstringa
    int subLen = value.length - beginIndex;
    // proveri da li je dužina podstringa negativna; ako jeste, baci izuzetak StringIndexOutOfBoundsException
    if (subLen < 0) {
        throw new StringIndexOutOfBoundsException(subLen);
    }
    // ako je početni indeks 0, vrati originalni string; inače, kreiraj i vrati novi string
    return (beginIndex == 0) ? this : new String(value, beginIndex, subLen);
}

Metod substring prvo proverava ispravnost argumenta; ako je argument neispravan, baca se izuzetak StringIndexOutOfBoundsException (o tome će biti detaljno reči kasnije). Zatim metod na osnovu argumenta izračunava dužinu podstringa. Ako je dužina podstringa manja od nule, takođe se baca izuzetak StringIndexOutOfBoundsException.

Ako je beginIndex jednak 0, to znači da je podstring isti kao i originalni string, pa se vraća originalni string. U suprotnom, koristi se deo niza value (niz karaktera originalnog stringa) da se kreira novi String objekat koji se zatim vraća.

Evo nekoliko primera upotrebe metoda substring:

①. Izdvajanje podstringa iz stringa:

String str = "Hello, world!";
String subStr = str.substring(7, 12); // izdvoji od 7. karaktera (uključujući) do 12. karaktera (isključujući)
System.out.println(subStr); // ispisuje "world"

②. Izdvajanje prefiksa ili sufiksa iz stringa:

String str = "Hello, world!";
String prefix = str.substring(0, 5); // izdvoji prvih 5 karaktera, odnosno "Hello"
String suffix = str.substring(7);    // izdvoji sve karaktere počevši od 7. karaktera, odnosno "world!"

③. Obrada razmaka i separatora u stringu:

String str = "   Hello,   world!  ";
String trimmed = str.trim();                 // ukloni razmake sa početka i kraja stringa
String[] words = trimmed.split("\\s+");      // podeli string po razmacima u niz reči
String firstWord = words[0].substring(0, 1); // izdvoji prvo slovo prve reči
System.out.println(firstWord);               // ispisuje "H"

④. Obrada brojeva i simbola u stringu:

String str = "1234-5678-9012-3456";
String[] parts = str.split("-");            // podeli string po crtici u četiri dela
String last4Digits = parts[3].substring(1); // izdvoji poslednje tri cifre poslednjeg dela
System.out.println(last4Digits);            // ispisuje "456"

Ukratko, metod substring omogućava fleksibilno izdvajanje podstringova prema potrebama i time znatno olakšava rad sa stringovima.

Metod indexOf klase String

Metod indexOf služi za pronalaženje pozicije prvog pojavljivanja podstringa u originalnom stringu i vraća indeks te pozicije. Pogledajmo izvorni kod ovog metoda:

/*
 * Pronalazi poziciju prvog pojavljivanja niza karaktera target u nizu karaktera source.
 * Parametri sourceOffset i sourceCount određuju opseg pretrage u nizu source,
 * parametri targetOffset i targetCount određuju opseg pretrage u nizu target,
 * dok parametar fromIndex određuje poziciju od koje počinje pretraga.
 * Ako je niz target pronađen, vraća se njegov indeks pozicije u nizu source (počevši od 0),
 * inače se vraća -1.
 */
static int indexOf(char[] source, int sourceOffset, int sourceCount,
        char[] target, int targetOffset, int targetCount,
        int fromIndex) {
    // ako je pozicija početka pretrage već van opsega niza source, vrati -1 (ako je niz target prazan, vrati sourceCount)
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    // ako je pozicija početka pretrage manja od 0, kreći od pozicije 0
    if (fromIndex < 0) {
        fromIndex = 0;
    }
    // ako je niz target prazan, vrati poziciju početka pretrage
    if (targetCount == 0) {
        return fromIndex;
    }

    // pronađi poziciju prvog karaktera niza target u nizu source
    char first = target[targetOffset];
    int max = sourceOffset + (sourceCount - targetCount);

    // u petlji traži poziciju niza target u nizu source
    for (int i = sourceOffset + fromIndex; i <= max; i++) {
        /* Look for first character. */
        // ako karakter na trenutnoj poziciji u nizu source nije prvi karakter niza target, nastavi da tražiš prvi karakter niza target u nizu source
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }

        /* Found first character, now look at the rest of v2 */
        // ako je prvi karakter niza target pronađen u nizu source, proveri da li se i ostatak niza target poklapa
        if (i <= max) {
            int j = i + 1;
            int end = j + targetCount - 1;
            for (int k = targetOffset + 1; j < end && source[j]
                    == target[k]; j++, k++);

            // ako se ceo niz target poklopio, vrati indeks pozicije u nizu source
            if (j == end) {
                /* Found whole string. */
                return i - sourceOffset;
            }
        }
    }
    // ako niz target nije pronađen, vrati -1
    return -1;
}

Pogledajmo primere.

①. Primer 1: pronalaženje pozicije podstringa

String str = "Hello, world!";
int index = str.indexOf("world"); // pronađi poziciju prvog pojavljivanja podstringa "world" u str
System.out.println(index);       // ispisuje 7

②. Primer 2: pronalaženje pozicije određenog karaktera u stringu

String str = "Hello, world!";
int index = str.indexOf(",");    // pronađi poziciju prvog pojavljivanja zareza u str
System.out.println(index);       // ispisuje 5

③. Primer 3: pronalaženje pozicije podstringa (počevši od zadate pozicije)

String str = "Hello, world!";
int index = str.indexOf("l", 3); // počevši od indeksa 3, pronađi poziciju prvog pojavljivanja podstringa "l" u str
System.out.println(index);       // ispisuje 3

④. Primer 4: pronalaženje više podstringova

String str = "Hello, world!";
int index1 = str.indexOf("o");   // pronađi poziciju prvog pojavljivanja podstringa "o" u str
int index2 = str.indexOf("o", 5); // počevši od indeksa 5, pronađi poziciju prvog pojavljivanja podstringa "o" u str
System.out.println(index1);      // ispisuje 4
System.out.println(index2);      // ispisuje 8

Ostali metodi klase String

①. Na primer, length() služi za vraćanje dužine stringa.

②. Na primer, isEmpty() služi za proveru da li je string prazan.

③. Na primer, charAt() služi za vraćanje karaktera na zadatom indeksu.

④. Na primer, valueOf() služi za pretvaranje drugih tipova podataka u string.

String str = String.valueOf(123); // pretvara ceo broj 123 u string

Iza metoda valueOf zapravo stoji poziv metoda toString odgovarajuće klase omotača — na primer, za pretvaranje celog broja u string poziva se metod toString klase Integer.

public static String valueOf(int i) {
    return Integer.toString(i);
}

A metod toString klase Integer zatim poziva statički metod klase Integer toString(int i):

public static String toString(int i) {
    // za minimalnu vrednost vrati "-2147483648"
    if (i == Integer.MIN_VALUE)
        return "-2147483648";
    // dužina celog broja; kod negativnog broja dužina je umanjena za 1
    int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
    // kopiraj ceo broj u niz karaktera
    char[] buf = new char[size];
    // konkretan proces kopiranja
    getChars(i, size, buf);
    // vrati string pomoću new
    return new String(buf, true);
}

Što se tiče metoda getChars, to je konkretan proces kopiranja celog broja u niz karaktera i nećemo ga ovde razrađivati.

⑥. Na primer, getBytes() služi za vraćanje niza bajtova stringa, pri čemu se može zadati način kodiranja, na primer:

String text = "Chenmo Wang Er";
System.out.println(Arrays.toString(text.getBytes(StandardCharsets.UTF_8)));

⑦. Na primer, trim() služi za uklanjanje praznih karaktera sa obe strane stringa. Pogledajmo izvorni kod:

public String trim() {
    int len = value.length;
    int st = 0;
    char[] val = value;   /* avoid getfield opcode */

    while ((st < len) && (val[st] <= ' ')) {
        st++;
    }
    while ((st < len) && (val[len - 1] <= ' ')) {
        len--;
    }
    return ((st > 0) || (len < value.length)) ? substring(st, len) : this;
}

Primer: " Chenmo Wang Er ".trim() vratiće „Chenmo Wang Er”.

⑧. Na primer, toCharArray() služi za pretvaranje stringa u niz karaktera.

String text = "Chenmo Wang Er";
char[] chars = text.toCharArray();
System.out.println(Arrays.toString(chars));

Pored toga, postoje i metodi poput split, equals, join i drugi, koje ćemo detaljno obraditi jednu po jednu kasnije.

Kratak pregled

Kada završiš sa ovim poglavljem, za vežbu možeš uzeti treći zadatak sa LeetCode-a „najduži podstring bez ponavljajućih karaktera”. Možeš ga rešiti grubom (brute-force) metodom, odnosno pomoću dve for petlje.

Naravno, ako baš ne uspeš da ga rešiš, rešenje sam ostavio u tehničkoj zajednici u okviru „Erdžeove zbirke zadataka sa LeetCode-a” — možeš pogledati tamo. Ovo je odlična vežba za rad sa stringovima i for petljama.

• Najduži podstring bez ponavljajućih karaktera

---