TreeMap

A Red-Black tree based NavigableMap implementation.

For the containsKey, get, put and remove operations, TreeMap guarantees log(n) time cost. While HashMap implements these four operation with O(1) time complexity. So when acting as a traditional hash table, TreeMap is slower than HashMap.

However, TreeMap has its own advantages. It’s not just a simple Map, but a SortedMap. It provides methods to get lowest and greatest key/entry more efficient than HashMap.

  • firstEntry() / firstKey() / pollFirstEntry(), to return/remove lowest key or entry.
  • lastKey() / lastEntry() / pollLastEntry(), for greatest key or entry.

To get the lowest or greatest, HashMap does it in O(n) time cost, while TreeMap only needs O(logn). (TreeMap keeps going left or right to retrieve the lowest or greatest.)

  // TreeMap source code
  final Entry<K,V> getFirstEntry() {
      Entry<K,V> p = root;
      if (p != null)
          while (p.left != null)
              p = p.left;
      return p;
  }

Check TreeMap Javadoc for more details.

PriorityQueue

An unbounded priority queue based on a priority heap.

The head of this queue is the least element with respect to the specified ordering.

So, for retrieving the lowest, PriorityQueue is faster than TreeMap. PriorityQueue provides O(1) time cost, while TreeMap provides log(n).

  // PriorityQueue source code
  public E peek() {
      return (E) queue[0];
  }

For removing the lowest in a PriorityQueue, it’s an O(logn) operation, which is same as doing it a TreeMap.

As its name indicates, PriorityQueue is a better choice when it’s used as a priority queue, that is, letting the lowest one be in the front of the queue. Retrieving the lowest, removing it and letting the next lowest value be in the front of the queue are fast, which are O(logn) operations.

However, if sometimes we need to remove an arbitrary entry, not the lowest entry, and want to retrieve the lowest fast, in this case, TreeMap provides a better overall performance than PriorityQueue. For example, we have a composite operation which has the following operations.

  1. Add a new entry.
  2. Remove some existed entry, not the lowest.
  3. Retrieve the lowest entry.

For PriorityQueue, the second step is the slowest operation, which is O(n). So, the overall time cost of the composite operation using PriorityQueue is O(n). While using TreeMap, all three steps cost O(logn), so the overall time cost is O(logn).

Check PriorityQueue Javadoc for more details.