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, vai 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][1] 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][2], talvez possa pegá-lo para testar com seus dados. lá claramente a `HashMap` ganhou.


  [1]: https://pt.stackoverflow.com/a/56868/101
  [2]: https://stackoverflow.com/a/23608250/221800