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

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.