Performance: HashSet em vez de ArrayList

Quando um programador começa com Java, ele rapidamente desiste das arrays para trabalhar com a ArrayList, que encapsula algumas rotinas comuns e trabalhosas. Depois o programador começa a se preocupar mais com o encapsulamento e passa a se refernciar as ArrayLists como List.

Um último passo que é mais díficil do programador tomar é de abstrair suas referências para Collection. Isso talvez ocorra por causa da óbvia ausência do método get(int) na interface Collection, apesar de que em muitos casos estamos apenas usando uma coleção para guardar um punhado de referências, sem nos importar com a ordem em que vamos percorrê-las e nem vamos precisar pegar uma referência que está em determinada posição (acesso aleatório). É nesse caso que a utilização dos Sets (em especial os que usam tabelas de espalhamento) é fortemente indicada (e mesmo que você precisasse garantir a ordem para iterar as referências, poderia usar uma coleção como a LinkedHashSet).

No curso de Java e Orientação a Objetos da Caelum, temos alguns exercícios extras. No capítulo de coleções tentamos mostrar a grande diferença de se usar um HashSet em vez de uma ArrayList quando precisamos realizar muitas buscas nessa coleção (isto é, usar o contains()). Você pode baixar essa apostila através do site.

Segue um código em que inserimos 30 mil referências a objetos do tipo Integer em uma ArrayList, e depois fazemos uma busca por cada um deles. Repare que 30 mil não é um número incomum.

public class TestaCollections {
  public static void main(String[] args) {
    Collection<Integer> colecao = new ArrayList<Integer>();

    long tempoInicial = System.currentTimeMillis();

    for (int i = 0; i < 30000; i++) {
      colecao.add(i);
    }

    for (int i = 0; i < 30000; i++) {
      colecao.contains(i);
    }

    long tempoFinal = System.currentTimeMillis();
    System.out.printf("%.3f segundos%n", (tempoFinal - tempoInicial) / 1000d);
  }
}

O resultado: 8,891 segundos.

Vamos agora realizar o mesmo teste só que com uma estrutura que utilize tabelas de espalhamento, nesse caso o HashSet. Mudamos a seguinte linha:

Collection<Integer> colecao = new ArrayList<Integer>();

Para:

Collection<Integer> colecao = new HashSet<Integer>();

O novo resultado? Incríveis 0,078 segundos. 114 vezes mais rápido! E se você aumentar o tamanho dos laços dos testes, essa proporção só vai aumentar! Porque isso? O contains da ArrayList faz uma busca linear, já o HashSet utiliza uma tabela de espalhamento para tentar fazer a busca em tempo constante.

Você ainda pode fazer outros testes interessantes. Um TreeSet será mais devagar para inserir, pois mantém uma árvore rubro negra como estrutura de dados interna, e sua busca muito melhor que a da ArrayList e um pouco mais lenta que a do HashSet, porém teremos nossos elementos ordenados. Comparar a inserção e busca de elementos entre LinkedList e ArrayList também mostra números impressionantes: percorrer uma LinkedList sem usar um Iterator (ou enhanced for) é absurdamente lento, já que o seu método get(int) percorre a lista toda desde o começo, por sua vez, na ArrayList inserir elementos nas posições iniciais não é nada performático (é necessário deslocar todo o restante da array pra frente).

Obviamente uma boa função de hash também é essencial. Recentemente a Sun melhorou a função de hash dos nomes dos métodos que o compilador utilizava para depois procurá-los, e com apenas isso conseguiu uma melhoria de performance de 2% na execução geral. Imagine se eles utilizassem uma List para isso? Dominar as coleções e estruturas de dados do Java é fundamental para um bom código.

