Better performance for a few hits: HashMap or TreeMap?

Question

Better performance for a few hits: HashMap or TreeMap?

Navigation

#1 by (6 votes)
#2 by (3 votes)

4

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

Does that make sense? For simplicity we can consider applications without competition.

java desempenho

asked by anonymous 25.01.2017 / 16:57

2 answers

3

With HashMap you will have O (1) to 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 the TreeMap for access is O (log n) , given that it uses a balanced binary tree.

If the ordering of search data is not essential, I believe that HashMap is faster in this case.

25.01.2017 / 17:13

Types of Calling Methods C # Get content inside string

score 6 · Accepted Answer

For a few hits, either. Performance is a problem even when it is done in very large volume.

In fact the amount of entries can make a difference. It is not so simple to answer black and white. It's really gray. If I tell you to measure, you'll find out how you perform with those data, not in any case. The architecture that is running and the infrastructure available can make a difference.

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

Another issue is that the hash calculation depends on the data being used as a key, so the time is not as constant as that, let alone anticipate without knowing what it is. p>

In most cases it should be faster.

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

In the SO has a test response , you might be able to get it to test with your data. there clearly the HashMap won.