8

I'm pretty new to the Java World (since I'm writing primary in C/C++). I'm using maps in my apps. Since java.util.Map is abstract I need to instantiate it's implementation. Usually I use HashMap like:

Map<String, MyClass> x = new HashMap<>();

But in java docs I found many other implementations, like TreeMap, LinkedHashMap, HashTable, etc. I want to know if I can continue blindly using of the HashMap or there are any important differences between those Map implementations.

The brief list of points-to-know will be ok. Thanks.

11
  • 6
    Have you checked the javadoc for those classes?
    – OpenSauce
    Dec 20, 2012 at 14:21
  • 2
    So, there's this company called Google...
    – Isaac
    Dec 20, 2012 at 14:22
  • 1
    I have to downvote, just for this comment There are too much to read. I'll read it anyway, but for now I need a quick answer like a brief list of difference.
    – Perception
    Dec 20, 2012 at 14:27
  • 2
    @Isaac sure. If it is a duplicate then it's my fault. Perception: official docs is a must read for all who uses the language. But once again, I'm not a Java programmer, I just need to rewrite a small piece of code. And do it quickly. I don't want to do it blindly but doesn't have enough time right know to read and (it is more important) to understand what I read in the official docs. I'm sorry if this makes your sad.
    – maverik
    Dec 20, 2012 at 14:35
  • 1
    @maverik, note that my comment was written before you explained this situation of yours. From the initial looks of it, it was seen as if you're too lazy to do some research. No offence meant, clearly. Cheers
    – Isaac
    Dec 20, 2012 at 14:39

5 Answers 5

12
  • Never bother with Hashtable, it's a relic from Java 1.0;
  • HashMap is the universal default due to O(1) lookup and reliance only on equals and hashCode, guaranteed to be implemented for all Java objects;
  • TreeMap gives you sorted iteration over the map entries (plus a lot more—see NavigableMap), but requires a comparison strategy and has slower insertion and lookup – O(logN) – than HashMap;
  • LinkedHashMap preserves insertion/access order when iterating over the entries.

SortedMap implementations offer some great features, like headMap and tailMap. NavigableMap implementations offer even more features with terrific performance for operations that assume sorted keys.

Further out there are java.util.concurrent map implementations, like ConcurrentHashMap, which offer great concurrent performance and atomic get/put operations.

10
  • Another thing about TreeMap, it implements SortedMap Dec 20, 2012 at 14:21
  • Thank you and all others. That's what I'm looking for.
    – maverik
    Dec 20, 2012 at 14:26
  • 2
    HashMap lookup is not O(1) - this heavily depends on the hash function and is in worst case O(n). See the for loop in the sources of get - hg.openjdk.java.net/jdk6/jdk6/jdk/file/a42d6999734b/src/share/… Dec 20, 2012 at 14:31
  • @SpaceTrucker It also sports a rehashing function that is applied to object's own hashCode, which mitigates these issues to a great extent. Dec 20, 2012 at 14:33
  • @MarkoTopolnik it doesn't change the fact that complexity is not O(1). Dec 20, 2012 at 14:34
2
  • HashMap use it almost all the time. Note that your object need have proper implementation of equals and hashCode methods. Does not save insertion order.
  • HashTable don't use it never.
  • LinkedHashMap the same as HashMap but saves insertion order. Large overhead.
  • TreeMap support natural ordering. But insertion works in O(logn).
2

I mostly use HashMap or ConcurrentHashMap if I need it to be thread safe

1

There of course are important differences between each of these maps. It depends purely on what you are trying to do. If you recall a HashMap becomes pretty useless (see inefficient) when you have a poor hashing function in place. The LinkedHashMap is a HashMap that is backed by a doubly linked list, so you can iterate over it. You would eat the overhead that is associated with a linked list of course. TreeMap keeps elements in order, so you will eat that overhead. HashTable is a synchronized collection, that is generally avoided.

0

are any important differences between those Map implementations

Yes there are some major differences to consider when choosing an implementation of Map.

  • Concurrency
    Will you be manipulating this map across threads?
  • NULLs
    Do you want to accept, or reject, NULL pointers as key and/or value?
  • Sorting
    Do you want map entries put in some order, such as sorted order or original-insertion order? Do you want support for the SortedMap/NavigableMap interfaces?
  • Not Modifiable
    Do you want a map to be frozen, refusing to accept or remove entries?
  • Identity
    Do want to compare keys based on reference-equality or object-equality?
  • Efficiency
    Do you want to take advantage of the very fast performance and very little memory used when your key is an enum?
  • Literals
    Do you want the convenience of declaring and populating a map in a single line of code?
  • Legacy
    Do you want to avoid using a legacy map, created before the modern Java Collections Framework?

Here is a graphic table I made comparing the features of each of the ten Map implementations bundled with Java 11.

Table comparing the features of the ten implementations of <code>Map</code> bundled with Java 11.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.