-image source

Difference between HashMap, LinkedHashMap and TreeMap

• All three 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.

• Chart by @shevchyk

  ╔══════════════╦═════════════════════╦═══════════════════╦══════════════════════╗
  ║   Property   ║       HashMap       ║      TreeMap      ║     LinkedHashMap    ║
  ╠══════════════╬═════════════════════╬═══════════════════╬══════════════════════╣
  ║              ║  no guarantee order ║ sorted according  ║                      ║
  ║   Order      ║ will remain constant║ to the natural    ║    insertion-order   ║
  ║              ║      over time      ║    ordering       ║                      ║
  ╠══════════════╬═════════════════════╬═══════════════════╬══════════════════════╣
  ║  Get/put     ║                     ║                   ║                      ║
  ║   remove     ║         O(1)        ║      O(log(n))    ║         O(1)         ║
  ║ containsKey  ║                     ║                   ║                      ║
  ╠══════════════╬═════════════════════╬═══════════════════╬══════════════════════╣
  ║              ║                     ║   NavigableMap    ║                      ║
  ║  Interfaces  ║         Map         ║       Map         ║         Map          ║
  ║              ║                     ║    SortedMap      ║                      ║
  ╠══════════════╬═════════════════════╬═══════════════════╬══════════════════════╣
  ║              ║                     ║                   ║                      ║
  ║     Null     ║       allowed       ║    only values    ║       allowed        ║
  ║ values/keys  ║                     ║                   ║                      ║
  ╠══════════════╬═════════════════════╩═══════════════════╩══════════════════════╣
  ║              ║   Fail-fast behavior of an iterator cannot be guaranteed       ║
  ║   Fail-fast  ║ impossible to make any hard guarantees in the presence of      ║
  ║   behavior   ║           unsynchronized concurrent modification               ║
  ╠══════════════╬═════════════════════╦═══════════════════╦══════════════════════╣
  ║              ║                     ║                   ║                      ║
  ║Implementation║      buckets        ║   Red-Black Tree  ║    double-linked     ║
  ║              ║                     ║                   ║       buckets        ║
  ╠══════════════╬═════════════════════╩═══════════════════╩══════════════════════╣
  ║      Is      ║                                                                ║
  ║ synchronized ║              implementation is not synchronized                ║
  ╚══════════════╩════════════════════════════════════════════════════════════════╝
  

Map<String, List<String>> map = new HashMap<String, List<String>>();
if (!hmap.containsKey(keyStr)) hmap.put(keyStr, new ArrayList<String>());
hmap.get(keyStr).add(s);

Differences between HashMap and Hashtable

There are several differences between HashMap and Hashtable in Java:

• Hashtable is synchronized, whereas HashMap is not.

  • This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.

• Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.

• One of HashMap's subclasses is LinkedHashMap, so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn't be as easy if you were using Hashtable.