TransWikia.com

Quais são as diferenças entre implementação de mapas por hashes ou árvores?

Stack Overflow em Português Asked by Felipe Machado on January 2, 2022

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

One Answer

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 arrya 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.

Answered by Maniero on January 2, 2022

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP