Sortowane kolekcje w Javie

W Javie mamy do dyspozycji całkiem sporo różnych implementacji kolekcji, których można użyć w zależności od potrzeb. Mamy też oczywiście kolekcje, które zachowują określony porządek, są to TreeSetTreeMap.

Obie kolekcje implementują odpowiednio interfejsy NavigableSet NavigableMap, które to z kolei rozszerzają interfejsy SortedSet SortedMap. Jak już pewnie wiecie, małe przypomnienie – zbiory implementują interfejs Collection, natomiast mapy już nie. Przekłada się to m.in. na różne metody służące do dodowania elementów (add() oraz put()). Wiedza ta przydaje się np. w rozmowach o pracę.

TreeMap, czyli posortowana mapa.

Zacznijmy od przyjrzenia się implementacji TreeMap, a konkretnie tego co najbardziej wyróżnia kolekcje sortowane. Otóż przechowują one obiekty zgodnie z naturalnym porządkiem lub zgodnie z konkretnym komparatorem (dlatego istotna jest poprawna implementacja metody compareTo()). Przyjrzyjmy się szczególnie put() odpowiedzialnej za dodawania elementów do mapy.

private V put(K key, V value, boolean replaceOld) {
    Entry<K,V> t = root;
    if (t == null) {
        addEntryToEmptyMap(key, value);
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else {
                V oldValue = t.value;
                if (replaceOld || oldValue == null) {
                    t.value = value;
                }
                return oldValue;
            }
        } while (t != null);
    } else {
        Objects.requireNonNull(key);
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else {
                V oldValue = t.value;
                if (replaceOld || oldValue == null) {
                    t.value = value;
                }
                return oldValue;
            }
        } while (t != null);
    }
    addEntry(key, value, parent, cmp < 0);
    return null;
}

Na samym początku widzicie, że mamy określony korzeń (ang. root). Korzeń niewątpliwie związany jest z drzewami binarnymi. I to odpowiedź na pytanie dlaczego sortowane kolekcje nazywane są TreeMap TreeSet, po prostu przechowują one elementy w drzewie. Temat drzew binarnych można przyswoić sobie np. na Wikipedii: https://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwań. W drzewie, począwszy od korzenia, wartości przechowywane są po lewej stronie, gdy są mniejsze od wartości korzenia, a po prawej gdy są większe od wartości korzenia. Mniej więcej w ten sposób.

                          20
                        /    \
                     12        33
                   /    \         \
                 9        19        38
               /   \    /    \    /    \  
             NIL   NIL NIL   NIL NIL    NIL

W implementacji mapy TreeMap mamy do czynienia konkretnie z drzewem czerwono-czarnym, w którym dodatkowo każdy węzeł (ang. node) ma określony kolor. Przykładowo korzeń i każdy liść (ang. leaf) musi być czarny. Liść to po prostu null, nie przechowujący już żadnej wartości. W ten sposób przechowujące elementy kolekcji wyszukiwanie jest odpowiednio szybkie, o czym za chwilę. Natomiast teraz wróćmy do przytoczonego kodu. Jak widzicie rodzic jest początkowo korzeniem, w miarę wykonywania się pętli do while w zależności od działań komparatora otrzymujemy przechodzimy albo do lewej albo do prawej części drzewa. Implementacja mapy nie pozwala na przechowywanie dwóch takich samym kluczy, więc ewentualnie mogą być one zamienione. Gdy w końcu znajdziemy rodzica, do którego możemy dodać naszą parę klucz-wartość (czyli węzeł kończący się liściem, a więc jest nullem) dodajemy ją.

Entry<K,V> t = root;
...
do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else {
                V oldValue = t.value;
                if (replaceOld || oldValue == null) {
                    t.value = value;
                }
                return oldValue;
            }
        } while (t != null);
...
addEntry(key, value, parent, cmp < 0);

O tym, że kolory rzeczywiście występują możecie przekonać się przeglądając metodę addEntry() w klasie TreeMap. Odnosi się ona do fixAfterInsertion(), która to wygląda tak:

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}

