7

Eu costumo usar bastante a estrutura java.util.HashMap<K,V> mesmo para escopos pequenos com poucas entradas (até umas 50). Mas andei me perguntando se a estrutura java.util.TreeMap<K,V> não seria melhor para essa situação, levando em consideração que o HashMap é implementado sobre uma hashtable em que o cálculo do hash é potencialmente caro, em termos de tempo de processamento? Já a TreeMap é implementada sobre árvore e faz operações com ponteiros, o que potencialmente levaria a uma melhor performance (tempo de escrita/leitura).

Isso faz sentido? Para simplificar podemos considerar aplicações sem concorrência.

1
  • São usos diferentes. TreeMap foi idealizado para quando você quer percorrer o mapa seguindo uma ordem natural, como a alfabética no caso de chaves Strings. HashMap é percorrido em ordem aleatória e quando não há excesso de colisões costuma ser rápido, como é dito na resposta.
    – Piovezan
    Commented 20/06/2022 às 23:52

2 Respostas 2

10

Para poucos acessos tanto faz. Performance é um problema mesmo quando se faz em volume muito grande.

De fato a quantidade de entradas pode fazer diferença. Não é tão simples responder preto no branco, é cinza mesmo. Se eu te falar para medir achará como é o desempenho com aqueles dados, não para qualquer caso. A arquitetura que está rodando e a infraestrutura disponível pode dar diferença.

Tabelas hash tem o problema da coincidência de valores calculados e o que era complexidade O(1) pode virar um O(n), ainda que esse é um caso extremo que não acontecerá de fato.

Outra questão é que o cálculo do hash depende do dado que está sendo usado como chave, então o tempo total não é tão constante assim (a constância dita é sobre a busca, não a preparação dela), muito menos dá para antecipar sem saber qual é ele.

Na maioria dos casos ele deve ser mais rápido.

A árvore tem complexidade O(log n) e para poucos dados o logaritmo de N tende ser muito próximo de 1, sem ter o overhead do cálculo. De fato ele pode ser mais rápido, mas na prática é difícil que seja.

No SO tem uma resposta com testes, talvez possa pegá-lo para testar com seus dados, lá claramente a HashMap ganhou.

Coloquei no GitHub para referência futura.

5

Com HashMap você terá O(1) para acesso na maioria das vezes. Depende do número de colisões, e que devido ao baixo número de dados não será o caso.

Enquanto com o TreeMap para acesso é O(log n), tendo em vista que utiliza uma árvore binária balanceada.

Se a ordenação dos dados para busca não for essencial acredito que HashMap seja mais rápido nesse caso.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .