Colectii de obiecte Object

Infrastructura claselor colectie

O colectie este un obiect ce contine un numar oarecare, variabil de obiecte. Colectiile se folosesc pentru memorarea si regasirea unor date sau pentru transmiterea unui grup de date de la o metoda la alta. Colectiile Java sunt structuri de date generice, realizate fie cu elemente de tip Object, fie cu clase sablon (cu tipuri parametrizate) .

Infrastructura colectiilor (Collection Framework) ofera clase direct utilizabile si suport pentru definirea de noi clase (sub forma de clase abstracte), toate conforme cu anumite interfete ce reprezinta tipuri abstracte de date (liste, multimi, dictionare).

Un utilizator isi poate defini propriile clase colectie, care respecta aceste interfete impuse si sunt compatibile cu cele existente (pot fi inlocuite unele prin altele).

Clasele abstracte existente fac uz de iteratori si arata ca aproape toate metodele unei clase colectie pot fi scrise numai folosind obiecte iterator (cu exceptia metodelor de adaugare obiect la colectie si de calcul numar de elemente din colectie, care depind de structura fizica a colectiei).

Familia claselor colectie din Java este compusa din doua ierarhii de clase :

- Ierarhia care are la baza interfata Collection,

- Ierarhia care are la baza interfata Map.

O colectie, in sensul Java, este un tip de date abstract care reuneste un grup de obiecte de tip Object, numite si elemente ale colectiei. Un dictionar (o asociere ) este o colectie de perechi chei-valoare (ambele de tip Object); fiecare pereche trebuie sa aiba o cheie unica, deci nu pot fi doua perechi identice.

Interfata Collection contine metode aplicabile pentru orice colectie de obiecte. Nu toate aceste operatii trebuie implementate obligatoriu de clasele care implementeaza interfata Collection; o clasa care nu defineste o metoda optionala poate semnala o exceptie la incercarea de apelare a unei metode neimplementate.

Urmeaza descrierea completa a interfetei Collection :

public interface Collection

Din interfata Collection sunt derivate direct doua interfete pentru tipurile abstracte:

- Set pentru multimi de elemente distincte.

- List pentru secvente de elemente, in care fiecare element are un succesor si un predecesor si este localizabil prin pozitia sa in lista (un indice intreg).

Pentru fiecare din cele 3 structuri de date abstracte (lista, multime,dictionar) sunt prevazute cate doua clase concrete care implementeaza interfetele respective. Structurile de date concrete folosite pentru implementarea tipurilor de date abstracte sunt : vector extensibil, lista dublu inlantuita, tabel de dispersie si arbore binar.

Toate clasele colectie instantiabile redefinesc metoda "toString", care produce un sir cu toate elementele colectiei, separate prin virgule si incadrate de paranteze drepte. Afisarea continutului unei colectii se poate face printr-o singura instructiune.

De asemenea sunt prevazute metode de trecere de la vectori intrinseci de obiecte (Object [] ) la colectii de obiecte si invers: functia "Arrays.asList", cu un argument vector intrinsec de obiecte si rezultat de tip List si functia "toArray" din clasa AbstractCollection, de tip Object[]. Exemplu:

String sv[] = ;

List list = Arrays.asList(sv); // nu este nici ArrayList, nici LinkedList !

System.out.println (list); // System.out.println (list.toString());

String aux[] = (String[ ]) list.toArray(); // aux identic cu sv

O a treia ierarhie are la baza interfata Iterator, pentru metodele specifice oricarui iterator asociat unei colectii sau unui dictionar. Toate colectiile au iteratori dar nu si clasele dictionar (se poate insa itera pe multimea cheilor sau pe colectia de valori).

Clasa Collections contine metode statice pentru mai multi algoritmi 'generici' aplicabili oricarei colectii ('min', 'max') sau numai listelor ("sort", "binarySearch", "reverse", "shuffle"). Ei foloseau initial tipul generic Object si metodele polimorfice equals, compareTo s.a., dar acum folosesc tipuri parametrizate (din versiunea 5). Exemple in forma mai veche dar mai simpla:

public static Object min (Collection col ); // obiect minim din colectia col

public static Object min (Collection col , Comparator cmp);

public static void sort (List lst); // ordonare lista lst

public static void sort (List lst, Comparator cmp);

Multimi de obiecte

O multime este o colectie de elemente distincte pentru care operatia de cautare a unui obiect in multime este frecventa si trebuie sa aiba un timp cat mai scurt.

Interfata Set contine exact aceleasi metode ca si interfata Collection, dar implementarile acestei interfete asigura unicitatea elementelor unei multimi. Metoda de adaugare a unui obiect la o multime 'add' verifica daca nu exista deja un element identic, pentru a nu se introduce duplicate in multime. De aceea obiectele introduse in multime trebuie sa aiba metoda "equals" redefinita, pentru ca obiecte diferite sa nu apara ca fiind egale la compararea cu "equals".

Clasele multime predefinite si care implementeaza interfata Set sunt:

HashSet : pentru o multime neordonata realizata ca tabel de dispersie

TreeSet : pentru o multime ordonata, realizata ca arbore binar echilibrat automat ("Red-Black Tree").

Tabelul de dispersie asigura cel mai bun timp de cautare, iar arborele echilibrat permite pastrarea unei relatii de ordine intre elemente si un timp de cautare bun.

Exemplul urmator foloseste o multime de tipul HashSet pentru un graf reprezentat prin multimea arcelor (muchiilor) :

// graf reprezentat prin multimea arcelor

class Graph

public void addArc (int v,int w)

public boolean isArc (int v,int w)

public String toString ()

}

In general se recomanda programarea la nivel de interfata si nu la nivel de clasa concreta. Asadar, se vor folosi pe cat posibil variabile de tip Collection sau Set si nu variabile de tip HashSet sau TreeSet (numai la construirea obiectului colectie se specifica implementarea sa).

Operatiile cu doua colectii sunt utile mai ales pentru operatii cu multimi:

s1.containsAll (s2) // true daca s1 contine pe s1 (includere de multimi)

s1.addAll (s2) // reuniunea multimilor s1 si s2 (s1=s1+s2)

s1.retainAll (s2) // intersectia multimilor s1 si s2 (s1=s1*s2)

s1.removeAll (s2) // diferenta de multimi (s1= s1-s2)

Diferenta simetrica a doua multimi se poate obtine prin secventa urmatoare:

Set sdif = new HashSet(s1);

sdif.addAll(s2); // reuniune s1+s2

