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 tem o problema da coincidência de valores calculados e o que era complexidade 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, talvez possa pegá-lo para testar com seus dados, lá claramente a HashMap
ganhou.
Coloquei no GitHub para referência futura.