Link Cerca Menu Expand Document
jgregor5.gitlab.io

Col.leccions i mapes

Framework

El framework de col.leccions de Java permet emmagatzemar, obtenir, manipular i comunicar dades agregades. Conté els següents elements:

  • Interfícies: són tipus de dades abstractes que representen col·leccions. Les interfícies permeten manipular les col·leccions independentment dels detalls de la seva representació. En llenguatges orientats a objectes, les interfícies formen generalment una jerarquia.
  • Implementacions: Són les implementacions concretes de les interfícies de recollida. En essència, són estructures de dades reutilitzables.
  • Algorismes: Són els mètodes que realitzen càlculs útils, com cercar i ordenar, en objectes que implementen interfícies de col·lecció. Es diu que els algoritmes són polimorfs: és a dir, es pot utilitzar el mateix mètode en moltes implementacions diferents de la interfície de col·lecció adequada. En essència, els algoritmes són funcionalitats reutilitzables.

A continuació es poden veure les interfícies principals.

  • Collection : l’arrel de la jerarquia de col·leccions. Una col·lecció representa un grup d’objectes coneguts com els seus elements. La interfície de col·lecció és el denominador menys comú que totes les col·leccions implementen i s’utilitza per passar col·leccions i manipular-les quan es desitgi la màxima generalitat. Alguns tipus de col·leccions permeten duplicar elements, i d’altres no. Alguns estan ordenats i d’altres no ordenats. La plataforma Java no proporciona cap implementació directa d’aquesta interfície, però proporciona implementacions de subinterfícies més específiques, com ara Set and List.
  • Set : una col·lecció que no pot contenir elements duplicats. Aquesta interfície modela l’abstracció de conjunts matemàtics i s’utilitza per representar conjunts, com ara les cartes que contenen una mà de pòquer, els cursos que configuren el programa d’un estudiant o els processos que s’executen en una màquina. Té una versió ordenada, SortedSet (per valor ascendent).
  • List : una col·lecció ordenada (de vegades anomenada seqüència). Les llistes poden contenir elements duplicats. L’usuari d’una llista generalment té un control precís sobre on s’insereix cada element a la llista i pot accedir a elements mitjançant l’índex d’enters (posició). Si heu utilitzat Vector, coneixeu el sabor general de la llista. Consulteu també la secció La interfície de llista.
  • Queue : una col·lecció usada per contenir diversos elements abans del processament. A més de les operacions bàsiques de recollida, una cua proporciona operacions addicionals d’inserció, extracció i inspecció. Les cues normalment, però no necessàriament, ordenen elements de manera FIFO (first-in, first-out).
  • Deque : és una cua de doble final, i per tant permet inserir, extraure i inspeccionar elements als dos punts. Deques es pot utilitzar tant com FIFO (primer ingrés, primer sortida) com LIFO (darrera entrada, primer sortida).
  • Map : un objecte que assigna mapes de valors. Un mapa no pot contenir claus duplicades; cada tecla pot associar com a màxim un valor. Si heu utilitzat Hashtable, ja coneixeu els fonaments bàsics de Map. Consulteu també la secció La interfície del mapa. Té una versió ordenada, SortedMap (per clau ascendent).

Les col·leccions utilitzen el concepte de genèrics de Java. Bàsicament, permet definir el tipus de l’element de les col·leccions com un paràmetre. Per exemple, per a la collecció de tipus List, la definició a la documentació de Java és:

Interface List<E>

Això significa que List és una llista d’elements (E) de tipus parametritzable. Per tant, podem utilitzar List per qualsevol classe (no tipus primitiu).

Genèrics

Els genèrics permeten que els tipus (classes i interfícies) siguin paràmetres a l’hora de definir classes, interfícies i mètodes. Un cop que s’instancien, els paràmetres són substituïts pels tipus reals.

Beneficis:

  • Controls de tipus més forts a la compilació.

Un compilador Java aplica una verificació de tipus forta al codi genèric i emet errors si el codi viola la seguretat del tipus. La correcció d’errors en temps de compilació és més fàcil que arreglar errors d’execució, que poden ser difícils de trobar.

  • Eliminació de casts. El següent codi requereix tipus:
List list = new ArrayList();
list.add("hello");
String s = (String) list.get(0);

Quan es reescriu amb genèrics, no el requereix:

List<String> list = new ArrayList<String>();
list.add("hello");
String s = list.get(0);   // no cast
  • Permet als programadors implementar algoritmes genèrics.

Mitjançant l’ús de genèrics, els programadors poden implementar algoritmes genèrics que treballin en col·leccions de diferents tipus, es poden personalitzar i són de tipus segur i més fàcil de llegir.

Des de Java 7 podem estalviar-nos la definició del paràmetre de tipus del constructor, ja que Java l’infereix:

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

Mètodes genèrics

  • Totes les declaracions genèriques del mètode tenen una secció de paràmetre tipus delimitada per claudàtors d’angle () que precedeix el tipus de retorn del mètode ( en el següent exemple).
  • Cada secció de paràmetres de tipus conté un o més paràmetres de tipus separats per comes. Un paràmetre tipus, també conegut com a variable de tipus, és un identificador que especifica un nom de tipus genèric.
  • Els paràmetres de tipus es poden utilitzar per declarar el tipus de devolució i actuar com a marcadors per als tipus d’arguments passats al mètode genèric, que es coneixen com a arguments de tipus reals.
  • El cos d’un mètode genèric es declara com el de qualsevol altre mètode. Tingueu en compte que els paràmetres de tipus només poden representar tipus de referència, no tipus primitius (com int, double i char).
public <E> void printArray(E[] inputArray) {
    // Display array elements
    for (E element : inputArray) {
        System.out.printf("%s ", element);
    }
    System.out.println();        
}

Paràmetres de tipus delimitat

Hi pot haver moments en què voldreu restringir els tipus de tipus que es permeten passar a un tipus de paràmetre. Per exemple, un mètode que opera sobre números només pot voler acceptar instàncies de Number o de les seves subclasses.

Per declarar un paràmetre de tipus delimitat, enumereu el nom del paràmetre del tipus, seguit de la paraula clau extends, seguit tipus delimitant.

public <T extends Comparable<T>> T maximum(T x, T y, T z) {
    T max = x;   // assume x is initially the largest
    if (y.compareTo(max) > 0) {
        max = y;   // y is the largest so far
    }
    if (z.compareTo(max) > 0) {
        max = z;   // z is the largest now                 
    }
    return max;   // returns the largest object   
}

Es poden tenir múltiples tipus delimitats:

<T extends Type1 & Type2>

Classes genèriques

Una declaració de classe genèrica sembla una declaració de classe no genèrica, tret que el nom de classe sigui seguit per una secció de paràmetre tipus.

Com en els mètodes genèrics, la secció de paràmetres de tipus d’una classe genèrica pot tenir un o més paràmetres de tipus separats per comes. Aquestes classes es coneixen com a classes parametrizades o tipus parametrizats perquè accepten un o més paràmetres.

public class Box<T> {
    private T t;
    public void set(T t) {
        this.t = t;
    }
    public T get() {
        return t;
    }
}

Implementacions genèriques

Les interfícies genèriques es poden implementar bàsicament de dues formes: de forma genèrica o no, utilitzant un tipus específic.

Suposem que tenim la següent interfície genèrica:

interface Container<T> {		
    T getValue();
}

Una implementació genèrica manté el paràmetre genèric:

public class ContainerImpl<T> implements Container<T> {
    private T t;
    public ContainerImpl(T t) {
        this.t = t;
    }
    @Override
    public T getValue() {
        return t;
    }		
}

Una implementació no genèrica utilitza un tipus específic a la interfície:

public class LongContainerImpl implements Container<Long> {
    private Long l;
    public LongContainerImpl(Long l) {
        this.l = l;
    }
    @Override
    public Long getValue() {
        return l;
    }
}

Així es podrien utilitzar aquestes dues implementacions:

Container<String> strContainer = new ContainerImpl<>("test");
System.out.println(strContainer.getValue().toUpperCase());
		
Container<Long> longContainer = new LongContainerImpl(12L);
System.out.println(longContainer.getValue() * 2);