Set aux = new HashSet(s1);

aux.retainAll (s2); // intersectie s1*s2 in aux

simdif.removeAll(aux); // reuniune minus intersectie

Exemplul urmator arata cum putem folosi doua multimi pentru afisarea cuvintelor care apar de mai multe ori si celor care apar o singura data intr-un text. S-a folosit o multime ordonata, pentru a permite afisarea cuvintelor in ordine lexicografica.

public static void main (String arg[ ]) throws IOException

System.out.println ('multiple: '+ dupl); // afisare cuvinte repetate

Set unice = new TreeSet (toate);

unice.removeAll (dupl); // elimina cuvinte multiple

System.out.println ('unice: ' + unice); // afiseaza cuvinte cu o singura aparitie

}

Nici una din multimile HashSet sau TreeSet nu pastreaza ordinea de adaugare a elementelor la multime, dar clasa LinkedHashSet contine o metoda "toString" care produce un sir cu elementele multimii in ordinea adaugarii lor la multime, dar are aceleasi performante la cautare ca HashSet.

Interfata SortedSet,implementata de clasa TreeSet, extinde interfata Set cu cateva metode aplicabile numai pentru colectii ordonate:

Object first(), Object last(), // primul si ultimul element din multime

SortedSet subSet(Object from, Object to), // submultimea definita prin 2 valori

SortedSet headSet(Object to), // subSet (first(),to)

SortedSet tailSet (Object from) // subSet (from, last())

Liste secventiale

Interfata List contine cateva metode suplimentare fata de interfata Collection :

- Metode pentru acces pozitional, pe baza unui indice intreg care reprezinta pozitia :

get (index), set (index,object), add (index, object), remove (index)

- Metode pentru determinarea pozitiei unde se afla un element dat, deci cautarea primei si ultimei aparitii a unui obiect intr-o lista:

indexOf (object), lastIndexOf (object)

- Metode pentru crearea de iteratori specifici listelor:

listIterator (), listIterator (index)

- Metoda de extragere sublista dintr-o lista:

List subList(int from, int to);

Exista doua implementari pentru interfata List:

ArrayList lista vector, preferabila pentru acces aleator frecvent la elementele listei.

LinkedList lista dublu inlantuita, preferata cand sunt multe inserari sau stergeri de elemente in lista.

In plus, clasei Vector i-au fost adaugate noi metode pentru a o face compatibila cu interfata List. Noile metode au nume mai scurte si o alta ordine a argumentelor in metodele 'add' si 'set':

Forma veche (1.1) Forma noua (1.2)

Object elementAt (int) Object get(int)

Object setElementAt (Objext, int) Object set (i, Object)

void insertElementAt (Object, int) void add (i,Object)

Exemplu de functie care schimba intre ele valorile a doua elemente i si j:

static void swap (List a, int i, int j)

De observat ca metodele 'set' si 'remove' au ca rezultat vechiul obiect din lista, care a fost modificat sau eliminat. Metoda "set" se poate folosi numai pentru modificarea unor elemente existente in lista, nu si pentru adaugare de noi elemente.

Algoritmii de ordonare si de cautare binara sunt exemple de algoritmi care necesita accesul direct, prin indici, la elementele listei; de aceea metodele "sort" si "binarySearch" din clasa Collections au argument de tip List si nu Collection.

Urmeaza o varianta simplificata a metodei "binarySearch"; in caz de obiect negasit, rezultatul este pozitia unde ar trebui inserat obiectul cautat astfel ca lista sa ramana ordonata ( decalata cu 1 si cu minus).

public static int binSearch (List list, Object key)

return -(low + 1); // negasit

}

Exemplu de utilizare a functiei de cautare intr-o secventa care adauga un obiect la o lista ordonata, astfel ca lista sa ramana ordonata:

int pos = Collections.binarySearch (alist,key);

if (pos < 0) // daca key nu exista in lista

alist.add (-pos-1, key); // se adauga key inainte de primul element mai mare ca el

Accesul pozitional este un acces direct, rapid la vectori dar mai putin eficient in cazul listelor inlantuite. De aceea s-a definit o clasa abstracta AbstractSequentialList, care este extinsa de clasa LinkedList dar nu si de clasa ArrayList. Metoda statica Collections.binarySearch, cu parametru de tipul general List, recunoaste tipul de lista si face o cautare binara in vectori, dar o cautare secventiala in liste secventiale.

Clasa LinkedList contine, in plus fata de clasa abstracta AbstractList, urmatoarele metode, utile pentru cazuri particulare de liste (stive, cozi etc.): getFirst(), getLast(), removeFirst(), removeLast(), addFirst(Object), addLast(Object).

Din versiunea 5 au mai fost adaugate interfetele Queue si Deque cu cateva metode noi, interfete implementate de mai multe clase, printre care AbstractQueue, PriorityQueue, LinkedList, ArrayDeque

Interfata Queue extinde interfata Collection cu o metoda de adaugare "offer" care nu produce exceptie daca nu mai este loc in colectie si, mai important, cu metode de acces la primul element din colectie (din coada) cu si fara exceptie in caz ca nu exista ("element" si "peek" fara eliminare din coada, "poll" si "remove" cu eliminare din coada).

Interfata Deque extinde interfata Queue cu metode de acces si la primul si la ultimul element din lista: addFirst, removeFirst, getFirst, addLast, removeLast, getLast si variantele care nu produc exceptii: offer, poll, peek ( offerFirst, offerLast,.).

Cele mai multe clase de tip coada (ca BlockingQueue si SynchronousQueue) au fost introduse, alaturi de alte clase, in pachetul java.util.concurrent pentru programare cu fire de executie concurente.

Pentru aplicatiile cu structuri de date sunt interesante clasele ArrayDeque si PriorityQueue; clasa LinkedList implementeaza acum si interfata Deque si de aceea nu exista o clasa LinkedDeque.

Coada cu prioritati este implementata ca un vector "heap" extensibil (fara limite de capacitate). Indiferent de ordinea de adaugare la coada, elementul din fata (obtinut prin una din metodele "peek", "poll" sau "remove") este cel cu prioritatea minima. Prioritatea este determinata de catre metoda "compareTo" a obiectelor introduse in coada (constructor fara argumente) sau de catre metoda "compare" a obiectului comparator transmis ca argument la construirea unei cozi. In exemplul urmator se adauga si se scoate dintr-o coada de arce ordonata dupa costuri, in ipoteza ca metoda "compareTo" din clasa "Arc" compara costuri:

PriorityQueue<Arc> pq = new PriorityQueue<Arc>();

.

pq.add (new Arc(v,w,cost)); // adauga arc la coada pq

.

// afisare coada in ordinea prioritatilor (costului arcelor)

while ( ! pq.isEmpty())

System.out.println( pq.remove()); // scoate si sterge din coada

Clase dictionar

Interfata Map contine metode specifice operatiilor cu un dictionar de perechi cheie valoare, in care cheile sunt unice . Exista trei implementari pentru interfata Map:

HashMap dictionar realizat ca tabel de dispersie, cu cel mai bun timp de cautare.

TreeMap dictionar realizat ca arbore echilibrat, care garanteaza ordinea de enumerare.

LinkedHashMap tabel de dispersie cu mentinere ordine de introducere (din vers. 1.4)

Definitia simplificata a interfetei Map este urmatoarea:

public interface Map

Metoda "get" are ca rezultat valoarea asociata unei chei date sau null daca cheia data nu se afla in dictionar. Metoda "put" adauga sau modifica o pereche cheie-valoare si are ca rezultat valoarea asociata anterior cheii date (perechea exista deja in dictionar) sau null daca cheia perechii introduse este noua. Efectul metodei "put (k,v)" in cazul ca exista o pereche cu cheia "k" in dictionar este acela de inlocuire a valorii asociate cheii "k" prin noua valoare "v" (valoarea inlocuita este transmisa ca rezultat al metodei "put").

Testul de apartenenta a unei chei date la un dictionar se poate face fie direct prin metoda "containsKey", fie indirect prin verificarea rezultatului operatiei "get".

Clasele care genereaza obiecte memorate intr-un obiect HashMap sau HashSet trebuie sa redefineasca metodele 'equals' si 'hashCode', astfel incat sa se poata face cautarea la egalitate dupa codul de dispersie.

In exemplul urmator se afiseaza numarul de aparitii al fiecarui cuvant distinct dintr-un text, folosind un dictionar-arbore pentru afisarea cuvintelor in ordine.

class FrecApar

System.out.println (dic); // afisare dictionar

}

}

Cheile dintr-un dictionar pot fi extrase intr-o multime cu metoda "keySet", iar valorile din dictionar pot fi extrase intr-o colectie (o lista) cu metoda "values".Metoda "entrySet" produce o multime echivalenta de perechi 'cheie-valoare', unde clasa pereche are tipul Entry. Entry este o interfata inclusa in interfata Map si care are trei metode: "getKey", "getValue" si "setValue".

De observat ca metodele "entrySet","keySet" si "values" (definite in AbstractMap) creeaza doar imagini noi asupra unui dictionar si nu alte colectii de obiecte; orice modificare in dictionar se va reflecta automat in aceste "imagini", fara ca sa apelam din nou metodele respective. O imagine este creata printr-o clasa care defineste un iterator pe datele clasei dictionar si nu are propriile sale date. Metodele clasei imagine sunt definite apoi pe baza iteratorului, care da acces la datele din dictionar.

Diferenta dintre clasele HashMap si LinkedHashMap apare numai in sirul produs de metoda "toString" a clasei: la LinkedHashMap ordinea perechilor in acest sir este aceeasi cu ordinea de introducere a lor in dictionar, in timp ce la HashMap ordinea este aparent intamplatoare (ea depinde de capacitatea tabelei de dispersie, de functia "hashCode" si de ordinea de introducere a cheilor). Pentru pastrarea ordinii de adaugare se foloseste o lista inlantuita, iar tabelul de dispersie asigura un timp bun de regasire dupa cheie.

Colectii ordonate

Problema ordonarii este rezolvata diferit pentru liste fata de multimi si dictionare. Listele sunt implicit neordonate (se adauga numai la sfarsit de lista) si pot fi ordonate numai la cerere, prin apelul unei metode statice (Collections.sort). Multimile, ca si dictionarele, au o varianta de implementare (printr-un arbore binar ordonat) care asigura mentinerea lor in ordine dupa orice adaugare sau eliminare de obiecte.

Exemplu de ordonare a unei liste:

public static void main (String arg[ ]) ;

List lista = Arrays.asList (tab);

Collections.sort (lista);

System.out.println (lista); // [cinci,doi,patru,trei,unu]

}

Putem sa ne definim vectori sau liste ordonate automat, sau alte alte structuri compatibile cu interfata List si care asigura ordinea (un arbore binar, de exemplu).

Exemplu de incercare de a defini o clasa pentru o multime ordonata implementata printr-un vector (dupa modelul clasei TreeSet):

public class SortedArray extends ArrayList implements List

public SortedArray (Comparator comp)

public boolean add (Object obj)

}

Problema clasei anterioare este ca ar trebui redefinita si metoda "set" care modifica elemente din lista, pentru a mentine lista ordonata. Acest lucru nu este posibil prin folosirea metodei "Collections.sort" deoarece aceasta apeleaza metoda "set" si apare o recursivitate indirecta infinita de forma set -> sort -> set -> sort -> set ->.

O multime ordonata este de tipul TreeSet iar un dictionar ordonat este de tipul TreeMap. Se pot defini si alte tipuri de colectii sau dictionare ordonate, care implementeaza (optional) interfata SortedSet, respectiv interfata SortedMap. Adaugarea sau modificarea valorilor dintr-un arbore se face cu mentinerea ordinii si nu necesita reordonarea multimii sau dictionarului. Obiectele introduse intr-o colectie TreeSet sau TreeMap trebuie sa apartina unei clase care implementeaza interfata Comparable si contine o definitie pentru metoda "compareTo".

Exemplu de ordonare a unei liste de nume (distincte) prin crearea si afisarea unei multimi ordonate:

SortedSet lst = new TreeSet (lista); // sau se adauga cu metoda addAll

Iteratorul unei colectii ordonate parcurge elementele in ordinea dictata de obiectul comparator folosit mentinerea colectiei in ordine.

O problema comuna colectiilor ordonate este criteriul dupa care se face ordonarea, deci functia de comparatie, care depinde de tipul obiectelor comparate. Sunt prevazute doua solutii pentru aceasta problema, realizate ca doua interfete diferite si care au aplicabilitate distincta.

Anumite metode statice (sort, min, max s.a.) si unele metode din clase pentru multimi ordonate apeleaza in mod implicit metoda 'compareTo', parte a interfetei Comparable. Clasele JDK cu date (String, Integer, Date s.a.) implementeaza interfata Comparable si deci contin o metoda 'compareTo' pentru o ordonare 'naturala' ( exceptie face clasa Boolean, ale carei obiecte nu sunt comparabile).

