Coleções em Java (Parte 1)

Flávia Falcão

AgendaIntroduçãoColeçõesListasConjuntosMapasPerformanceComo escolher uma coleção

Introdução -Problema É possível criar array, de tamanhos fixo,

em Java , tanto de tipos primitivos como de Objetos

// declaração de arrayint[] x, y;int z[];// criação de 10 posiçõesx = new int[10];

Problema Depois de criado, o array não pode ser

redimensionado. O que podemos fazer é copiar os

elementos de um array para outro.int[] x = {1,2,3};int[] y = new int[5];System.arraycopy(x, 0, y, 0, 3);

for (int i = 0; i < y.length; i++) { System.out.println(y[i]);} // será impresso 1,2,3,0 e 0

Problema Não conseguimos saber quantas

posições do array já foram populadas sem criar, para isso, métodos auxiliares.

ColeçõesDesde a versão 1.2 a plataforma J2SE

inclui um framework de coleções. Coleção é um objeto que representa um grupo

de objetos. Um framework de coleções é uma arquitetura

unificada para representação e manipulação de coleções, permitindo que elas sejam manipuladas independentemente dos detalhes de sua implementação.

ColeçõesUma coleção representa um grupo de

objetos armazenados em uma estrutura de dados.

Utilizadas para armazenar, recuperar e manipular elementos.

Ex: Vector, HashTable

Collections Framework Conjunto de interfaces, implementações

e algoritmos Vantagens

Reduz esforço de programaçãoAumenta velocidade e qualidade na

programaçãoPermite interoperabilidade entre API´sReduz esforço para aprender uma nova APIReduz esforço para criar uma nova APIPromove reuso

Collections Framework Consistem em :

Interfaces de coleçõesImplementações de uso geralImplementações abstratasAlgoritmos

Coleções Java -Interfaces

InterfacesSão utilizadas sempre que possível

como: Parâmetros de métodosRetorno dos métodos

Lembrar sempre posso utilizar uma interface onde poderia se usar uma implementação.

Permite polimorfismo

Collection Raiz da hierarquia Grupo mais genérico de elementos Não garante nas implementações

DuplicatasOrdenação

Não possui nenhuma implementação direta

Iterator, estrutura de navegaçãonext, hasNext, remove(opcional)

ColeçõesDefine as operaçoes básicas para as

coleções de objetos:Adição de elementos;Remoção de elementos;Acesso aos elementos;Pesquisa de elementos;Metadados da coleção.

Coleções Java

Tipo do método Nome do método

Adição add(Object elemento)Remoção remove(Object elemento)

clear()Acesso iterator()Pesquisa contains (Object elemento)Atributos size()

A tabela abaixo mostra os principais métodos da interface Collection.

Collectionpublic interface Collection { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); // Optional boolean remove(Object element); // Optional Iterator iterator();

// Bulk Operations boolean containsAll(Collection c); boolean addAll(Collection c); // Optional boolean removeAll(Collection c); // Optional boolean retainAll(Collection c); // Optional void clear(); // Optional

// Array Operations Object[] toArray(); Object[] toArray(Object a[]); }

Existem vários tipos de coleções, sendo que a utilização de cada um depende da necessidade da aplicação.

ColeçõesExistem três grandes tipos de

coleções:Listas (List)Conjuntos (Set)Mapas (Map)

A seguir veremos em detalhes cada tipo.

Coleções - listasUma lista é uma coleção de objetos

armazenados linearmente. Cada elemento tem o seu sucessor (menos o último) e o seu antecessor (menos o primeiro).

Listas podem ser mantidas ordenadas ou sem ordem.

Pode haver duplicatas

Coleções - ListasControle na posição de inserção ou

remoçãoAcesso aos elementos pelo índice

Coleções - listas As operações mais importantes em listas

são:Adicionar um objeto em qualquer lugar da

lista;Remover um objeto de qualquer lugar da

lista;Obter o elemento de qualquer lugar da

lista;

Percorrer os elementos da lista;Verificar se um elemento está na lista;Descobrir o índice de um elemento na

lista;Obter o número de elementos da

coleção.

