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*][1] tem o problema da coincidência de valores calculados e o que era [complexidade][2] 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*][3] 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*][4] 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][5], talvez possa pegá-lo para testar com seus dados, lá claramente a `HashMap` ganhou. [Coloquei no **GitHub** para referência futura][6]. [1]: https://pt.stackoverflow.com/q/429851/101 [2]: https://pt.stackoverflow.com/a/56868/101 [3]: https://pt.stackoverflow.com/q/356435/101 [4]: https://pt.stackoverflow.com/q/198252/101 [5]: https://stackoverflow.com/a/23608250/221800 [6]: https://github.com/maniero/SOpt/blob/master/Java/Conceptual.md