Ordinea naturala este ordinea valorilor algebrice (cu semn) pentru toate clasele numerice, este ordinea numerica fara semn pentru caractere si este ordinea lexicografica pentru obiecte de tip String. Pentru alte clase, definite de utilizatori, trebuie implementata interfata Comparable prin definirea metodei 'compareTo', daca obiectele clasei pot fi comparate (si sortate).

Pentru ordonarea dupa un alt criteriu decat cel natural si pentru ordonarea dupa mai mlte criterii se va folosi o clasa compatibila cu interfata Comparator.

Rezultatul metodei 'compare' este acelasi cu al metodei 'compareTo', deci un numar negativ daca ob1<ob2, zero daca ob1==ob2 si un numar pozitiv daca ob1>ob2.

Un argument de tip Comparator apare in constructorii unor clase si in cateva metode din clasa Collections (sort, min, max) ce necesita compararea de obiecte.

Pentru a utiliza o functie "compare" trebuie definita o clasa care contine numai metoda 'compare', iar un obiect al acestei clase se transmite ca argument functiei. Exemplu de ordonare a dictionarului de cuvinte-frecventa creat anterior, in ordinea inversa a numarului de aparitii:

Set entset = dic.entrySet();

ArrayList entries = new ArrayList(entset);

Collections.sort (entries, new Comp());

. . .

// clasa comparator obiecte Integer in ordine inversa celei naturale

class Comp implements Comparator

}

Din versiunea 5 s-a introdus in clasa Collections si un comparator pentru ordinea inversa:

Comparator reverseOrder(Comparator cmp); // comparator pentru ordine inversa lui cmp

Clase iterator

Una din operatiile frecvente asupra colectiilor de date este enumerarea tuturor elementelor colectiei (sau a unei subcolectii) in vederea aplicarii unei prelucrari fiecarui element obtinut prin enumerare. Realizarea concreta a enumerarii depinde de tipul colectiei si foloseste un cursor care inainteaza de la un element la altul, intr-o anumita ordine (pentru colectii neliniare). Cursorul este un indice intreg in cazul unui vector sau un pointer (o referinta) pentru o lista inlantuita sau pentru un arbore binar. Pentru colectii mai complexe, cum ar fi vectori de liste, enumerarea poate folosi indici (pentru vectori) si pointeri (pentru noduri legate prin pointeri).

Generalizarea modului de enumerare a elementelor unei colectii pentru orice fel de colectie a condus la aparitia claselor cu rol de "iterator" fata de o alta clasa colectie. Orice clasa colectie Java 2 poate avea o clasa iterator asociata. Pentru un acelasi obiect colectie (de ex. un vector) pot exista mai multi iteratori, care progreseaza in mod diferit in cadrul colectiei, pentru ca fiecare obiect iterator are o variabila cursor proprie.

Toate clasele iterator rebuie sa includa urmatoarele operatii:

- Pozitionarea pe primul element din colectie

- Pozitionarea pe urmatorul element din colectie

- Obtinerea elementului curent din colectie

- Detectarea sfarsitului colectiei (test de terminare a enumerarii).

Interfata Iterator contine metode generale pentru orice iterator:

public interface Iterator

De observat ca modificarea continutului unei colectii se poate face fie prin metode ale clasei colectie, fie prin metoda "remove" a clasei iterator, dar nu ar trebui folosite simultan ambele moduri de modificare. In exemplul urmator apare o exceptie de tip ConcurrentModificationException:

ArrayList a = new ArrayList();

Iterator it = a.iterator();

while (it.hasNext())

Pentru fiecare clasa concreta de tip colectie exista o clasa iterator. Un obiect iterator este singura posibilitate de enumerare a elementelor unei multimi si o alternativa pentru adresarea prin indici a elementelor unei liste. Un dictionar nu poate avea un iterator, dar multimea perechilor si multimea cheilor din dictionar au iteratori.

Clasele iterator nu sunt direct instantiabile (nu au constructor public), iar obiectele iterator se obtin prin apelarea unei metode a clasei colectie (metoda "iterator"). In felul acesta, programatorul este obligat sa creeze intai obiectul colectie si numai dupa aceea obiectul iterator. Mai multi algoritmi generici realizati ca metode statice (in clasa Collections) sau ca metode ne-statice din clasele abstracte folosesc un obiect iterator pentru parcurgerea colectiei. Exemplu:

public static void sort (List list)

}

Fragmentul urmator din clasa AbstractCollection arata cum se pot implementa metodele unei clase colectie folosind un iterator pentru clasa respectiva:

public abstract class AbstractCollection implements Collection

public Object[] toArray()

public boolean containsAll(Collection c)

public boolean addAll (Collection c)

return modified;

}

. . . // alte metode

}

Interfata ListIterator contine metode pentru traversarea unei liste in ambele sensuri si pentru modificarea elementelor enumerate : hasNext(), next(), hasPrevious(), previous(), nextIndex(), previousIndex(), remove(), set (Object o), add(Object o).

Exemplu de parcurgere a unei liste de la coada la capat:

List a = new LinkedList();

for (ListIterator i= a.listIterator (a.size()); i.hasPrevious(); )

System.out.println (i.previous());

Metoda "listIterator()" pozitioneaza cursorul pe inceputul listei, iar metoda "listIterator(index)" pozitioneaza initial cursorul pe indicele specificat.

O clasa dictionar (Map) nu are un iterator asociat, dar este posibila extragerea unei multimi de chei sau unei multimi de perechi cheie-valoare dintr-un dictionar, iar aceste multimi pot fi enumerate.

Secventa urmatoare face o enumerare a perechilor cheie-valoare dintr-un dictionar "map", folosind interfata publica Entry, definita in interiorul interfetei Map:

for (Iterator it= map.entrySet().iterator(); it.hasNext();)

Definirea de noi clase colectie

Din versiunea 1.5 s-a introdus tipul de date definit prin enumerare (si cuvantul cheie enum), precum si doua colectii performante pentru elemente de un tip enumerat: EnumSet si EnumMap (implementate prin vectori de biti).

Biblioteca de clase Java mai contine si clase pentru crearea si prelucrarea de arbori multicai, in pachetul "javax.swing.tree": clasa instantiabila DefaultMutableTreeNode pentru un nod de arbore, clasa DefaultTreeModel pentru un (model de) arbore si interfete pentru alte eventuale implementari. Desi ele au fost create special pentru clasa JTree care asigura vizualizarea acestor arbori, cu facilitati de expandare/contractie noduri, selectie de noduri, s.a., pot fi folosite si separat de clasa JTree.

Definirea unor noi clase colectie poate fi necesara din mai multe motive:

- Cerinte de performanta (de memorie ocupata sau timp de acces) impun alte implementari pentru tipurile abstracte de date existente; de exemplu o multime de obiecte realizata ca vector sau ca lista simplu inlantuita.

- Sunt necesare alte tipuri abstracte de date neimplementate in SDK: graf, colectie de multimi disjuncte, arbore binar s.a.

Aceste noi clase colectie ar trebui sa se conformeze cadrului creat de interfetele Collection, Set, List, Map, Iterator s.a. si pot sa refoloseasca metode definite in clasele abstracte si in clasele instantiabile deja existente.

In Java, elementele unei colectii pot fi de orice tip derivat din Object, deci pot fi la randul lor colectii, ceea ce simplifica definirea si utilizarea colectiilor de colectii. Exemplul urmator este o clasa pentru grafuri memorate prin liste de adiacente. Se foloseste un vector de liste inlantuite:

public class Graph

public void addArc (int v,int w)

public boolean isArc (int v,int w)

public String toString ()

}

Clasa abstracta AbstractCollection, compatibila cu interfata Collection, contine implementari pentru o serie de operatii care pot fi realizate indiferent de tipul colectiei, folosind iteratori : isEmpty, contains, toArray, remove, containsAll, addAll, removeAll, retainAll, clear, toString.

Clasele AbstractSet si AbstractList extind clasa AbstractCollection, iar clasele instantiabile pentru multimi si liste extind aceste clase abstracte. Astfel se mostenesc toate functiile mentionate, desi unele din ele sunt redefinite din motive de performanta.

Prin extinderea claselor abstracte se pot defini noi clase colectie cu un efort de programare minim si cu pastrarea compatibilitatii cu interfetele comune (List, Set, Map). Exemplu de clasa pentru obiecte dictionar realizate ca vectori de perechi:

public class ArrayMap extends AbstractMap

public Object put ( Object key, Object value)

else

}

public Set entrySet ( )

public String toString( )

}

// multime-vector de obiecte

class ArraySet extends AbstractSet

public Iterator iterator ()

}

// clasa iterator (inclusa in clasa ArrayMap)

class ASIterator implements Iterator

public boolean hasNext()

public Object next()

public void remove ()

}

Clasa "Entry" implementeaza interfata "Map.Entry" si redefineste metoda "equals" (eventual si metoda "toString"):

class Entry implements Map.Entry

public Object getKey()

public Object getValue()

public Object setValue (Object v)

public boolean equals (Object obj)

public String toString()

}

Colectii virtuale

Vom folosi denumirea de colectie virtuala pentru ceea ce in literatura de limba engleza se numeste "view", adica o alta imagine (perspectiva) asupra unei colectii de date din memoria RAM sau de pe un suport extern. Prima utilizare a acestui termen a aparut in domeniul bazelor de date unde exista posibilitatea prezentarii datelor din mai multe tabele fizice sub forma unui nou tabel ( cu o parte din coloanele tabelelor fizice, posibil intr-o alta ordine), tabel care insa nu este creat efectiv pe disc ci este doar o imagine diferita a unor date existente prezentata utilizatorilor bazei de date pentru afisare sau pentru cautare (un tabel virtual, creat printr-o comanda SELECT).

In Java problema se pune in cazul metodelor "keySet" si "values" din clasele dictionar, care trebuie sa furnizeze o multime a cheilor si respectiv o colectie a valorilor din dictionar, dar fara sa creeze noi colectii si fara sa copieze referintele din dictionar in aceste noi colectii. Pe langa consumul inutil de memorie ar exista si problema mentinerii in concordanta a dictionarului cu cele doua colectii dupa orice modificare efectuata in dictionar (sau a refacerii colectiilor la fiecare nou apel).

Solutia acestei probleme se bazeaza pe ideea urmatoare: o noua colectie (multime) se poate defini prin extinderea unei clase abstracte cu definirea unei clase iterator, iar clasa iterator se poate defini prin parcurgerea multimii de perechi cheie-valoare ("entrySet") si extragerea campului dorit din fiecare pereche (fie cheia, fie valoarea). Asadar, se vor defini noi clase pentru multimea cheilor si colectia valorilor, dar aceste clase nu vor contine date, pentru ca metoda "next" a iteratorului clasei va furniza urmatoarea cheie sau valoare din dictionarul existent (intr-o ordine care depinde de tipul clasei dictionar). Implementarea acestei idei in clasa AbstractMap foloseste clase incluse anonime, dar aici vom folosi clase exterioare, pentru a facilita intelegerea ideii de colectie virtuala.

O alta observatie utila pentru intelegerea codului este aceea ca metodele "keySet" si "values" au rol de metode fabrica de obiecte ("Factory Methods") si nu vor produce cate un nou obiect la fiecare apel; o variabila a clasei AbstractMap retine o referinta la obiectul creat numai la primul apel, iar la un apel ulterior se verifica doar valoarea acestei variabile (initial valoarea null):

private transient Set keySet = null; // adresa obiectului creat la primul apel keySet

public Set keySet()

Clasa KSet implementeaza o multime virtuala a cheilor dintr-un dictionar, dictionar definit complet prin multimea perechilor cheie-valoare, multime generata de metoda "entrySet" (specifica fiecarui tip de dictionar):

class KSet extends AbstractSet

public Iterator iterator ()

public int size()

public boolean contains(Object k)

}

Metoda de adaugare la multime ("add") nu poate fi definita pentru multimea KSet dar nici nu este necesar (pentru ca nu este metoda abstracta in AbstractSet); multimea cheilor nu este modificata direct ci numai indirect, prin metode ale clasei dictionar ("put", in principal).

Clasa iterator parcurge multimea de perechi si extrage cheia din fiecare pereche:

class KIter implements Iterator

public boolean hasNext()

public Object next()

public void remove()

}

In mod similar se procedeaza la metoda "values" pentru a crea o colectie virtuala a valorilor din dictionar, prin iterare pe aceeasi multime de perechi "entrySet". Ideea este aplicabila si in alte situatii, cum ar fi obtinerea unei imagini inversate a unui dictionar, deci a unui dictionar virtual in care valorile (distincte intre ele) sunt folosite drept chei de cautare, iar cheile din dictionar apar ca valori.

