CODEWITHSUNDEEP
javaperformancedictionary
Vicky
Vicky

Reputation: 1235

Performance of TreeMap, HashMap and LinkedHashMap?

In TreeMap - Elements are sorted
In HashMap - Elements are not sorted

So, if I consider get, put and remove methods which map should I use for performance?

Upvotes: 8

Views: 15150

Answers (3)

JoaoFCarvalho
JoaoFCarvalho

Reputation: 21

It depends on your intentions, in terms of iteration:

  • The HashMap makes no guarentee of such, wich means its random;
  • The TreeMap uses natural order or a Comparator if specified;
  • The LinkedHashMap is iterated according to insertion order.

Futhermore, for TimeComplexity for put/get/remove/containsKey:

  • HashSet - O(1);
  • TreeMap - O(log(n)) or O(1); -- see references!
  • LinkedHashSet - O(1).

Geekforgeeks:

StackOverflow:

Upvotes: 0

dhardy
dhardy

Reputation: 12144

It depends on how fast the hash and comparison functions are on the keys in your map. It depends on whether you're more interested in average case performance or worst-case performance. It depends on whether you have a good hash function applied to your map's keys; hash values should be well distributed across the hash function's domain (yes, it can depend on your data).

In general (when you can't be bothered to test), a hash map is often a good answer, but it's also unlikely to make a big difference if you don't have a thousands of entries (for small sizes, a "vec map" can also work well).

Upvotes: 0

Keith Randall
Keith Randall

Reputation: 23265

Use a HashMap unless you have some need for ordering. HashMap is faster.

That said, you can make it easy to switch by using the generic interface as your declaration:

 Map<String,String> M = new HashMap<String,String>();
 ...use M lots of places...

Then all you have to do is switch one place and your code uses the new map type.

Edit:

A simple timing test:

import java.util.*;
class TimingTest {
  public static void main(String[] args) {
    Map<String,String> M = new HashMap<String,String>();
    long start = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {
      M.put(Integer.toString(i), "foo");
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);
  }
}

Upvotes: 5

Related Questions