19 Comentários

  1. Carlos Villela 05/10/2006 at 05:48 #

    Nao que seja o caso aqui, mas eh sempre, seeeeeeempre importante lembrar que essas otimizacoes nao devem ser feitas antes de um bom estudo da performance da aplicacao, e nao adianta sair trocando ArrayList por HashSet a torto e a direito se o problema esta num LEFT OUTER JOIN monstruoso e sem indices.

    Profiler. Sempre tenha um por perto 😉

  2. Guilherme 06/10/2006 at 05:51 #

    Cara uma dúvida… porque vc percorreu um por um ??? com o método contains….

    ele já faz isso pra vc… não precisa de um loop :S

    correto?

  3. Paulo Silveira 06/10/2006 at 08:31 #

    Não percorri um por um não, verifique o código: eu vejo um por um se o elemento I esta contido na coleção. apenas para testar a performance, ja que nao faco nada com o retorno booleano do metodo.

  4. Guilherme Silveira 06/10/2006 at 15:11 #

    Eu nunca tenho meu profiler por perto. Por isso que semanalmente eu baixo o JProfiler e pego uma licensa nova dele…

  5. Guilherme 06/10/2006 at 17:51 #

    relamente nao havia intendido… entendi sim a sua ideía de teste de perfomance… me desculpe pelo mal entendido.

    no mais parabéns pelo artigo. muito interessante o HAshSet

  6. takeshi 10/10/2006 at 09:10 #

    o unico problema do hashset eh que ele usa um HashMap por traz, gerando varios Map.MapEntry’s (e um objeto como chave), enquanto o ArrayList usa um simples array.
    Poderia se dizer que eh um compromisso entre processamento e consumo de memoria, certo?

  7. Paulo Silveira 10/10/2006 at 09:32 #

    Ola Takeshi. bom ponto. Creio que não faça tanta diferença, porque a array da arraylist tambem gasta bastante memória: 4 bytes para cada indice (tamanho da referencia considerando que a maquina virtual endereça 32 bits). O MapEntry pode acabar gasnta mais memoria, ja que guarda uma referencia a key e outra a value. Mas ambos os gastos ficarão muito pequeno em relação a memória total (deep) gasta por seus objetos pendurados nessas coleções.

  8. Wagner 22/10/2006 at 13:12 #

    Pô senhores, apesar de este assunto ainda ser para eu meu alienijena, ou seria alienigena, bem tanto faz, esta matéria estou vendo no curso. Parabéns pelo trabalho, digo comentário.

    Um abraço.

  9. Nelson 01/04/2008 at 14:23 #

    Paulo parabéns pelo artigo!

    Gostaria de saber de vc, qual a melhor implementação de collection para usar com thread e a melhor forma de compartilhar uma única instancia dessa collection com várias threads.

    Um abraço.

  10. Paulo Silveira 01/04/2008 at 14:27 #

    Ola Nelson. Voce pode usar as collections de dentro do java.util.concurrent, que sao thread safe e algumas delas nem mesmo usam locks. Voce tambem pode usar as antigas Vector e Hashtable, mas eu nao aconselho, prefiro ate usar ArrayList e utilizar o Collections.synchronizedList junto com syncrhonized quando for iterar sob ela…

  11. Eduardo 27/03/2009 at 06:25 #

    Pois eh… e como fica as aplicações com java 1.4???

    Fiz um teste aqui e vi que somente java 1.5 acima roda.

    Obrigado

  12. thiago 16/02/2011 at 12:12 #

    Esse tempo tá em milissegundos mesmo? Eu não saquei bem aquela divisão por 1000.

    Os dois tempos tão em milissegundos, só a subtração já vai dar o tempo em milissegundos. Sem a divisão por 1000 poderíamos fazer um cast pra float:

    System.out.printf(“%.0f ms%n”, (float) (tempoFinal – tempoInicial) );

    E aí sim o tempo estaria em milissegundos.

    Ou eu tô errado?

  13. Paulo Silveira 16/02/2011 at 15:14 #

    @Thiago tem toda razão, eu quis imprimir em segundos. O que estava errado era a saída. troquei ms por segundos. obrigado!

  14. Rafael Rocha 28/07/2011 at 18:28 #

    em muitos casos o uso do arraylist tb é mais performático

    http://scrtchpad.files.wordpress.com/2008/10/java-collections-performance-evaluation.pdf

  15. Paulo Silveira 28/07/2011 at 18:33 #

    Essa nao é uma comparação total de collections: so compara inserção e iteração de elementos. O contains, que muitas vezes é essencial, é justo onde os hashes vao ser incomparavelmente superior, nao só na notação O,.

  16. Rafael Costa 23/10/2016 at 12:30 #

    Paulo Silveira, obrigado pelo artigo.

    Incrível, o artigo postado dia 04/10/2006 me tirou uma dúvida em 23/10/2016 (10 anos depois).. rsrs

    Muito bom, agradeço ao pessoal que fez comentários também, acabaram mensionando pontos que não foram abordados no artigo.

  17. Paulo Silveira 23/10/2016 at 22:59 #

    que legal rafael! o artigo é antigo, mas como está relacionado a computação ele não fica desatualizado, além de lidar com duas classes ainda essenciais no java

  18. Felipe Borba 12/11/2016 at 21:04 #

    Parabéns pelo artigo Paulo,

    Gosto de artigos desse tipo, que mostram a teoria e funcionando na prática, entender como os algoritmos funcionam internamente é um grande ponto a levar em consideração antes de implementar algo;

    Valeu

  19. Antonio Henrique 10/09/2017 at 11:36 #

    Paulo, eu tenho uma necessidade de armazenar uma lista de uma class em memoria um pouco longa perto de 30000000, e praticamente com HashSet ou outros tipos de listas por volta de 9000000 o processamento fica muito lento, quem em certo ponto inviabiliza, estou preenchendo sequencialmente em um loop, alguma solução melhor para o meu problema?

    depois terei que armazenar isso em tabela, estou fazendo em memoria a parte de validação pra ficar mais rápido, quando for armazenar utilizarei uma especia de bulkcopy

    Obrigado.

Deixe uma resposta