Comodins

El comodí (?) permet referir-se a un tipus desconegut. Habitualment s’utilitza com a tipus d’un paràmetre, camp o variable local. Tenim diferents tipus:

  • comodins delimitats per dalt: ? extends Foo. El paràmetre permet Foo o qualsevol subtipus de Foo. Utilitzat si és un paràmetre només d’entrada d’un mètode.
public static void process(List<? extends Foo> list) {
    for (Foo elem: list) {
        // ...
    }
}
  • comodins no delimitats: ?. El paràmetre permet qualsevol tipus.
  • comodins delimitats per baix: ? super Foo. Permet Foo o qualsevol supertipus de Foo. Utilitzat si és un paràmetre només de sortida d’un mètode.

Ús de col·leccions

Tota Collection és un Iterable, la qual cosa serveix per iterar qualsevol List, Set o Queue.

Per iterar tenim el mètode iterator():

Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
    Integer nextInt = iterator.next();
}

També es pot utilitzar el format for-each loop:

for (Integer nextInt: list) {
    // ...
}

Hi ha dos mètodes d’Object que utilitzem en relació a les col·leccions, i que sovint cal sobreescriure:

  • public int hashCode(): retorna un sencer diferent per a cada objecte. Si equals() retorna true, han de retornar el mateix sencer. S’utilitza per a inserir i cercar a col·leccions que utilitzen taules hash.
  • public boolean equals(Object obj): retorna true si els dos objectes es consideren iguals. Si es retorna true, cal que també hashCode() retorni el mateix sencer. Object té aquesta implementació per defecte: this == obj, que significa que són el mateix objecte. Però sovint volem retornar true encara que no es tracti del mateix objecte. Per exemple, Integer retorna true si els dos objectes contenen el mateix valor int.

Implementació típica de equals():

public boolean equals(Object o){
    if (o == null)
        return false;
    if (!(o instanceof Treballador))
        return false;
    Treballador altre = (Treballador) o;
    return this.treballadorId == altre.treballadorId;
}

Implementació típica de hashcode():

public int hashCode(){
    return (int) treballadorId;
}

Implementació alternativa de hashcode() utilitzant Objects:

public int hashCode(){
    return Objects.hash(treballadorId); // llista de camps de l'objecte
}

Altres mètodes Collection<E>:

  • boolean add(E e);
  • void clear();
  • boolean contains(Object o);
  • boolean isEmpty();
  • boolean remove(Object o);
  • int size()

El mètode contains() utilitza el mètode equals() per veure si existeix l’element. Per tant, depèn de la implementació de cada classe. En el cas de Integer, la documentació diu:

  • The result is true if and only if the argument is not null and is an Integer object that contains the same int value as this object.

Per tant, són iguals dos objectes Integer que contenen el mateix valor sencer. Object implementa el mètode equals() com la igualtat (this == o). Compte, perquè si es pretén sobreescriure el mètode equals(), sempre s’ha de sobreescriure també el mètode hashcode(). Veure Objects.hash().

List<E> afegeix operacions per posicions:

  • void add(int index, E element)
  • E get(int index)
  • E set(int index, E element)
  • E remove(int index)

La implementació més clàsica és la de ArrayList. LinkedList podria ser interessant si s’insereixen elements al començament amb freqüència.

Set<E> és una col·lecció que no conté repeticions. O sigui, no hi ha dos elements tals que e1.equals(e2). No conté mètodes addicionals respecte Collection.

Tenim tres implementacions:

  • HashSet utilitza el hashCode() de la clau per a optimitzar l’accés als elements.
  • TreeSet utilitza una estructura en arbre navegable segons l’ordre dels elements, que han de ser comparables (implementen la interfície Comparable). Es basa en TreeMap.
  • LinkedHashSet permet navegar els elements segons l’ordre d’inserció.

Queue<E> és una col·lecció amb el concepte associat de “cap” i “cua”: lloc per on es treuen i s’afegeixen els elements:

  • boolean add(E e): afegeix un element a la cua (amb excepció).
  • boolean offer(E e): afegeix un element a la cua.
  • E remove(): esborra l’últim element al cap (amb excepció).
  • E poll(): esborra l’últim element al cap.
  • E element(): examina l’‘últim element al cap (amb excepció).
  • E peek(): examina l’últim element al cap.

