HashMap vs TreeMap: differences, operation complexity, when to use?

HashMap vs TreeMap:

• HashMap:

  • Based on a hash table.
  • Insertion, deletion, and search operations — on average O(1).
  • Does not guarantee the order of elements.
  • Allows null as a key.

• TreeMap:

  • Based on a red-black tree (self-balancing tree).
  • Insertion, deletion, and search operations — O(log n).
  • Stores elements in sorted order by key.
  • Does not allow null as a key (throws NullPointerException).

When to use:

• If fast arbitrary sampling and order are not important — HashMap.
• If a sorted order of keys is needed, or navigation by ranges (e.g., subMap, headMap) is required — TreeMap.

Example of using TreeMap to store an iterable sorted dictionary:

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "three");
treeMap.put(1, "one");
treeMap.put(2, "two");

for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}
// Output will be in key order: 1, 2, 3