HashTable x ArrayList em busca

Olá

Não é uma resposta que possa ser dada sem saber de mais detalhes. A única coisa que a gente pode dizer com certeza é que isto não tem nada a ver com desenvolvimento web ou não.

Entre os detalhes que podem influenciar a resposta estão o tamanho da tabela, o tipo de objetos que serão armazenados e se a tabela será ordenada ou não.

Para tabelas grandes, não ordenadas, com tamanho igual a um número primo, com load factor adequado e com o Hash code dos objetos armazenados calculado com um mínimo de inteligência, tabelas hash armazenadas em uma instância de HashMap permitirão buscas muitíssimo mais rápidas do que usando um ArrayList (que nem tem método de busca por um elemento isolado).

Caso a tabela seja muito pequena, ou possa ser ordenada, ou ainda não seja estudado um método HashCode adequado ao tipo de objeto armazenado, as vantagens das tabelas hash diminuirão, podendo até não existir (no caso de extrema ignorância no seu uso).

Dê uma breve estudada na teoria das tabelas hash e perceberá logo se é adequada ao seu problema. Experimente rodar testes comparando com ArrayList em termos de desempenho.

[]s
Luca

obrigado pela resposta, Luca

Cara,

Não sei quanto a busca para web, mas em uma busca normal, eu fiz o teste uma vez.
A diferença do ArrayList pro HashTable é gritante.
Eu fiz a seguinte rotina:

1. Adicionar 100 000 inteiros em uma coleção;
   2 Pesquisar por esses inteiros, 1 a 1.

O ArrayList demorou cerca de 20s, já a coleção Hash (usei um HashSet) demorou menos de 3s.

Se o seu HashTable contiver como chaves números inteiros, e se os dados que você for armazenar não forem muito dispersos (isso é, ocuparem bem todo arraylist), então, o ArrayList será certamente mais rápido que o HashMap.

Percorrer um ArrayList também tende a ser mais rápido do que percorrer um HashTable. Isso porque os dados de um ArrayList são armazenados “lado-a-lado” na memória, enquanto os de um HashMap tendem a ficar dispersos. O ArrayList também é uma classe mais econômica, pois usa poucas referências para apontar para seus dados.

Mas no geral, use como guideline o que o Luca falou. Detalhes como esse que eu citei vão ser problemas em pouquíssimas aplicações, geralmente onde memória é crítica ou o código executa num loop frenético.

O melhor mesmo é testar as implementações e analisar bem o comportamento de sua aplicação com um profiler. Isso é… se isso realmente estiver sendo um problema de performance para você.

PS: Só depois que respondi que percebi que você está falando em HashTable e não HashMap. O HashTable tem sincronização em todos os métodos, e isso pode torna-lo potencialmente mais lento, dependendo da aplicação. Assim como não é legal usar um Vector na maioria dos casos, prefira o HashMap ao HashTable.

viniGodoy, pode me dar um exemplo de hashMap?

É muito parecido com o HashTable.

Map<String, String> umMapa = new HashMap<String, String>();

umMapa.put("Vinicius", "Godoy");
umMapa.put("Sergio", "Taborda");
umMapa.put("David", "Buzzato");

System.out.println(umMapa.get("Vinicius"));

if (!umMapa.containsKey("Joana"))
    System.out.println("Joana não está no mapa!");

Existem algumas vantagens no mapa. É mais fácil iterar sobre as chaves e os valores:

//Você pode navegar pelas keys
for (String key : umMapa.keySet())
    System.out.println(key);

//Você pode navegar pelos valores
for (String value : umMapa.values())
    System.out.println(value);

//Ou por ambos
for (String entry : umMapa.entrySet())
    System.out.println(entry.getKey() + " -&gt " + entry.getValue());

Map<String, String> mapaSync = Collections.synchronizedMap(umMapa);

Map<String, String> unmodifiable = Collections.unmodifiableMap(umMapa);

Além do HashMap há também o TreeMap, que usa uma árvore binária para ordenar as chaves. A vantagem do TreeMap é que as chaves ficam ordenadas (portanto devem ser de uma classe Comparable ou você deve fornecer um Comparator). É útil também para classes comparáveis que não tem um hash bem definido, ou um hash que varia com o tempo.

valeu, cara! muitíssimo obrigado!

pra vc iterar entre um mapa e outro usa-se um while com .next()?

Não entendi a pergunta.

como eu faço pra inserir vários objetos automaticamente? por exemplo:

while (crs.next())
{
                Produto p = new Produto();
                p.setIdProduto(crs.getInt("idProduto"));
                p.setDescricao(crs.getString("descricao"));
                p.setPrecoSugerido(crs.getDouble("precoSugerido"));
                p.setQuantidadeEstoque(crs.getInt("quantidadeEstoque"));
                produtos.add(p);
}

é feito da mesma forma ou muda algo?

Da mesma forma. Mas lembre-se que com o mapa vc associa sempre um valor a uma chave, através do método put. Não o objeto diretamente, com o add.

Se for um mapa do ID para o Produto, ficaria assim:

Map<Integer, Produto> produtos = new HashMap<Integer, Produto>();

while (crs.next())   
{   
                Produto p = new Produto();   
                p.setIdProduto(crs.getInt("idProduto"));   
                p.setDescricao(crs.getString("descricao"));   
                p.setPrecoSugerido(crs.getDouble("precoSugerido"));   
                p.setQuantidadeEstoque(crs.getInt("quantidadeEstoque"));   
                produtos.put(p.getIdProduto(), p);   
}

valeu, viniGodoy!