Com es veu, hi ha dos mètodes per cada operació (afegir, esborrar, examinar), una amb excepció i una altra sense.

Dues de les possibles implementacions:

  • LinkedList: la implementació més habitual.
  • PriorityQueue: permet que la cua estigui ordenada mitjançant un comparador, en lloc d’utilitzar l’ordre en que s’afegeixen els elements.

Deque<E> és una Collection i també una Queue<E>. Permet afegir i treure elements als dos costats de la col.lecció, ‘first’ i ‘last’. També permet implementar una pila (classe deprecada Stack) amb els mètodes:

  • void push(E e): afegeix un element a la pila (cap)
  • E pop(): treu un element de la pila (cap)
  • E peek(): examina l’element de la pila (cap)

LinkedList també implementa Deque.

Ús de mapes

Els mapes són estructures de dades dinàmiques que contenen correspondències entre parelles de clau i valor.

Map<K, V> té aquestes operacions principals:

  • int size()
  • boolean isEmpty()
  • boolean containsKey(Object)
  • V put(K, V)
  • V remove(Object)
  • void clear()
  • Set<K> keySet()
  • Collection<V> values()
  • Set<Entry<K, V>> entrySet()

El tipus Entry<K, V> és una parella clau/valor immutable amb els mètodes:

  • K getKey()
  • V getValue()

Les tres principals implementacions són:

  • HashMap utilitza el hashCode() de la clau per a optimitzar l’accés als elements.
  • TreeMap permet navegar els elements segons l’ordre natural d’aquests, que han de ser comparables (implementen la interfície Comparable).
  • LinkedHashMap: permet navegar els elements segons l’ordre d’inserció.

Comparació d’objectes

Comparables

Una classe és comparable si permet que les seves instàncies puguin ser comparades per poder ordenar-les entre sí. Totes les classes embolcall dels tipus primitius ho són (String, Integer, Double…). Les classes comparables implementen la interfície Comparable<T>.

La interfície té només un mètode:

int compareTo(T o)

El valor retornat pot ser:

  • negatiu, si aquest objecte és menor que o.
  • 0, si els dos són iguals.
  • positiu, si aquest objecte és major que o.

Les claus de la implementació TreeMap i els objectes d’un TreeSet han de ser comparables. Això permet poder navegar-los segons el seu ordre.

Comparadors

Els comparadors permeten comparar dos objectes d’un tipus T per poder ordenar-los. Són objectes que implementen la interfície Comparator<T>.

La interfície té només un mètode:

int compare(T o1, T o2)

El valor retornat pot ser:

  • negatiu, si o1 és menor que o2.
  • 0, si els dos són iguals.
  • positiu, si o1 és major que o2.

Alguns algorismes permeten utilitzar comparadors per ordenar col·leccions (veure la secció Algorismes). En general, és millor comparar fent la classe comparable, però si no podem o volem modificar el seu codi, podem crear un comparador.

Algorismes

La majoria d’algorismes operen en llistes (List), i alguns a Collection:

  • static <T extends Comparable<? super T>> void sort(List<T> list): ordena una llista d’elements comparables.
  • static <T> void sort(List<T> list, Comparator<? super T> c): ordena una llista d’elements, utilitzant un comparador.
  • static void shuffle(List<?> list): desordena una llista
  • Cinc algorismes més per manipular objectes d’una llista: reverse, fill, copy, swap i addAll
  • static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key): cerca binària a una llista
  • Sobre collections: frequency, disjoint, min i max

Stream API

Java té una API que permet processar seqüències d’objectes mitjançant operacions que es poden afegir a una canonada. Un Stream es genera a partir de col.leccions, arrays o canals d’E/S, i no és modificable: només podem canviar el resultat mitjançant les operacions de la canonada.

Tenim bàsicament dos tipus d’operacions: les intermèdies i les terminals.

  • Operacions intermèdies: permeten afegir operacions addicionals al darrere.
  • Operacions terminals: marquen el final del stream i retornen el resultat.

