Better performance for few accesses: Hashmap or Treemap?

Question

I use the structure a lot java.util.HashMap<K,V> even for small scopes with few inputs (up to 50). But I’ve been wondering if the structure java.util.TreeMap<K,V> would not be better for this situation, taking into account that the HashMap is implemented on a hashtable where the calculation of hash is potentially expensive in terms of processing time? Already the TreeMap is implemented over a tree and does pointer operations, which would potentially lead to better performance (writing/reading time).

Does this make sense? To simplify we can consider applications without competition.

Answer 1

For few accesses it does much. Performance is a problem even when it is made in very big volume.

In fact the amount of entries can make a difference. It’s not so simple to answer black on white. It’s even gray. If I tell you to measure, you’ll find the performance with that data, not for any case. The running architecture and available infrastructure can make a difference.

Tables hash has the problem of matching calculated values and what was complexity (1) May become an O(n), although this is an extreme case that will not actually happen.

Another issue is that the calculation of hash depends on the data being used as key, so the total time is not so constant (the constancy said is about the search, not the preparation of it), much less can you anticipate without knowing what it is.

In most cases it should be faster.

The tree has complexity O(log n) and for few data the logarithm of N tends to be very close to 1, without having the overhead calculation. In fact it may be faster, but in practice it is difficult to be.

In the Only one answer with tests, maybe I can pick it up to test with your data. there clearly the HashMap won.

Answer 2

With HashMap you will have O(1) for access most of the time. It depends on the number of collisions, and that due to the low number of data will not be the case.

While with Treemap for access is O(log n), as it uses a balanced binary tree.

If the ordering of data for search is not essential I believe that Hashmap be faster in this case.