Metoda ta odpowiada za odpowiednie ułożenie elementów w drzewie zgodnie z zasadami drzewa czerwono-czarnego. Czyli synowie czerwonego rodzica nie mogą być czerwoni, a jak widać na końcu korzeń musi zostać czarny.

TreeSet a TreeMap – to prawie to samo

Skoro mamy omówioną mapę, to co z tym zbiorem? Otóż przeglądając klasę TreeSet łatwo zauważymy, że zbiory to tak naprawdę mapy, w których elementy przechowywane są jako klucze. Oto fragment implementacji metody add(), w której zaszyta jest metoda put() z pustym obiektem jako wartością. Spróbujcie sobie stworzyć jakiś TreeSet, dodać jakiś element i zrobić breakpoint w metodzie put() klasy TreeMap. Zobaczycie, że debuger trafi właśnie tam.

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

...

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
...
}

Działanie sortowanych kolekcji w Javie

Przeanalizujmy działanie na konkretnym przykładzie.

Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(1, "one"); // Step 1
treeMap.put(2, "two");
treeMap.put(3, "three");
treeMap.put(4, "four");
treeMap.put(5, "five");

I oto kolejność ułożenia węzłów w drzewie czerwono-czarnym przy wywołaniu powyższego kodu:

Krok 1: klucz 1 zostaje dodany do do mapy i jest jednocześnie korzeniem.

Krok 2: klucz 2 zostaje dodany do mapy po prawej stronie od korzenia. Przybiera kolor czerwony.

                      1
                        \
                          2

Krok 3: klucz 3 zostaje dodany do mapy jako lewe dziecko 2, jednak każdy nowy element zostaje dodany jako czerwony, a dzieci czerwonego rodzica muszą być czarne. Musi nastąpić więc przywrócenie właściwości czerwono-czarnych i odpowiednia rotacja w lewo. Tym samym 2 (rodzic) staje się czarny, 1 zostaje czerwona i staje się lewym dzieckiem czarnej 2, a czerwona 3 wciąż zostaje prawym dzieckiem 2.

                      2
                    /   \
                  1       3

Krok 4: zostaje dodany klucz 4 jako prawe czerwone dziecko 3. Jednak czerwony rodzic nie może mieć czerwonych dzieci i tu występuje element stryja (drugie dziecko rodzica rodzica wstawianego elementu, czyli tu 1), który jest czerwony nie wykonujemy rotacji, a jedynie zmiany kolorów. I tak kolor elementów 1 i 3 zmieniamy na czarny, a elementowi 2 zmienilibyśmy kolor na czerwony jednak węzeł musi zostać czarny.

                      2
                    /   \
                  1       3
                            \
                             4

Krok 5: dodajemy klucz 5 jako czerwony. Znów mamy czerwonego rodzica (stryj nie jest czerwony, bo nie ma go w ogóle), więc wykonujemy rotację w lewo by przywrócić założenia czerwono-czarne.

                      2
                    /   \
                  1       4
                        /   \
                       3     5

I tak dalej, zgodnie z zasadami czerwono-czarnymi. Jak widać, umieszczenie elementu w mapie jest bardziej złożone niż w takich strukturach, gdzie następuje dodanie elementu na końcu listy jak w ArrayList. Mamy jednak ważną zaletę jaką jest przechowanie elementów w odpowiedniej kolejności przez co otrzymujemy w miarę szybki dostęp do elementu. Metody get() będą również korzystać z wyniku porównania (compareTo()) i jeżeli szukamy elementu z kluczem 1 to porównanie do korzenia od razu wskaże na lewą stronę i już w drugiej iteracji pętli znajdujemy szukany element.

Powyższe właściwości wskazują na złożoność obliczeniową operacji put()get(). Jak widzicie są one bardzo podobne i wymagają wykonywania tych samych operacji wychodząc od korzenia. Dzięki temu dla obu operacji mamy złożoność logarytmiczną, czyli w notacji dużego „O” będzie to zapis O(log n). Jest to więc bardzo dobry rezultat, zwłaszcza dla ogromnych zbiorów.

Sortowane kolekcje w Javie

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

Przewiń do góry