Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java TreeMap firstEntry(): How to Get the First Entry

Learn how to retrieve the lowest-key entry from a Java TreeMap using firstEntry(), with examples, performance notes, empty-map handling, and alternatives such as pollFirstEntry().

~5 min readJava
#TreeMap#Java Collections#SortedMap#First Entry
Diagram showing a red-black tree with the leftmost node highlighted as the first entry, representing the java treemap firstentry operation.

To retrieve the entry with the smallest key from a TreeMap, call firstEntry(). It returns a Map.Entry<K,V> for the lowest key under the map's ordering, or null if the map is empty. This is useful when you need to process items in sorted order, expire the oldest entry, or implement priority-like behavior with a sorted map.

The corresponding firstKey() method returns just the key, but if you need both key and value, firstEntry() avoids an extra lookup.

Below is a minimal example using a TreeMap with natural (alphabetical) ordering:

java
import java.util.TreeMap; import java.util.Map; public class FirstEntryExample { public static void main(String[] args) { TreeMap<String, Integer> scores = new TreeMap<>(); scores.put("alice", 90); scores.put("bob", 85); scores.put("carol", 92); Map.Entry<String, Integer> first = scores.firstEntry(); if (first != null) { System.out.println(first.getKey() + " -> " + first.getValue()); } } }

The output is alice -> 90 because String implements Comparable, and "alice" is the smallest key lexicographically. The code checks for null because the map might be empty; returning null is the contract of firstEntry() in that case.

Understanding TreeMap Ordering

TreeMap maintains its keys in ascending order according to their natural ordering (if keys implement Comparable) or according to a Comparator provided at map creation. The "first" entry is always the one with the lowest key under that ordering. This is guaranteed even if you insert keys in an arbitrary order, because the tree structure keeps the data sorted internally.

For custom key types, you must either implement Comparable or supply a Comparator. Here is how to use a reverse-order comparator so that the "first" entry becomes the highest key in the natural order:

java
import java.util.*; public class ReverseOrderFirst { public static void main(String[] args) { TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder()); map.put(1, "one"); map.put(10, "ten"); map.put(5, "five"); Map.Entry<Integer, String> first = map.firstEntry(); System.out.println(first.getKey() + " -> " + first.getValue()); // 10 -> ten } }

Here, the comparator reverses the natural order, so 10 is placed before 5 in the map's ordering. Understanding the comparator is essential because firstEntry() always returns the element that the map considers smallest under its ordering scheme.

Time Complexity and Performance

firstEntry() runs in O(log n) time, where n is the number of entries in the map. TreeMap is based on a red-black tree, and the smallest entry is stored at the leftmost node. The method follows left-child references from the root, so the cost is proportional to the tree height, which is O(log n).

If you only need the first entry, firstEntry() is clearer than using an iterator:

java
// Works, but less clear and throws NoSuchElementException on an empty map Map.Entry<String, Integer> first = scores.entrySet().iterator().next();

Using an iterator is less readable and does not handle an empty map gracefully. It is more natural when you are already iterating the entry set. For a single first-entry lookup, prefer firstEntry().

For repeated accesses that also remove the first entry, use pollFirstEntry(), which removes and returns the entry in one operation. This is common in caching eviction scenarios where you need to expire the smallest key.

java
Map.Entry<String, Integer> evicted = scores.pollFirstEntry(); if (evicted != null) { // process evicted entry }

pollFirstEntry() also runs in O(log n) because it removes the leftmost node and then rebalances the tree.

Common Pitfalls When Using firstEntry()

A common mistake is forgetting that firstEntry() returns null on an empty map. Many developers expect an exception, but calling getKey() on a null result produces a NullPointerException. Always check for null, as shown in the examples.

Another subtle issue arises when using a Comparator that is inconsistent with equals(). The firstEntry() method relies on the comparator to determine ordering. If the comparator returns 0 for keys that are not equal, the map may treat those keys as duplicates and discard later insertions. This can lead to unexpected "first" entries. Ensure your comparator is consistent with equals to avoid such anomalies.

Also, do not assume the Map.Entry returned by firstEntry() is a live view that supports updating the map through setValue(). If you need to change a value, use put() with the key and the new value.

Advanced Usage: Navigating from the First Entry

TreeMap provides a family of navigation methods that are useful when you need to traverse the map in sorted order. Besides firstEntry(), you have lastEntry(), lowerEntry(), floorEntry(), ceilingEntry(), and higherEntry(). These allow you to move forward and backward without iterating the entire map.

For example, to process entries in ascending order starting from the first, you can combine firstEntry() with a loop using higherEntry():

java
Map.Entry<String, Integer> current = scores.firstEntry(); while (current != null) { System.out.println(current.getKey() + " = " + current.getValue()); current = scores.higherEntry(current.getKey()); }

This is useful when you need to skip entries or jump to specific keys; each higherEntry() call is O(log n). For a complete traversal in sorted order, iterating entrySet() is simpler.

When to Use firstEntry() vs Other Approaches

If you need the smallest key and value only once, firstEntry() is the clearest choice. If you need to repeatedly remove the smallest entry, pollFirstEntry() is better. If you need to iterate all entries in order, use an enhanced for loop on entrySet(); it is simpler than calling navigation methods repeatedly.

Here is a comparison in tabular form:

OperationMethodTime ComplexityReturnsEmpty Map Behavior
Get first entry (not remove)firstEntry()O(log n)Map.Entry or nullReturns null
Get first key onlyfirstKey()O(log n)Key or throwsThrows NoSuchElementException
Get and remove first entrypollFirstEntry()O(log n)Map.Entry or nullReturns null
Iterate all entriesentrySet()O(n) to iterateIteratorEmpty iterator

Choose based on whether you need both key and value, whether you want to remove the entry, and whether the map could be empty. Prefer methods that return null on an empty map over those that throw exceptions unless you specifically want an error.

Edge Cases with null Keys and Non-Comparable Keys

TreeMap cannot use null keys with natural ordering, because null cannot be compared by a Comparable. Inserting a null key under natural ordering throws NullPointerException. If you supply a custom comparator, it may permit null keys, but the ordering must be well defined; otherwise results such as firstEntry() can be surprising. Avoid null keys unless your comparator explicitly handles them.

If your key type does not implement Comparable and you do not provide a Comparator, the map cannot compare keys and throws ClassCastException when a comparison is needed. For example, after inserting keys, calling firstEntry() will trigger that comparison. Make your keys comparable or supply a comparator.

Production Considerations and Concurrency

TreeMap is not thread-safe. If multiple threads access the map and at least one modifies it, you must synchronize externally. To keep TreeMap's navigation methods and still synchronize individual calls, wrap it with Collections.synchronizedNavigableMap:

java
NavigableMap<String, Integer> syncMap = Collections.synchronizedNavigableMap(new TreeMap<String, Integer>());

This synchronization only guarantees atomicity for each individual method call, not for compound actions like "check if empty and then call firstEntry." For compound operations, synchronize explicitly on the map or use ConcurrentSkipListMap, which provides a thread-safe sorted map with similar navigation methods. ConcurrentSkipListMap also has firstEntry() and pollFirstEntry(), with the same null-on-empty behavior.

For concurrent read-heavy access, ConcurrentSkipListMap often avoids the overhead of external locking. The tradeoff is additional memory overhead and different performance characteristics, so choose it when concurrent access is expected.

Conclusion

firstEntry() gives you direct access to the least entry in a TreeMap without scanning the whole map. Check for null on empty maps, understand the comparator's ordering, and use pollFirstEntry() when you need to remove as well. For concurrent access, guard the TreeMap or use ConcurrentSkipListMap.

Try matching browser tools

All tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.