Nowadays I expected an opaque dictionary to be amortized O(1).

Granted, one can technically call that O(log(n)), but that's not a helpful categorization.