Estruturas de Dados - Tipos de Coleções

Objetivos da seção

Conceito Geral de Coleção

Tipos de Coleções

Listas

Conjuntos

Mapas

Coleções em Java

CollectionInterfaces.gif (3005 bytes)

Tipo de Coleção Coleção Java Tipo de Método Nome do Método
Todas as coleções com exceção de Mapas Collection Adição add(Object elemento)
Remoção remove(Object elemento)
clear()
Acesso iterator()
Pesquisa contains(Object elemento)
Atributos size()
List Vector
ArrayList
LinkedList		 Adição add(int index, Object elemento)
Remoção remove(int index)
Acesso get(index)
listIterator
(iterador que pode andar para trás)
Pesquisa indexOf(Object elemento)
Conjunto HashSet
TreeSet		   Nenhum método a mais
Map HashMap
TreeMap		 Adição put(Object key, Object value)
Remoção remove(Object key)
clear()
Acesso get(Object key)
(Isso também é "pesquisa")
Set entrySet()
(retorna os itens como conjunto)
Set keySet()
(retorna as chaves como conjunto)
Collection values()
(retorna os valores como Collection)
Pesquisa get(Object key)
(Isso também é "acesso")
Atributos size()

Collection.gif (9840 bytes)

Map.gif (4082 bytes)

Exemplos de Uso das Coleções em Java

Implementação com 6 tipos de Coleções

import java.io.*;
import java.util.*;

public class TestaColecoes {
  public static void main(String[] args) {
    if(args.length < 3) {
      sintaxe();
    }
    try {
      BufferedReader arqDados = new BufferedReader(new FileReader(args[1]));
      BufferedReader arqPesquisa = new BufferedReader(new FileReader(args[2]));
      if(args[0].equals("-v")) {
        testaColecao(new ArrayList(), arqDados, arqPesquisa);
      } else if(args[0].equals("-le")) {
        testaColecao(new LinkedList(), arqDados, arqPesquisa);
      } else if(args[0].equals("-hs")) {
        testaColecao(new HashSet(), arqDados, arqPesquisa);
      } else if(args[0].equals("-ts")) {
        testaColecao(new TreeSet(), arqDados, arqPesquisa);
      } else if(args[0].equals("-hm")) {
        testaMapa(new HashMap(), arqDados, arqPesquisa);
      } else if(args[0].equals("-tm")) {
        testaMapa(new TreeMap(), arqDados, arqPesquisa);
      } else {
        sintaxe();
      }
    } catch(IOException e) {
      System.err.println(e);
      System.exit(1);
    }
  }
  static void sintaxe() {
    System.err.println("Sintaxe: TestaColecoes [-v|-le|-hs|-ts|-hm|-tm] arquivoDados arquivoAPesquisar");
    System.exit(1);
  }
  static void testaColecao(Collection colecao, BufferedReader arqDados, BufferedReader arqPesquisa) throws IOException {
    long init = System.currentTimeMillis();
    carregaColeção(colecao, arqDados);
    long fimCarga = System.currentTimeMillis();
    int numAchados = pesquisaColeção(colecao, arqPesquisa);
    long fimPesquisa = System.currentTimeMillis();
    System.out.println("Elementos achados usando " + colecao.getClass().getName() + ": " + numAchados);
    System.out.println("Carga de dados demorou " + ((fimCarga - init)/1000.0) + " segundos");
    System.out.println("Pesquisa de dados demorou " + ((fimPesquisa - fimCarga)/1000.0) + " segundos");
    System.out.println("Total de tempo " + ((fimPesquisa - init)/1000.0) + " segundos");
  }
  static void carregaColeção(Collection colecao, BufferedReader arqDados) throws IOException {
    String linha;
    while((linha = arqDados.readLine()) != null) {
      colecao.add(linha);
    }
  }
  static int pesquisaColeção(Collection colecao, BufferedReader arqPesquisa) throws IOException {
    String linha;
    int numAchados = 0;
    while((linha = arqPesquisa.readLine()) != null) {
      if(colecao.contains(linha)) {
        numAchados++;
      }
    }
    return numAchados;
  }
  static void testaMapa(Map mapa, BufferedReader arqDados, BufferedReader arqPesquisa) throws IOException {
    long init = System.currentTimeMillis();
    carregaMapa(mapa, arqDados);
    long fimCarga = System.currentTimeMillis();
    int numAchados = pesquisaMapa(mapa, arqPesquisa);
    long fimPesquisa = System.currentTimeMillis();
    System.out.println("Elementos achados usando " + mapa.getClass().getName() + ": " + numAchados);
    System.out.println("Carga de dados demorou " + ((fimCarga - init)/1000.0) + " segundos");
    System.out.println("Pesquisa de dados demorou " + ((fimPesquisa - fimCarga)/1000.0) + " segundos");
    System.out.println("Total de tempo " + ((fimPesquisa - init)/1000.0) + " segundos");
  }
  static void carregaMapa(Map mapa, BufferedReader arqDados) throws IOException {
    String linha;
    while((linha = arqDados.readLine()) != null) {
      StringTokenizer st = new StringTokenizer(linha, ":");
      String chave = st.nextToken();
      mapa.put(chave, st.nextToken());
    }
  }
  static int pesquisaMapa(Map mapa, BufferedReader arqPesquisa) throws IOException {
    String linha;
    int numAchados = 0;
    while((linha = arqPesquisa.readLine()) != null) {
      StringTokenizer st = new StringTokenizer(linha, ":");
      String chave = st.nextToken();
      if(mapa.get(chave) != null) {
        numAchados++;
      }
    }
    return numAchados;
  }
}
java GeraDados 20000 >dados.txt
java TestaColecoes -xxx dados.txt dados.txt
(onde xxx = -v, -le, -hs, -ts, -hm, -tm)
Exemplo:

C:\...\src>java TestaColecoes -tm dados.txt dados.txt
Elementos achados usando java.util.HashMap: 20000
Carga de dados demorou 1.252 segundos
Pesquisa de dados demorou 0.501 segundos
Total de tempo 1.753 segundos
Coleção Tempo de carga de dados (segundos) Tempo de pesquisa de dados (segundos) Tempo total (segundos)
ArrayList 0.6 54.7 55.3
LinkedList 0.7 154.1 154.8
HashSet 0.8 0.7 1.5
TreeSet 1.1 0.8 1.9
HashMap 1.3 0.5 1.8
TreeMap 1.5 0.7 2.3

Como Escolher entre Coleções?

ed-2 programa anterior próxima