For small values of n ;)
A tree of maps would be consistently log(n), like any map. Even a hashtable would hash to buckets eventually, and are log(n).
Honestly, I have no idea why people aren't taught Cuckoo-maps by default. It's simple, has true O(1) worst-case lookup, and has easy deletion. About the only problem is trying to prove insertion time.
For small values of n ;)
A tree of maps would be consistently log(n), like any map. Even a hashtable would hash to buckets eventually, and are log(n).