Listpublic interface List extends Collection { // Positional Access Object get(int index); Object set(int index, Object element); // Optional void add(int index, Object element); // Optional Object remove(int index); // Optional abstract boolean addAll(int index, Collection c); // Optional

// Search int indexOf(Object o); int lastIndexOf(Object o);

// Iteration ListIterator listIterator(); ListIterator listIterator(int index);

// Range-view List subList(int from, int to);}

Coleções - conjuntosUm conjunto é uma coleção que não

tem elementos duplicados.Da mesma forma que as listas, os

conjuntos podem ser mantidos ordenados ou não.

Coleções - conjuntosAs operações mais importantes em

conjuntos são:Adicionar um objeto no conjunto

(descartando os repetidos);Remover um objeto do conjunto;Percorrer os elementos do conjunto;Verificar se um elemento está no

conjunto;Obter o número de elementos do

conjunto.

Coleções - mapasUm mapa armazena pares (chave,

valor) chamados de itens.Chaves e valores podem ser de

qualquer tipo.A chave é utilizada para achar o

elemento de forma rápida, utilizando estruturas especiais.

As chaves armazenadas nos mapas podem estar ordenadas ou não.

Coleções - mapasAs operações mais importantes em

mapas são:Adicionar um item no mapa, fornecendo

chave e valor;Remover um item baseado em uma

chave;Percorrer os itens da coleção;Verificar se um item está na coleção,

fornecendo a chave;Obter o número de elementos da coleção.

Coleções Java

Tipo do método Nome do método

Adição add(int index, Object elemento)Remoção remove(int index)

Acesso get(int index)listIterator()

Pesquisa indexOf (Object elemento)

A tabela abaixo mostra os principais métodos de listas (Vector, ArrayList e LinkedList).

IteratorO método iterator retorna uma

estrutura que permite percorrer os elementos armazenados.

A interface Iterator possui dois métodos:hasNext() – verifica se ainda existem

elementos;next() – retorna o próximo elemento.

Coleções JavaPara conjuntos, os métodos

principais são os mesmos mostrados em Collection.

As duas implementações principais para conjuntos são o HashSet e o TreeSet.

Coleções Java

Tipo do método Nome do método

Adição put(Object chave, Object elemento)Remoção remove(Object chave)Acesso get(Object chave)

set entrySet()set keySet()

Pesquisa get(Object chave)Atributos size()

A tabela abaixo mostra os principais métodos de mapas (HashMap, TreeMap, Hashtable).

PerformancePara testar a performance das

coleções podemos criar um arquivo texto contendo um conjunto de dados.

Cada elemento desse conjunto será inserido na coleção e depois pesquisado.

No final teremos o tempo que cada uma das estruturas levou para executar as operações.

PerformanceO arquivo tem 20000 linhas e cada

linha é composta de valor1:valor2.Quando a coleção for um mapa o

primeiro valor será a chave e o segundo é o valor.

Caso a coleção for uma lista ou conjunto será inserida a linha inteira.

Performance

Coleção Carga Pesquisa Total

ArrayList 0,21 66,58 66,79LinkedList 0,35 85,66 86,01

Vector 0,42 66,45 66,87HashSet 0,46 0,18 0,64TreeSet 0,61 0,27 0,88

HashMap 0,62 0,22 0,84TreeMap 0,83 0,34 1,17

Hashtable 0,60 0,23 0,83

Os tempos podem ser vistos na tabela abaixo:

Escolha da coleçãoA aplicação é quem indica o tipo

de coleção que deve ser usada:Se a aplicação requer duplicatas use

lista;Se requer muita pesquisa de dados

não use lista;Se não requer duplicatas e não utiliza

chaves, use conjunto;Se não requer duplicatas e utiliza

chaves, use mapa.

Exemplo de listaimport java.util.*;public class AppLinkedList { public static void main(String[] args) { LinkedList v = new LinkedList(); for (int i = 0; i < 5; i++) { Integer valor = new Integer(i); v.add(valor); } v.add(new Integer(3)); v.add(new Integer(5)); Iterator it = v.iterator(); while (it.hasNext()) { Integer valores = (Integer)it.next(); System.out.println(valores.intValue()); } // vai imprimir 0,1,2,3,4,3,5 }}

Exemplo de conjuntoimport java.util.*;public class AppTreeSet { public static void main(String[] args) { TreeSet v = new TreeSet(); for (int i = 0; i < 5; i++) { Integer valor = new Integer(i); v.add(valor); } v.add(new Integer(3)); // elemento repetido v.add(new Integer(5)); Iterator it = v.iterator(); while (it.hasNext()) { Integer valores = (Integer)it.next(); System.out.println(valores.intValue()); } // vai imprimir 0,1,2,3,4,5 }}

Exemplo de conjunto

• No exemplo a seguir foi redefinido o método compareTo() para permitir que o elemento seja inserido no conjunto.

import java.util.*;public class Empregado implements Comparable { public String nome; public float salario; public Empregado (String nome, float salario) { this.nome = nome; this.salario = salario; } public int compareTo(Object obj) { Empregado e = (Empregado) obj; return this.nome.compareTo(e.nome); }}

Exemplo de conjuntoimport java.util.*;public class AppEmp { public static void main(String[] args) { Empregado e1 = new Empregado("Andrés", 240); Empregado e2 = new Empregado("Andrés", 240); TreeSet t = new TreeSet(); t.add(e1); t.add(e2); Iterator it = t.iterator(); while (it.hasNext()) { Empregado e = (Empregado)it.next(); e.imprimir(); } }}

Exemplo de conjuntoSe a inserção for em uma tabela hash, os métodos equals() e hashCode() devem ser redefinidos de forma que objetos iguais tenham o mesmo hashCode.

Exemplo de conjuntoimport java.util.*;public class Empregado { ... public boolean equals(Object obj) { if (obj != null) { Empregado e = (Empregado) obj; if (this.nome.equalsIgnoreCase(e.nome) ) return true; } return false; } public int hashCode() { return this.nome.hashCode(); } ...}

Exemplo de conjuntoimport java.util.*;public class AppHashSet { public static void main(String[] args) { HashSet v = new HashSet(); Empregado e1 = new Empregado("Andrés", 240); Empregado e2 = new Empregado("Andrés", 240); Empregado e3 = new Empregado("Danielle", 540); v.add(e1); v.add(e2); v.add(e3); Iterator it = v.iterator(); while (it.hasNext()) { Empregado emp = (Empregado) it.next(); emp.imprimir(); } }}

Exemplo de mapaimport java.util.*;public class AppTreeMap { public static void main(String[] args) { TreeMap v = new TreeMap(); for (int i = 0; i < 5; i++) { Integer valor = new Integer(i); v.put(valor, valor.toString()); } // obter os valores como coleção Collection c = v.values(); Iterator it = c.iterator(); while (it.hasNext()) { String valores = (String)it.next(); System.out.println(valores); } // vai imprimir 0,1,2,3,4 }}

Exemplo de mapaimport java.util.*;public class AppHashMap { public static void main(String[] args) { TreeMap v = new TreeMap(); Empregado e1 = new Empregado("Andrés", 240); Empregado e2 = new Empregado("Andrés", 240); Empregado e3 = new Empregado("Danielle", 540); v.put(new Integer(1), e1); v.put(new Integer(2), e2); v.put(new Integer(3), e3); Collection c = v.values(); Iterator it = c.iterator(); while (it.hasNext()) { Empregado emp = (Empregado) it.next(); emp.imprimir(); } }}

Classe VectorA seguir temos um trecho de

código que preenche um Vector.import java.util.Vector;public class AppVector { public static void main(String[] args) { Vector v = new Vector(); for (int i = 0; i < 20; i++) { Integer valor = new Integer(i); v.add(valor); } }}

VectorNo próximo exemplo veremos

como fazer para remover e recuperar elementos de uma estrutura do tipo Vector.

import java.util.*;public class AppVector2 { public static void main(String[] arg) { Vector v = new Vector(); for (int i = 0; i < 10; i++) { Integer valor = new Integer(i); v.add(valor); } // recuperar um elemento Integer recuperado = (Integer)v.get(5); System.out.println(recuperado.intValue()); v.remove(3); // remover um elemento

// percorrer os elementos Iterator it = v.iterator(); while (it.hasNext()) { Integer valores = (Integer)it.next();

System.out.println(valores.intValue());

} }}

O método get(int i) recupera o elemento que está na posição i do Vector.

O método remove(int i) remove o elemento na posição i;

ExercícioA crie uma classe conta e uma

classe VetorConta que armazene quantas contas desejar e imprima o saldo de cada uma, use iterator.