Muito provavelmente HashMap
, cuja implementação é a mais simples dentre as alternativas disponíveis: uma simples tabela de espalhamento não-sincronizada, não-concorrente, não-ordenada (no sentido de não haver garantia na ordem em que seu iterator retorna elementos) e não-navegável (no sentido de NavigableMap
).
A documentação sugere uma otimização na hora de instanciar o HashMap
:
This implementation provides constant-time performance for the basic
operations (get and put), assuming the hash function disperses the
elements properly among the buckets. Iteration over collection views
requires time proportional to the "capacity" of the HashMap instance
(the number of buckets) plus its size (the number of key-value
mappings). Thus, it's very important not to set the initial capacity
too high (or the load factor too low) if iteration performance is
important.
An instance of HashMap has two parameters that affect its performance:
initial capacity and load factor. The capacity is the number of
buckets in the hash table, and the initial capacity is simply the
capacity at the time the hash table is created. The load factor is a
measure of how full the hash table is allowed to get before its
capacity is automatically increased. When the number of entries in the
hash table exceeds the product of the load factor and the current
capacity, the hash table is rehashed (that is, internal data
structures are rebuilt) so that the hash table has approximately twice
the number of buckets.
As a general rule, the default load factor (.75) offers a good
tradeoff between time and space costs. Higher values decrease the
space overhead but increase the lookup cost (reflected in most of the
operations of the HashMap class, including get and put). The expected
number of entries in the map and its load factor should be taken into
account when setting its initial capacity, so as to minimize the
number of rehash operations. If the initial capacity is greater than
the maximum number of entries divided by the load factor, no rehash
operations will ever occur.
A ideia é que, havendo memória disponível, se evite custosos processos de rehash adotando uma capacidade inicial maior que o quociente entre o número esperado de entradas e o load factor. No seu caso que é de 2 a 10 mil elementos, portanto, seria bom instanciar o HashMap
com uma capacidade inicial da ordem de 2667 a 13334, já que o load factor padrão e recomendado é 0.75.
Note que se for em Android, vale a pena conhecer a classe android.util.SparseArray
, que é uma implementação mais eficiente que um HashMap
para uso com chaves do tipo inteiro.