TreeMap vs HashMap

A sorted map in Java is based on a Red-Black Tree (balanced BST): ordered keys, $O(\log n)$ per operation. The hash-based map provides expected $O(1)$ without key order.

If you need range queries or sorted iteration, use the tree-based map. If you only need membership based on equals/hashCode, the hash-based variant is often sufficient.

Check the search-tree invariant: Validate Binary Search Tree [1].

Where used

Hash-based map: expected constant membership without order. Tree map: sorted keys, range queries (subMap), stable iteration. Caches and session maps are often hash-based; financial/time series keys are often kept as ordered trees.

Depth

An ordered tree-based map keeps keys sorted according to a comparison relation. This enables it to support range queries, next keys, and ordered iteration with path length-dependent costs.

A hash-based map distributes keys into buckets and provides very short expected access times with good distribution. However, it does not maintain any specific key order and cannot directly answer range queries.

The choice therefore depends not only on average lookup time. Comparison costs, hash quality, required order, mutable keys, and worst-case requirements are part of the operational profile.

Difficulty levels

1. Distinguish between point queries and range queries.
2. Separate expected costs from guaranteed ordered performance.
3. Justify an appropriate mapping principle for a specific API.

Pitfalls

Natural order and equals may form different equality classes. In hash-based storage, subsequently modified keys can damage discoverability.