Les operacions s’encadenen en la canonada mitjançant crides successives que utilitzen expressions lambda. En el següent exemple, s’utilitza l’operació terminal forEach() amb una expressió lambda de tipus Consumer.

List<Integer> list = Arrays.asList(3, 2, 5, 4, 1);
Stream<Integer> stream = list.stream();

Consumer<Integer> consumer = (number) -> { System.out.println(number); };		
stream.forEach(consumer);

Operacions intermèdies:

  • map: permet aplicar una Function per a canviar el tipus del Stream de T a R

    <R> Stream<R> map(Function<? super T, ? extends R> mapper)

  • flatMap: permet aplicar una Function per a convertir cada T als continguts d’un stream de R

    <R> Stream<R> flatMap(Function<? super T,? extends Stream<? extends R>> mapper)

  • filter: permet modificar el stream filtrant els elements del Stream amb un Predicate

    Stream<T> filter​(Predicate<? super T> predicate)

  • sorted: permet ordenar els elements amb l’ordre natural (han de ser Comparable)

    Stream<T> sorted()

Operacions terminals:

  • collect: permet reduir els elements amb un Collector<T, A, R>: T és l’entrada, A l’acumulació i R el tipus resultat. Tenim collectors a la classe Collectors.

    <R,​A> R collect​(Collector<? super T,​A,​R> collector)

  • forEach: permet executar una acció per cada element.

    void forEach​(Consumer<? super T> action)

  • reduce: permet reduir els elements d’aquest stream utilitzant un BinaryOperator que permet fer T apply(T, T).

    Optional<T> reduce​(BinaryOperator<T> accumulator)

Exemples:

// crear llista de sencers
List<Integer> number = Arrays.asList(2, 3, 4, 5);

// map
List<Integer> square = number.stream()
    .map(x -> x * x)
    .collect(Collectors.toList());
System.out.println(square);

// flatMap
List<Integer> square2 = number.stream()
    .flatMap(x -> Stream.of(x, x*2))
    .collect(Collectors.toList());
System.out.println(square2);

// crear llista de strings
List<String> names = Arrays.asList("Reflection", "Collection", "Stream");

// filter
List<String> result = names.stream()
    .filter(s -> s.startsWith("S"))
    .collect(Collectors.toList());
System.out.println(result);

// sorted
List<String> show = names.stream()
    .sorted()
    .collect(Collectors.toList());
System.out.println(show);

// crear llista de sencers
List<Integer> numbers = Arrays.asList(2, 3, 4, 5, 2);

// collect retorna un Set
Set<Integer> squareSet = numbers.stream()
    .map(x -> x * x)
    .collect(Collectors.toSet());
System.out.println(squareSet);

// forEach
number.stream()
    .map(x -> x * x)
    .forEach(y -> System.out.println(y));

// reduce
int even = number.stream()
    .filter(x -> x % 2 == 0)
    .reduce(0, (ans, i) -> ans + i);
System.out.println(even);

Expressions regulars

Les expressions regulars ens permeten trobar patrons dins de cadenes de text. Podem utilitzar-les per validar dades, fer cerques i substituir-les. Estan implantades a molts gestors de bases de dades.

A Java, tenim un mètode de Pattern que permet comprovar si una cadena compleix un patró, retornant true en cas positiu. L’ús més general es fa utilitzant les classes Pattern i Matcher.

// regex: 0 a N lletres a i una b
boolean b = Pattern.matches("a*b", "aaaaab");
// alternativament:
Pattern p = Pattern.compile("a*b");
Matcher m = p.matcher("aaaaab");
boolean b = m.matches();

El funcionament de les expressions regulars a Java s’explica a la documentació de la classe Pattern.

Una de les funcionalitats més interessants de les expressions regulars és la captura de grups. A la secció d’una expressió podem afegir parèntesi, i això voldrà dir que volem obtenir aquell grup de forma individual.

Pattern p = Pattern.compile("(a*)(b*)c");
Matcher m = p.matcher("aaabbc");
boolean b = m.matches(); // true
String group1 = m.group(1); // aaa
String group2 = m.group(2); // bb

Referències