Colectii arborescente

Bibliotecile de clase Java contin o singura clasa care poate fi utilizata ca arbore general, multicai, sub numele de DefaultMutableTreeNode in pachetul javax.swing.tree, folosita pentru pastrarea datelor care vor fi afisate intr-o componenta grafica JTree. Este o clasa cu multe metode si posibilitati de utilizare si in aplicatii fara interfata grafica.

Un arbore este complet definit prin nodul radacina, deci un obiect arbore este de fapt un obiect nod de arbore. Vom folosi in continuare un nume mai scurt pentru clasa DefaultMutableTreeNode astfel:

class TNode extends DefaultMutableTreeNode

public TNode (Object info)

}

Clasa nod de arbore foloseste o implementare in care fiecare nod contine un vector extensibil de referinte la nodurile fii (lista fiilor este un obiect de tip Vector), o referinta la nodul parinte si un obiect cu date (de tipul generic Object). Se pot defini si alte variante dar care ar trebui sa implementeze interfata MutableTreeNode pentru a fi folosite de un obiect JTree. O idee ar fi inlocuirea vectorului extensibil de succesori cu o lista inlantuita de succesori.

Dintre metodele publice mai des folosite mostenite de clasa TNode mentionam:

void add (TNode child); // adauga acestui nod fiul "child"

int getChildCount(); // numarul fiilor acestui nod

TNode getParent(); // parintele acestui nod

Enumeration children(); // fiii directi ai acestui nod

Object getUserObject(); // datele din acest nod

void remove (TNode child); // elimina fiul "child" din lista fiilor acestui nod

Enumeration preorderEnumeration(); // noduri din subarborele acestui nod, in adancime

Enumeration breadthFirstEnumeration(); // noduri din subarbore, parcurs in latime

Exemple de utilizare a unor obiecte de tip DefaultMutableTreeNode:

// clasa ptr un nod de arbore ( cu un nume mai scurt)

class TNode extends DefaultMutableTreeNode

public TNode (Object info)

}

// cauta in arborele cu radacina root nodul ce contine un obiect dat obj

public static TNode find (TNode root, Object obj)

return null;

}

Crearea unui arbore depinde de modul cum sunt furnizate datele ce vor fi introduse in arbore. Daca aceste date vin sub forma unor perechi parinte-fiu atunci fie utilizam metoda "find" de mai inainte pentru cautarea adresei nodului parinte, fie folosim un dictionar in care cheile sunt valori din noduri si au asociate adresele nodurilor in arbore (daca valorile din noduri sunt distincte). Exemplu:

private TNode buildTree()

p.add(c=new TNode(child)); // creare si adaugare nod fiu

h.put(child,c); // pune adresa nod fiu in dictionar

}

} catch (IOException ex)

return r;

}

Crearea unui arbore cu numele fisierelor dintr-un director dat si din subdirectoarele sale este un caz particular important de creare a unui arbore general:

// subclasa ptr arbori multicai de fisiere

class FTree extends DefaultMutableTreeNode

public FTree (String info)

public FTree (File dir)

// creare arbore cu fisierele dintr-un director d si din subdirectoarele sale

void dirtree ( FTree r, File d)

}

}

Se poate folosi si un constructor recursiv de nod, care construieste intreg arborele:

class FileNode extends DefaultMutableTreeNode

}

}

Exemplu de afisare in mod text, folosind metode ale clasei DefaultMutableTreeNode, cu indentare diferita la fiecare nivel din arbore:

public void print ()

static void printTree (FTree r, String ind)

Utilizarea inlantuita de metode nestatice cu rezultat (diferit de void) poate conduce la o sintaxa mai compacta si mai expresiva pentru construirea de colectii liniare sau arborescente (ierarhice). Ideea este ca functia de adaugare a unui nou nod la arbore (la o colectie in general) sa aiba ca rezultat nodul la care s-a facut adaugarea. Deoarece metoda "add" este de tip void in clasa de biblioteca, vom defini o subclasa cu metoda "add" redefinita:

class TNode extends DefaultMutableTreeNode

public TNode (Object info)

public TNode add (TNode kid)

}

Exemplu de creare arbore dupa modelul unui "builder" din limbajul Groovy:

private static TNode builder ()

8. Colectii generice

Clase generice in Java 5

Clasele colectie cu tipuri parametrizate au fost introduse in versiunea 1.5, ca solutii alternative pentru colectiile de obiecte Object. Aceste clase au fost numite generice ("generics") si nu clase "sablon" ("templates") pentru ca desi se definesc si se folosesc aproape la fel cu clasele sablon din C++ ele difera prin implementare: in C++ din clasa sablon se genereaza diverse clase prin substitutia parametrilor tip din clasa sablon, dar in Java exista o singura clasa generica (sursa si compilata) in care se inlocuiesc parametri formali cu parametrii efectivi, ca si la apelul de functii.

Exemple de declarare a unor vectori cu elemente de diferite tipuri :

ArrayList<Integer> a = new ArrayList<Integer>();

ArrayList<String> b = ArrayList<String> (100);

ArrayList<TNode> c = ArrayList<TNode> (n);

ArrayList<LinkedList<Integer>> graf; // initializata ulterior

Avantajele sunt acelea ca se poate verifica la compilare daca se introduc in colectie numai obiecte de tipul declarat pentru elementele colectiei, iar la extragerea din colectie nu mai este necesara o conversie de la tipul generic la tipul specific aplicatiei. Exemplu cu un vector de obiecte Integer:

ArrayList<Integer> list = new ArrayList<Integer>();

for (int i=1;i<10;i++)

list.add( new Integer(i) ); // nu se poate adauga alt tip decat Integer

int sum=0;

for (int i = 0; i< list.size();i++)

Exemplu de utilizare dictionar cu valori multiple pentru problema listei de referinte incrucisate - in ce linii dintr-un fisier text apare fiecare cuvant distinct :

public static void main (String[ ] arg) throws IOException

}

System.out.println (cref);

}

Trecerea de la un tip primitiv la tipul clasa corespunzator si invers se face automat in versiunea 1.5, procese numite "autoboxing" si "unboxing". Exemplu:

ArrayList<Integer> list = new ArrayList<Integer>();

for (int i=1;i<10;i++)

list.add(10*i); // trecere automata de la int la Integer

int sum=0; // suma valorilor din vector

for (Iterator i = list.iterator(); i.hasNext();)

sum += i.next(); // trecere automata de la Integer la int

