2

I am preparing for software interviews and i am stuck with a question for days now.

I have not been able to figure out the difference between linkedhashmap, map, hashtable, hashmap present in the Java Collection API.

Do all of these have the same get and put complexities? I know that map is the interface class and hashmap, hashtable, linkedhashmap implement this interface. So does that mean that the inner implementation of these 3 classes is the same? How are they implemented in the collections api?

Thanks in Advance!!!

Amm Sokun
  • 1,298
  • 4
  • 20
  • 35
  • use LinkedHashMap, it is basically a linked list it very fast search. HashMap is a bad impl of a hash table (tree based, pow2 buckets size) it's worse on iteration and mediocre on search. Hashtable is the oldest impl. w/ some synchronizations. IdentityHashMap is what a hashtable impl should be, alas it is only for identity (==) and identityHashcode – bestsss Jun 17 '11 at 07:53

3 Answers3

14

I doubt the differences can be explained significantly better than what's already written in the JavaDocs for these classes:

  • Map is the basic interface common to all these classes
  • a Hashtable is one implementation of that interface, for the "old" days when it was thought that having everything synchronized is a good idea (ref. Vector). It offers "kind of" thread-safety, if you know what you are doing. If you are serious about a map which can be used from multiple threads you should absolutely check out the ConcurrentHashMap and ConcurrentSkipListMap.
  • a HashMap is almost the same as a Hashtable, but with the synchronization removed. It's the preferred general-purpose Map implementation.
  • a LinkedHashMap additionally maintains a linked list of it's entries, which allows to maintain an ordering or use it as a LRU cache easily, just read the JavaDoc.

All of the aforementioned Map implementations have their basic get/put operations in (amortized) O(1) time complexity. There are minor differences in the handling of null values, it's inevitable to check the JavaDoc for details.

To get an idea of how these classes are implemeted, have a look at their inheritance tree:

  • Map (just the interface)
    • Dictionary (obsoleted abstract class)
      • Hashtable (the "old" map implementation lives on it's own)
    • AbstractMap (the basic functionality of the "new" map implementations)
      • HashMap (the first concrete map implementation for general purpose use)
        • LinkedHashMap (extends HashMap by mainaining the linked list)
Waldheinz
  • 10,399
  • 3
  • 31
  • 61
  • 1
    Hashtable extends Dictionary btw. Dictionary is a quite useless now abstract class, no one pays attention at. The difference between the HashMap and Hashrable (beside the obvious sync) is the size of the bucket array. HashMap uses a pow2 and can utilize `hash&(table.length-1)` which is faster than Hashtable `(hash & 0x7FFFFFFF) % tab.length` – bestsss Jun 17 '11 at 08:19
  • can a abstract class implement an interface? – Amm Sokun Jun 17 '11 at 08:42
  • @Amm Yes, you can make every class abstract, event if it does not have any abstract methods at all. – Waldheinz Jun 17 '11 at 08:44
  • Also i thought the table length is ideally prime? – Amm Sokun Jun 17 '11 at 08:45
  • 2
    @Amm, in the simple case yes, but [`HashMap` has been reimplemented in Java4](http://www.javaspecialists.eu/archive/Issue054.html), to use a more tricky algorithm which requires that the map size is always a power of 2. – Péter Török Jun 17 '11 at 08:49
7

They all honor the same contract, but there are some differences in the implementation:

  • LinkedHashMap : keys are maintained in insertion order
  • HashTable : all operations are synchronized, no ordering guarantees
  • HashMap : no ordering guarantees, best performance

Generally, the best practice is to use Map as the type for variables, and then you instantiate an implementing type based on the needs of your code. HashMap is generally preferred unless you need some ordering guarantees, in which case LinkedHashMap or TreeMap are good choices.

stevevls
  • 10,675
  • 1
  • 45
  • 50
  • stevevls, HashMap is worse on iteration than LinkedHashMap and for being fast: it's a tree based hash table which sucks on nowadays hardware – bestsss Jun 17 '11 at 07:52
  • @bestsss I'm pretty sure a `HashMap` is *not* tree based, only the `TreeMap` is. – Waldheinz Jun 17 '11 at 08:05
  • 1
    @Waldheinz, then you do NEED to check again. I am absolutely sure it is. it's an array of buckets and each collision is a linked list, the entire structure is a tree, albeit not binary but hell of a tree. So, you aint sure. The other popular option for hashing is linear probe which outperforms tree-based quite nicely. – bestsss Jun 17 '11 at 08:14
  • @bestsss You are right, the lists attached to the buckets might indeed hurt locality. +1 for the insight. – Waldheinz Jun 17 '11 at 08:42
  • In STL, map is implemented as a Self balancing binary tree....i wonder what is the need to use tree? \ – Amm Sokun Jun 17 '11 at 08:43
  • Also HashMap allows for NULL key values while HashTable doesnt – Amm Sokun Jun 17 '11 at 09:00
  • @Amm, self-balancing (like red-black, ALV) is not a hashing tree and doesn't use hash at all, Java version is TreeMap (red-black w/o nil nodes) – bestsss Jun 17 '11 at 09:45
  • 1
    @Waldheinz, yes there are a few more indirections that needed. 1st the bucket (Map.Entry) itself can be omitted and just use Object[] w/ Key/Value neightbours. That removes allocations on put and removes the indirection on get. Traversing is much faster too (it's basically traversing an ArrayList) and so on. – bestsss Jun 17 '11 at 09:49
0

All classes implement the Map interface and offer mostly the same functionality. The most important difference is the order in which iteration through the entries will happen:

HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added. TreeMap will iterate according to the "natural ordering" of the keys according to their compareTo() method (or an externally supplied Comparator). Additionally, it implements the SortedMap interface, which contains methods that depend on this sort order. LinkedHashMap will iterate in the order in which the entries were put into the map "Hashtable" is the generic name for hash-based maps. In the context of the Java API, Hashtable is an obsolete class from the days of Java 1.1 before the collections framework existed. It should not be used anymore, because its API is cluttered with obsolete methods that duplicate functionality, and its methods are synchronized (which can decrease performance and is generally useless). Use ConcurrrentHashMap instead of Hashtable.

jigar
  • 307
  • 2
  • 11