Framework de Coleções Java PDF

Tipos de Coleções da JCF A JCF oferece-nos essencialmente 4 formas de colecionar elementos: conjuntos (coleções que implementam a interface Set); listas (coleções que implementam a interface List); filas (coleções que implementam a interface Queue); d...

Tipos de Coleções da JCF A JCF oferece-nos essencialmente 4 formas de colecionar elementos: conjuntos (coleções que implementam a interface Set); listas (coleções que implementam a interface List); filas (coleções que implementam a interface Queue); dicionários (coleções que implementam a interface Map); Framework de Coleções do Java 16 Algoritmos e Estrutura de Dados Conjuntos (Set) Um set é uma coleção de elementos que se comporta como um conjunto e que, por isso, apresenta as suas principais características: não permite elementos duplicados; Só algumas das suas implementações (classes concretas que implementam o Set) são ordenadas; os seus elementos não são referenciados por índices, como nos arrays; Algumas classes concretas que implementam a interface Set: HashSet – é uma coleção desordenada; LinkedHashSet – é uma coleção ordenada por ordem de inserção; TreeSet – é uma coleção que mantém os elementos ordenados pelo seu valor. Framework de Coleções do Java 17 Algoritmos e Estrutura de Dados Listas (List) Uma lista é uma coleção que se comporta como uma sequência de elementos e que, por isso, apresenta as seguintes características: permite elementos duplicados todas as implementações (classes concretas que implementam a List) são ordenados pela ordem de inserção (quando iteradas, os seus elementos são percorridos pela ordem de inserção); os seus elementos podem ser acedidos por indexação, tal como nos arrays assumindo o índice necessariamente valores entre 0 e size()-1; e possibilitando que qualquer coleção do tipo lista possa ser percorrida através de iteração mas também usando indexação. Algumas classes concretas que implementam a interface List: ArrayList – pode ser vista como um array dinâmico; Vector – idêntica à ArrayList mas mais lenta, uma vez que os seus métodos são sincronizados (esta coleção só deve ser usada se for necessária a implementação segura de threads em contexto de programação concorrente); Stack – é uma coleção que assegura o comportamento last-in first-out, típico de uma pilha (descontinuada). LinkedList – baseada numa lista duplamente ligada e com métodos adicionais de inserção e remoção no início e no fim da lista; Framework de Coleções do Java 18 Algoritmos e Estrutura de Dados Métodos extra duma Lista void add(int i, E obj) adiciona um elemento à lista na posição i, deslocando para a frente todos os elementos que já existirem a partir dessa posição E set(int i, E obj) substitui o elemento da posição i pelo novo elemento, devolvendo o elemento original E remove(int i) remove o elemento da posição i, devolvendo-o E get(int i) retorna, sem remover, o elemento da posição i int indexOf(E obj) devolve a posição da primeira ocorrência do elemento, ou -1 caso esse elemento não exista int lastIndexOf(E obj) devolve a posição da última ocorrência do elemento, ou -1 caso esse elemento não exista ListIterator listIterator() devolve um ‘iterador de listas’ que referencia o primeiro elemento da coleção ListIterator devolve um ‘iterador de listas’ que referencia o listIterator(int i) elemento da posição i Framework de Coleções do Java 19 Algoritmos e Estrutura de Dados Iterador para listas A interface ListIterator deriva da interface Iterator, à qual acrescenta métodos que permitem a travessia bidirecional , a consulta dos índices e a modificação dos elementos. public interface ListIterator extends Iterator { //boolean hasNext(); //E next(); //void remove(); boolean hasPrevious(); //devolve true se houver elemento predecessor E previous(); //devolve o elemento predecessor int nextIndex(); //devolve a posição do próximo elemento int previousIndex(); //devolve a posição do elemento predecessor void set(E obj); //substitui o último elemento devolvido por next() void add(E obj); //o elemento é inserido imediatamente antes do elemento que seria devolvido por next() e imediatamente depois do elemento que seria devolvido pelo previous() } Framework de Coleções do Java 20 Algoritmos e Estrutura de Dados Filas (Queue) Uma Fila, tal como uma Lista, é também uma sequência de elementos, mas com algumas funcionalidades adicionais destinadas a assegurar que o processamento dos seus elementos se faça pela ordem com que foram adicionados: tipicamente, implementam o comportamento first-in first-out, próprio de uma fila de espera, mas na JCF acabam também por permitir um comportamento um pouco mais geral (inserção e remoção pelos extremos) os seus elementos não são referenciados por índices, como nas Listas; Algumas classes concretas que implementam a interface Queue: PriorityQueue – fila prioritária com os seus elementos ordenados por ordem crescente dos seus valores, de forma a garantir que à cabeça esteja sempre o de menor ordem (o mais prioritário); ArrayDeque – coleção baseada num “array dinâmico”, que se pode comportar quer como Queue quer como Stack; LinkedList – coleção baseada numa lista duplamente ligada que, à semelhança do ArrayDeque, permite implementar o comportamento quer de uma Queue quer de uma Stack. Framework de Coleções do Java 21 Algoritmos e Estrutura de Dados Principais métodos duma Queue Numa Queue da JCF, cada uma das operações de inserção, remoção e consulta é assegurada por dois métodos distintos alternativos: num é lançada uma exceção sempre que a operação falhe; no outro é devolvido um valor especial (null ou false). boolean add(E obj) adiciona um elemento no fim da fila; devolve true se o elemento for inserido e lança uma exceção caso contrário boolean offer(E obj) adiciona um elemento no fim da fila; devolve true se o elemento for inserido e false caso contrário E remove() remove e devolve o elemento à cabeça da fila; lança uma exceção caso a fila esteja vazia E poll() remove e devolve o elemento à cabeça da fila; devolve null caso a fila esteja vazia E element() devolve, sem remover, o elemento à cabeça da fila; lança uma exceção caso a fila esteja vazia E peek() devolve, sem remover, o elemento à cabeça da fila; devolve null caso a fila esteja vazia Framework de Coleções do Java 22 Algoritmos e Estrutura de Dados Filas com dupla terminação (deque – double ended queue) Uma Deque estende (deriva de) a interface Queue e, como tal, estabelece o comportamento de coleções que tipicamente se destinam a manter elementos para que posteriormente sejam processamento por uma determinada ordem, mas fornece métodos adicionais que permitem que as operações de inserção, remoção e consulta passem a poder realizar-se por ambos os extremos da fila – daí a designação deque (double ended queue). Assim, uma deque tanto pode assegurar um comportamento FIFO (first-in, first out), próprio de uma queue, como um comportamento LIFO (last-in, first out), típico de uma stack, que é o que acontece com as duas coleções LinkedList e ArrayDeque – ambas podem funcionar como stacks ou como queues. Tal como numa queue, as operações de acesso numa deque são asseguradas por dois tipos de métodos: os que lançam uma exceção em caso de falha e os que retornam um valor especial. pelo início pelo fim Queue lança exceção retorna val. lança exceção retorna val. especial especial inserir addFirst(e) offerFirst(e) addLast(e) offerLast(e) Deque remover removeFirst() pollFirst() removeLast() pollLast() consultar getFirst() peekFirst() getLast() peekLast() LinkedList ArrayDeque Framework de Coleções do Java 23 Algoritmos e Estrutura de Dados Métodos da Deque para os comportamentos FIFO e FILO Quando uma deque é usada como uma queue, os método da método Deque elementos são adicionados no fim e retirados Queue equivalente pelo início da coleção. add(e) addLast(e) A interface Deque fornece uma conjunto de offer(e) offerLast(e) métodos perfeitamente equivalentes aos herdados da interface Queue remove() removeFirst() poll() pollFirst() element() getFirst() peek() peekFirst() Quando uma deque é usada como uma stack, os método da método Deque elementos são inseridos e retirados pelo início da Stack equivalente coleção. push(e) addFirst(e) A interface Deque fornece uma conjunto de métodos equivalentes aos da coleção Stack. pop(e) removeFirst() Deve-se evitar usar a classe Stack. peek() peekFirst() Framework de Coleções do Java 24 Algoritmos e Estrutura de Dados A polivalência da coleção LinkedList A classe LinkedList representa uma coleção polivalente, uma vez que, implementando quer a interface List, quer a interface Deque, pode comportar- se como list (métodos da interface List); queue (métodos da interface Deque que asseguram o comportamento FIFO); stack (métodos da interface Deque que asseguram o comportamento LIFO); List Queue Deque LinkedList Framework de Coleções do Java 25 Algoritmos e Estrutura de Dados Dicionários (Map) Os Dicionários representam uma forma diferente de colecionar elementos por vezes também conhecidos por: maps, correspondências, coleções de pares ou coleções associativas. implementam a interface Map, mas não implementam a interface Collection, ainda que façam também parte da JCF. Em informática (e não só) é frequente identificar-se cada elemento de informação por um código único (habitualmente designado por chave) é o que acontece, por exemplo, com as fichas de alunos, em que cada uma delas é identificada pelo número mecanográfico do aluno em causa; Esta nova família de coleções, os Dicionários, tem como principal característica assegurar precisamente a correspondência entre os elementos de informação e os respetivos códigos de identificação para isso, colecionam pares formados pela chave e pelo elemento de informação em si; daí estas coleções admitirem dois parâmetros tipo, K (Key) e V (Value), para o tipo de chave e para o tipo de valor (elemento) a colecionar, respetivamente; disponibilizam métodos que asseguram, entre outras operações, o acesso aos valores colecionados por indicação dos seus atributos chave. Os Dicionários são então coleções que implementam a interface Map, guardam correspondências entre chaves do tipo K e valores de tipo V, e não permitem chaves duplicadas. Framework de Coleções do Java 26 Algoritmos e Estrutura de Dados Classes que implementam a interface Map HashMap coleção baseada numa tabela de hash os seus elementos são armazenados de forma desordenada; LinkedHashMap coleção implementada com uma tabela de hash e uma lista duplamente ligada que serve para preservar a ordem de inserção; numa iteração, os seus elementos são acessíveis pela ordem de inserção; TreeMap coleção baseada numa árvore binária de pesquisa; os seus elementos são ordenados pelo valor das chaves, logo, neste tipo de coleção é a classe representada por K (tipo de chave) que tem de ser comparável, ou então existir um comparador que saiba comparar dois quaisquer elementos do tipo K. Framework de Coleções do Java 27 Algoritmos e Estrutura de Dados Métodos dum dicionário (declarados na interface Map) adiciona um par chave/valor, sobrepondo o eventual V put(K key, V value) valor que já exista associado à chave; devolve o valor prévio associado à chave ou null V get(K key) devolve o valor associado à chave key ou null remove o par chave/valor e devolve o valor associado à V remove(K key) chave ou null caso não exista boolean containsKey(K key) devolve true se a coleção contém a chave key boolean containsValue(V value) devolve true se a coleção contém o valor value devolve a quantidade de pares chave/valor contidos na int size() coleção boolean isEmpty() devolve true se a coleção estiver vazia void clear() remove todos os pares chave/valor contidos na coleção devolve um conjunto com todas as chaves do dicionário Set keySet() (que passam a ser partilhadas) devolve uma coleção (que não pode ser um set – Collection values() descubra porquê) com todos os valores contidos no dicionário (ficam partilhados) devolve um conjunto com todos os pares chave/valor Set entrySet() Framework de Coleções do Java 28 Algoritmos e Estrutura de Dados do dicionário (ficam partilhados) Exemplo de aplicação de um dicionário Problema: ler um conjunto de palavras e apresentar por ordem alfabética o número de ocorrências de cada uma se usarmos o TreeMap temos a garantia que as palavras são no fim mostradas por ordem alfabética, como pedido. TreeMap dic = new TreeMap(); Scanner input = new Scanner(System.in); String word = input.next(); while (!word.equals(".")) { if (dic.containsKey(word)) dic.put(word, dic.get(word) + 1); um e um são dois else dic.put(word, 1); output: dois -> 1 word = input.next(); e -> 1 } são -> 1 for (String key: dic.keySet()) um -> 2 System.out.println(key + " -> " + dic.get(key)); Tal como exemplificado, a utilização do método keySet(), juntamente com o método get(), permite-nos iterar um dicionário. Mas seria mais indicado (eficiente) usarmos o método entrySet(), juntamente com os métodos getKey() e getValue() de cada objeto do set por ele devolvido: for (Entry e: dic.entrySet()) System.out.println(e.getKey() + " -> " + e.getValue()); Framework de Coleções do Java 29 Algoritmos e Estrutura de Dados O método hashCode() Qualquer objeto em Java contem o método hashCode(), para ser usado por algoritmos ou estruturas baseadas em Tabelas de Hash tal como os métodos clone(), toString() e equals(), é herdado da classe Object. O inteiro devolvido pelo hashCode() é um código usado pelas coleções baseadas em Tabelas de Hash, para conseguirem organizar os objetos de uma forma eficiente, isto é, de uma forma que possibilite o acesso mais rápido aos elementos colecionados. Para que possamos colecionar devidamente objetos em coleções baseadas em tabelas de hash (HashSet, LinkedHashSet, HashMap, …) devemos então implementar na classe dos objetos o método hashCode(), garantindo o cumprimento do seu contrato: Objetos que sejam iguais, devem ter necessariamente o mesmo código de hash; Objetos que sejam diferentes, podem ainda assim ter o mesmo código de hash, esta característica advém do facto de em geral o número de possíveis objetos ser maior que o número de possíveis códigos hash; Sempre que seja invocado sobre o mesmo objeto várias vezes durante uma execução da aplicação, o método hashCode() deve devolver consistentemente o mesmo inteiro. no entanto, o método hashCode() não garante o mesmo resultado entre diferentes execuções. Framework de Coleções do Java 30 Algoritmos e Estrutura de Dados O método hashCode() O contrato anterior subentende também a seguinte regra: sempre que implementemos o método equals(), devemos também implementar o hashCode(), de forma a ficarem consistentes; o método hashCode() deve ter em conta os mesmos atributos em que se basear o método equals(). Repare-se que, quando implementamos o equals(), estamos de alguma forma a considerar que alguns objetos são iguais a outros, e é sabido que o método hashCode() original trata todos os objetos como diferentes; daí, caso não reescrevêssemos convenientemente o método hashCode(), resultariam objetos iguais (obj1.equals(obj2)==true) com códigos diferentes (obj1.hashCode()!=obj2.hashCode()) A forma correta de definir o método hashCode() é algo complexa e sai fora do âmbito desta unidade curricular, mas felizmente, nos atuais IDEs, como é o caso do NetBeans, podemos facilmente gerar de forma (semi) automática esse método. Não devemos confundir código de hash com chave, dado que, como dissemos, objetos diferentes podem ter o mesmo código de hash (a que chamamos colisões), mas nunca chaves iguais. Framework de Coleções do Java 31 Algoritmos e Estrutura de Dados