This Table is created after the code has been done to see any missing API which has not been optimized. This also demonstrates the architecture little info to see in detail you need to read the code.
N = Elements in tree. B = Branching factor (Degree).
All Auxiliary Space must be O(1) (zero-allocation).
| Method | Time Complexity | Space Complexity | ChaosTree Optimization Implementation |
|---|---|---|---|
size() |
O(1) | O(1) | Reads cached size variable. Instantaneous return. |
isEmpty() |
O(1) | O(1) | Checks size == 0. |
containsKey(K key) |
O(log_B N) | O(1) | Standard B-Tree descent with internal array binary search. |
containsValue(V value) |
O(N) | O(1) | Scans sequentially via optimized leaf pointers, bypassing full tree traversal overhead. |
get(K key) |
O(log_B N) | O(1) | Internal array binary search within nodes. |
put(K key, V value) |
O(log_B N) | O(1) | Node splitting handled in-place with zero-allocation. |
remove(K key) |
O(log_B N) | O(1) | Merging and borrowing handled in-place with zero-allocation. |
putAll(Map m) |
O(M log_B N) | O(1) | Standard iterative insertion. For O(N+M) performance, use Dragon Feed builder. |
clear() |
O(1) | O(1) | Unlinks root and resets size. GC handles cleanup asynchronously. |
keySet(), values(), entrySet() |
O(1) | O(1) | Returns pre-instantiated lightweight view objects. Zero data copied. |
firstKey(), firstEntry() |
O(log_B N) | O(1) | Follows highly optimized left-most path. |
lastKey(), lastEntry() |
O(log_B N) | O(1) | Follows highly optimized right-most path. |
lowerKey(), lowerEntry() |
O(log_B N) | O(1) | Exact nearest-neighbor search. |
floorKey(), floorEntry() |
O(log_B N) | O(1) | Exact nearest-neighbor search. |
ceilingKey(), ceilingEntry() |
O(log_B N) | O(1) | Exact nearest-neighbor search. |
higherKey(), higherEntry() |
O(log_B N) | O(1) | Exact nearest-neighbor search. |
pollFirstEntry() |
O(log_B N) | O(1) | Combines firstEntry() + remove() in optimized pass. |
pollLastEntry() |
O(log_B N) | O(1) | Combines lastEntry() + remove() in optimized pass. |
subMap(), headMap(), tailMap() |
O(1) | O(1) | Constructs a view wrapper instantly. Zero data copied. |
descendingMap() |
O(1) | O(1) | Constructs a view wrapper instantly. |
navigableKeySet(), descendingKeySet() |
O(1) | O(1) | View wrapper around existing Map views. |
| Method | Time Complexity | Space Complexity | ChaosTree Optimization Implementation |
|---|---|---|---|
getOrDefault() |
O(log_B N) | O(1) | Single lookup pass. |
forEach(BiConsumer) |
O(N) | O(1) | Iterates natively via leaf links. Avoids Map.Entry allocation overhead. |
replaceAll(BiFunction) |
O(N) | O(1) | Updates values in-place sequentially. |
putIfAbsent() |
O(log_B N) | O(1) | Optimized: Uses internal single-pass putInternal. Eliminates double traversal. |
remove(key, value) |
O(log_B N) | O(1) | Single pass lookup + equality check before removal. |
replace(key, value) |
O(log_B N) | O(1) | Single pass. |
replace(key, oldV, newV) |
O(log_B N) | O(1) | Single pass. |
computeIfAbsent() |
O(log_B N) | O(1) | Optimized: Custom single-pass descent. Does not rely on AbstractMap's slow two-pass default. |
computeIfPresent() |
O(log_B N) | O(1) | Single pass modification. |
compute() |
O(log_B N) | O(1) | Single pass modification. |
merge() |
O(log_B N) | O(1) | Single pass modification. |
Creating a view is always O(1). However, operating on the view has different complexities.
| View Method | Time Complexity | Space Complexity | ChaosTree Optimization Implementation |
|---|---|---|---|
SubMap.size() |
O(K) | O(1) | K = elements in range. Iterates the bounded range to count elements (JDK matching behavior). |
SubMap.get(K) |
O(log_B N) | O(1) | Standard descent + O(1) boundary check. |
SubMap.put(K, V) |
O(log_B N) | O(1) | Standard put + O(1) boundary check. Throws IllegalArgumentException if out of bounds. |
GlobalKeySet.size() |
O(1) | O(1) | Delegates to outer map size(). |
GlobalKeySet.contains(K) |
O(log_B N) | O(1) | Delegates to outer map containsKey(). |
ValuesView.contains(V) |
O(N) | O(1) | Delegates to outer map containsValue(). Scans entire tree sequentially. |
EntrySet.contains(Entry) |
O(log_B N) | O(1) | Looks up key, then checks value equality natively. |