8

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?

nawfal
  • 70,104
  • 56
  • 326
  • 368
Vicky
  • 1,215
  • 6
  • 22
  • 45
  • 1
    See the Javadoc. `HashMap` is specified to be O(1): 'constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets'. `TreeMap` is specified to 'guaranteed log(n) time cost for the `containsKey`, `get`, `put` and `remove` operations. – user207421 May 04 '12 at 12:30
  • Without knowing your criteria for assessing which option would be better, answering this question is impossible. Clearly, if you need a sorted collection only `TreeMap` will do. But you already know that. – Raedwald Jun 21 '14 at 10:29
  • 1
    Pretty detailed here: [difference-between-hashmap-linkedhashmap-and-treemap](http://stackoverflow.com/questions/2889777/difference-between-hashmap-linkedhashmap-and-treemap) – nawfal Jun 30 '14 at 14:46
  • The accepted answer says `HashMap` is faster. But the Javadocs for `LinkedHashMap` (Java 8) says that it iterates considerably faster than `HashMap`. So YMMV, depending on your specific criteria. Definitely don't use `TreeMap` unless you need _sorting_, and use `LinkedHashMap` to preserve insertion order. – Lambart Sep 15 '17 at 17:31

3 Answers3

5

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);
  }
}
Keith Randall
  • 22,985
  • 2
  • 35
  • 54
  • 1
    @keith-Can you please tell me, How is hashmap faster than treemap?? Treemap access values on keys sequentially. Can you please tell me how hashmap works?? – Vicky May 04 '12 at 04:58
  • 1
    The answer is longer than will fit in this comment. Take a data structures class, or read up on hash tables and red-black trees on Wikipedia. Hash tables are `O(1)` amortized work per operation, assuming a good hash function. Red-black trees are `O(lg n)` work per operation. – Keith Randall May 04 '12 at 05:28
  • I have tried examples for treemap and hashmap...I entered 100000 entry in map and access them.. I counted time. but result for my programs is treemap-187 hashmap 206 means hashmap requires more time...Got confused, please explain me what is your opinion on this? – Vicky May 04 '12 at 07:12
  • 1
    I don't get the same result. Putting 100000 entries into a map takes about 60 msec for a `HashMap` and 90 msec for a `TreeMap`. I'll post my code. – Keith Randall May 04 '12 at 15:55
  • ok, Have you tried with both sequential and non sequential numbers? – Vicky May 05 '12 at 04:14
0

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).

dhardy
  • 11,175
  • 7
  • 38
  • 46
0

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:

JoaoFCarvalho
  • 11
  • 3