0

Qual a vantagem da implementação de mapas por tabela hash ao invés da árvore binaria?

3
  • Aqui tem um link que acredito vai te ajudar: Listas, árvores e tabela hash Commented 11/07/2018 às 12:38
  • Acho que compreendi o que estava procurando,vê se minha lógica tem sentido e se tiver coloque como resposta para colocar como solucionado já que sem sua ajuda não teria conseguido. Commented 11/07/2018 às 13:45
  • Resposta :É mais adequado a implementação da tabela Hash em um cenario quando se tem um grande volume de dados,sendo assim sua grande vantagem é o desempenho,enquanto a busca binária tem complexidade $ O(\log N)$ , o tempo de busca na tabela hash é praticamente independente do número de chaves armazenadas na tabela, ou seja, tem complexidade temporal $ O(1)$. Resumindo: Na tabela Hash seu desempenho não está relacionado com o sua quantidade de dados,ou seja para buscas com grande volume de dados é mais adequado sua utilização. Commented 11/07/2018 às 13:46

1 Resposta 1

3

A dúvida deveria ser mais ao contrário.

Se você precisa que os dados sejam classificados você precisa da árvore binária. Se precisa de ordem, precisa de um array, ou algum truque com a árvore binária (ou não). Se pode desprezar ordem ou classificação então a tabela de espalhamento pode ser útil.

A tabela de espalhamento possui complexidade O(1), ou seja, é constante não importa o volume de dados. É como se fosse o tempo de acesso de um array pelo seu índice. Não o mesmo tempo porque o hash precisa calcular o bucket onde o dado está antes de acessar.

A árvore binária tem complexidade O(log n) que em muitos casos é próximo de constante. De fato por não ter que calcular com baixo volume de dados é possível que ele seja mais rápido que hash, mesmo que log n dê algo maior que 1. Em grandes volumes será mais lento, mas não é uma diferença tão grande assim. Para ter uma ideia 1 bilhão de elementos pode ser acessado em apenas 30 passos. Apesar do volume influenciar o tempo de acesso, é irrisório, e em alguns casos não faz diferença.

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 .