I disagree somewhat with this advice. Big-O notation only tells you
about the limiting behavior for large problems.

If there is a very frequent need to retrieve from small collections, the
performance could be dominated by overheads and constant factor
differences that disappear in the limiting case. There is then no
substitute for measurement.

However, the measurement needs to be realistic. In particular, timing
one retrieval makes no sense at all.

Patricia

Yes, you are measuring it the wrong way.

In any situation where the system is multi-tasking (and Java is always
multitasking to a first approximation because there are at least two
threads running) its meaningless to measure elapsed time. The only valid
measure of efficiency for an task that doesn't involve i/o is the amount
of CPU time it consumes because that, at least, is not affected by other
processes unless the machine is so overloaded that every task switch
involves paging or task swapping.

Patricia's runs show interference by other processes very nicely.

If you are using Linux or a UNIX you should at least use the "time"
utility to measure the CPU time used. As you don't say what OS you're
using I can't say more than that.

Exactly. We can't advise you because we haven't any idea of:
- the number of items you want to search
- the relative size of the key and value in each item
- the degree of key duplication in your data
- the degree of key value clustering in your data
- the complexity of the key comparisons [1]

As Patricia said, the number of items and the key value distribution are
both vital information which you didn't provide.

The following assumes that all keys are not unique. It that's not true
then you need a more complex approach that can handle duplicates.

If the data is static the following is generally true: if you only do
infrequent searches of under 10 items a simple sequential search is
probably best because its overheads are minimal. With a few hundred
items and many searches of static data its better to sort the data once
its loaded and use a binary chop search: SortedMap will work this way
provided that you  build an unsorted map first and then construct the
SortedMap from it. Adding unsorted data item by item to an empty
SortedMap is likely to be very slow.

If the data isn't static and is initially unordered then either a hash
table (HashMap) or a red-black binary tree (TreeMap) is the way to go.
If the HashMap hashing algorithm generates synonyms because of your key
value distribution or because you've set the initial capacity too low
its performance will degrade fast and the TreeMap would be better. If
you need to read out the data in order then TreeMap is the only game in
town.

[1] This alone can invalidate a theoretical analysis. For instance, most
people will swear blind that Quicksort will always blow a Replacement
sort into the weeds. No less an authority than Niklaus Wirth says so
without any qualification of this opinion so it *must* be so! But his
analysis assumes that swapping items is much more expensive than
comparing them. If your item swap method is very fast (e.g. swapping
references to large objects rather than copying the objects about in an
array) and the key comparison is slow (e.g. a lexicographic string
comparison over multiple keys rather than comparing single integer keys)
then you'll find in practice that a Replacement sort is several times
faster than Quicksort. I know this because I've been there.

Yes. You need a sample of real data to test against so you get a
representative key distribution and the sample has to be large enough to
 give a realistic performance estimation for live data. This means it
*must* be within 2 - 3 orders of magnitude of the design data volume and
preferably within one order of magnitude. By way of illustration, I've
seen several databases that ran just fine on typical programmer test
volumes (under 10-50 items in the biggest table) but that had unusably
bad performance with a few tens of thousands of rows loaded.

If all this is new to you, go and find a copy of Sedgewick: Algorithms.
Its code examples are in Pascal, but any competent programmer should be
able to translate that to Java in their head. There are also Java
versions of this book - at a price.