Tot din versiunea 1.5 se poate utiliza o forma mai simpla pentru enumerarea elementelor unei colectii care implementeaza interfata Iterable. Exemplu:

for (Integer it : list) // it este iterator pe colectia list de obiecte Integer

sum += it; // sau sum += (int) it; sau sum += it.intValue();

Un alt exemplu, cu o lista de siruri :

LinkedList<String> list = new LinkedList<String>();

for (int x=1;x<9;x++)

list.add(x+'');

String sb='';

for (String s : list)

sb += s; // concatenare de siruri extrase din vector

In versiunea 1.5 toate interfetele si clasele colectie au fost redefinite pentru a permite specificarea tipului elementelor colectiei. Pentru exemplificare redam un fragment din clasa ArrayList, unde "E" este tipul neprecizat al elementelor colectiei :

public class ArrayList<E> extends AbstractList<E>

implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public boolean add(E o)

public boolean contains(Object elem)

. . .

}

Nu numai clasele pot avea parametri tip dar si metodele (numite metode generice). Exemplu:

// transforma un vector intr-o colectie (gresit)

static void arrayToCol (Object[] a, Collection<?> c)

// transforma un vector intr-o colectie (corect)

static <T> void arrayToCol (T[] a, Collection<T> c)

// utilizare (fara argumente efective de tip la apel)

String[] sa = new String[100];

Collection<String> cs = new LinkedList<String>();

arrayToCol (sa, cs); // T presupus a fi String

La utilizarea unui cod anterior versiunii Java 5 (cod fara generice) de catre programe Java cu generice pot aparea mesaje la compilare inevitabile (care pot fi suprimate numai prin adnotarea @SuppressWarning ). Exemplu:

class OldClass

}

class Generic2

}

Avertismente la compilare apar si la redefinirea unor metode din clasa Object in alte clase. Exemplu:

class MEntry<K,V> extends Object implements Map.Entry<K,V>

Functia urmatoare nu produce avertisment la compilare:

public boolean equals (Object obj)

Compilatorul Java poate verifica numai utilizarea corecta de tipuri statice, pe baza numelor de tip.

Forme posibile pentru parametri tip

O colectie Collection<Object> nu este un supertip al unei colectii Collection<T> desi Object este un supertip al lui T. Exemplu:

List<String> ls = new ArrayList<String>();

List<Object> lo = ls; // eroare la compilare !

Exemplul urmator de utilizare arata de ce nu este corecta atribuirea anterioara:

lo.add(new Object()); // adauga la lista lo

String s = ls.get(0); // incercare de atribuire a unui Object la un String

Exemplul urmator arata de ce se foloseste caracterul ? (wildcard) ca parametru de tip:

// functie naiva de afisare a unei colectii generice

static void printCol (Collection<Object> c)

// utilizare incorecta

HashSet<String> m = new HashSet<String> ();

printCol (m);

Functia 'printC' poate fi folosita numai cu colectii de Object si nu cu colectii de un subtip al lui Object. Urmeaza varianta corecta de definire a functiei de afisare a unei colectii generice:

// functie generica de afisare a oricarei colectii

static void printCol (Collection<?> c)

In concluzie Collection<?> este supertipul oricarei colectii de obiecte, iar caracterul '?' are sensul de 'tip necunoscut'. Declaratiile urmatoare nu sunt echivalente:

Collection<Object> Collection<?>

In linia 2 din exemplul urmator apare eroare la compilare:

Collection<?> c = new ArrayList<String>();

c.add(new Object()); // eroare !

Compilatorul nu stie daca 'Object' este un subtip al tipului necunoscut '?'.

Tipurile necunoscute pot fi limitate inferior sau superior (Bounded Wildcard) folosind sintaxa

<? extends T> pentru tipuri limitate inferior si <? super T> pentru tipuri limitate superior.

Fie functia urmatoare pentru calculul sumei numerelor dintr-o colectie:

static double sum (Collection<Number> c)

// utilizare incorecta

ArrayList<Long> a = new ArrayList<Long> ();

a.add(2L); a.add(3L);

System.out.println( (long)sum(a));

Daca argumentul functiei 'sum' ar fi '?' atunci nu am putea folosi metoda 'doubleValue' decat dupa conversie de la Object la Number:

static double sum (Collection<?> c)

Desi nu apar mesaje la compilare pot apare exceptii la executie, ca in exemplul urmator:

ArrayList<Date> d = new ArrayList<Date> ();

System.out.println(sum(a)); // exceptie la conversia din Date in Number

Solutia sigura pentru definirea functiei 'sum' este:

static double sum (Collection<? extends Number> c)

deci functia 'sum' poate opera cu o colectie de obiecte de orice subtip al lui Number (Byte, Short, Integer, Long, Float, Double). Se spune ca Number este limita superioara a tipului necunoscut '?'.

De observat ca urmatoarea functie se compileaza cu erori:

static void addLong (Collection<? extends Number> c, long x)

deoarece comilatorul nu poate verifica daca tipul necunoscut '?' este un supertip al tipului Long.

Tipurile limitate superior se folosesc in general pentru argumente de functii.

Exemplul urmator arata necesitatea unor tipuri necunoscute limitate inferior (? super T).

O colectie ordonata poate primi un comparator folosit la compararea elementelor din colectie:

class TreeSet<E>

}

// utilizare

class MyComp<String> implements Comparator<String>

TreeSet<String> a = new TreeSet<String> ( new MyComp<String>());

Pentru a permite utilizarea unui comparator mai general se va scrie:

