[java] What is the difference between a HashMap and a TreeMap?

I'll talk about the HashMap and TreeMap implementation in Java:

• HashMap -- implement basic map interface

  1. implemented by an array of buckets, each bucket is a LinkedList of entries
  2. running time of basic operations: put(), average O(1), worst case O(n), happens when the table is resized; get(), remove(), average O(1)
  3. not synchronized, to synchronize it: Map m = Collections.synchronizedMap(new HashMap(...));
  4. Iteration order of the map is unpredictable.

• TreeMap -- implement navigable map interface

  1. implemented by a red-black tree
  2. running time of basic operations: put(), get(), remove(), worst case O(lgn)
  3. not synchronized, to synchronize it: SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
  4. provide ordered iteration. higherKey(), lowerKey() can be used to get the successor and predecessor of a given key.

To sum, the biggest difference between HashMap and TreeMap is that TreeMap implements NavigableMap<K,V>, which provide the feature of ordered iteration. Besides, both HashMap and TreeMap are members of Java Collection framework. You can investigate the source code of Java to know more about their implementations.