Every keyed operation on TreeMap is O(log n) in the worst case — including the navigation methods like floorKey/ceilingKey. Iteration is O(n). There is no O(1) fast path the way HashMap has, because the data structure is fundamentally a tree.
The table
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| get | O(log n) | O(log n) | O(log n) | tree descent |
| put | O(log n) | O(log n) | O(log n) | descend + at most O(log n) rotations |
| remove | O(log n) | O(log n) | O(log n) | find + recolor/rotate to fix invariants |
| containsKey | O(log n) | O(log n) | O(log n) | same as get |
| containsValue | O(n) | O(n) | O(n) | linear scan; no index on values |
| firstKey / lastKey | O(log n) | O(log n) | O(log n) | leftmost / rightmost descent |
| floorKey / ceilingKey | O(log n) | O(log n) | O(log n) | tree descent with bookkeeping |
| higherKey / lowerKey | O(log n) | O(log n) | O(log n) | strict variants of floor/ceiling |
| subMap / headMap / tailMap | O(1) | O(1) | O(1) | returns a view; no copy |
| iteration (full) | O(n) | O(n) | O(n) | in-order traversal |
| size | O(1) | O(1) | O(1) | cached counter |
A few subtleties
containsValueis O(n) — there's no secondary index on values. Don't rely on it for hot paths.subMapis O(1) but the resulting view'ssize()is O(n) — it has to count by walking, because the backing tree'ssizecounter covers the whole map, not the range.- Range iteration is O(k + log n), where k is the number of entries returned: O(log n) to find the start, plus k tree-successor steps.
putrotations are bounded at O(log n) total in the worst case, but amortised, recolorings happen far more often than rotations — rotations average O(1) per insert in practice.
How does it compare to HashMap?
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| get (avg) | HashMap: O(1) | HashMap: O(1) | TreeMap: O(log n) | HashMap is faster for plain lookup |
| get (worst) | HashMap: O(log n) | TreeMap: O(log n) | Both O(log n) | HashMap's worst case = TreeMap's normal case |
| ordered iteration | TreeMap: O(n) | TreeMap: O(n) | HashMap: needs sort, O(n log n) | TreeMap wins decisively |
| range query | TreeMap: O(log n + k) | TreeMap: O(log n + k) | HashMap: O(n) | HashMap has no native range support |