class TreeSet<E> {

public TreeSet (Comparator<? super E>)

class MyComp<? super E> implements Comparator<? super E>

TreeSet<String> a = new TreeSet<String> ( new MyComp<Object>());

Tipurile limitate superior se folosesc in general pentru rezultatele functiilor.

Necesitatea unor limite multiple ("Multiple bounds") este ilustrata de urmatoarea posibila definire a functiei 'Collections.max' :

public static <T extends Comparable<T>> T max(Collection<T> coll)

Definitia este prea restrictiva deoarece permite numai compararea de obiecte de tip T intre ele. Exemplu de situatie care produce eroare la compilare desi nu ar trebui:

class A implements Comparable<Object>

Collection<A> a =

A am = Collections.max(a);

Eroarea provine din aceea ca tipul A nu implementeaza tipul <Comparable><A> si ar trebui ca tipul T sa fie comparabil cu orice supertip al lui T :

public static <T extends Comparable<? super T>> T max(Collection<T> coll)

Aceasta definire nu este compatibila cu definitia anterioara versiunii Java 5:

public static Object max (Collection coll);

Definitia urmatoare rezolva aceasta compatibilitate :

public static <T extends Object & Comparable<? super T>>

T max(Collection<T> coll)

Exemple comparative

Discutia anterioara arata ca este mai simplu sa folosim clase si metode generice existente decat sa definim clase generice noi aplicabile in diverse situatii si care sa nu produca erori la compilare.

Exemplele care urmeaza ilustreaza beneficiile claselor generice comparativ cu colectiile mai vechi, de variabile Object.

Primul exemplu creeaza arborele de codificare Huffman si genereaza coduri de lungimi diferite pentru cateva caractere cu frecvente de aparitie cunoscute. De remarcat cat de compact este codul sursa comparativ cu un program C pentru aceeasi problema. Codul Java poate fi facut si mai compact prin definirea clasei BT ca o subclasa a clasei de biblioteca DefaultMutableTreeNode.

import java.util.*;

// clasa pentru un caracter cu frecventa sa de aparitie

class FC

public boolean equals (Object obj)

public String toString()

public int getFreq ()

public char getChar()

}

// clasa pentru arbori binari de obiecte Object

class BT

// metode

public Object getValue ()

public BT getLeft ()

public BT getRight ()

public String toString()

public String toString(String sp)

public boolean equals (Object obj)

public boolean isLeaf ()

}

// comparator noduri de arbore dupa frecventa

class FComp implements Comparator

}

class A ;

int fa[]= ;

char s='1';

int n=ca.length; // n= numar de caractere

PriorityQueue pq = new PriorityQueue (20,new FComp());

for (int i=0;i<n;i++)

pq.add(new BT(new FC(ca[i],fa[i]),null,null));

BT t=null;

while ( pq.size()>1 )

t = (BT)pq.remove();

System.out.println (t.toString(''));

codif(t,'');

}

// parcurgere arbore si generare cod

static void codif (BT r, String cod)

}

Alte clase pentru colectii

In 2007 firma Google a publicat un pachet de clase colectie care vin sa completeze clasele Java de biblioteca. Dintre ele mentionam clase "MultiSet" pentru multimi cu valori multiple, "MultiMap" pentru dictionare cu chei multiple, "BiMap" pentru dictionare bidirectionale, in diverse variante de implementare, dar toate cu generice.

Colectiile Google folosesc intens delegarea ca metoda de reutilizare a unor clase existente, precum si alte tehnici de programare cu obiecte aplicabile si in alte situatii decat cea a claselor colectie.

O multime cu valori multiple este o colectie in care elementele nu sunt neaparat distincte, care nu permite accesul direct, prin indice (ca la liste), dar permite realizarea eficienta a unor operatii cum sunt obtinerea numarului de elemente cu o valoare data, eliminarea tuturor elementelor cu aceeasi valoare si compararea la egalitate a doua colectii cu elemente multiple. Interfata "MultiSet" este:

public interface Multiset<E> extends Collection<E>

}

Toate implementarile interfetei "MultiSet" se bazeaza pe un dictionar in care cheia este elementul din multime iar valoarea asociata cheii este numarul de repetari ale elementului respectiv. Astfel multimea de elemente se va memora sub forma dictionarului:

Clasa "AbstractMultiSet" este definita dupa exemplul clasei AbstractMap, adica are toate metodele definite in functie de multimea de perechi furnizata de metoda abstracta "entrySet":

public abstract class AbstractMultiset<E> extends AbstractCollection<E> implements Multiset<E>

return (int) Math.min(sum, Integer.MAX_VALUE);

}

// alte metode .

}

Clasa AbstractMapBasedMultiMap defineste metoda abstracta "entrySet" in functie de un dictionar primit de constructorul clasei si care poate avea orice implementare:

abstract class AbstractMapBasedMultiset<E> extends AbstractMultiset<E> implements Serializable

// entrySet creeaza obiect numai la primul apel

private transient volatile EntrySet entrySet;

@Override public Set<Multiset.Entry<E>> entrySet()

return entrySet;

}

// clasa inclusa

private class EntrySet extends AbstractSet<Multiset.Entry<E>>

public Multiset.Entry<E> next()

public int getCount()

}

return count;

}

};

}

public void remove()

};

}

@Override public int size()

@Override public void clear()

backingMap.clear();

size = 0L;

}

}

// alte metode mostenite si redefinite ptr eficienta

}

Clasele HashMultiSet, TreeMultiSet apeleaza la implementari existente pentru dictionarul folosit:

public final class TreeMultiset<E> extends AbstractMapBasedMultiset<E>

public TreeMultiset(Comparator<? super E> comparator)

// metode redefinite pentru multimi ordonate

@Override public SortedSet<E> elementSet()

@Override protected Set<E> createElementSet()

// clase incluse si alte metode .

}

Un dictionar cu valori multiple va respecta interfata "MultiMap" si poate extinde clasa abstracta "StandardMultiMap", care asociaza fiecarei chei o colectie de valori:

abstract class StandardMultimap<K, V> implements Multimap<K, V>, Serializable

abstract Collection<V> createCollection(); // definita in subclase

// colectia de valori asociata unei chei date (colectie virtuala)

public Collection<V> get(K key)

// daca exista o valoare data in multimap

public boolean containsValue( Object value)

return false;

}

// . alte metode si clase incluse

}

Interfata ListMultiMap asociaza fiecarei chei o lista de valori, iar metoda "get" are rezultat o lista:

public interface ListMultimap<K, V> extends Multimap<K, V>

Interfata "BiMap" este implementata de dictionare reversibile (bidirectionale), la care si valorile sunt distincte si pot fi deci folosite drept chei de cautare:

public interface BiMap<K, V> extends Map<K, V>

Clasa "StandardBiMap" primeste doua dictionare (nu neaparat diferite ca implementare) pe care le transmite unei clase "ForwardingMap", care deleaga implementarea unui dictionar (posibil acelasi si pentru dictionarul direct si pentru dictionarul invers):

class StandardBiMap<K, V> extends ForwardingMap<K, V> implements BiMap<K, V>

// constructor privat pentru dictionarul invers

private StandardBiMap(Map<K, V> backward, StandardBiMap<V, K> forward)

// alte metode si clase interne . . .

}

Clasa "StandardBiMap" nu este publica si deci nu este direct utilizabila, iar clasa "HashBiMap" este singura clasa Google predefinita pentru dictionare bidirectionale (neordonate!).