My understanding is that "deterministic O(1) time" means that an operation always takes O(1) time, while "amortized O(1) time" means that any sequence of k operations takes O(k) total time, for an average of O(1), with nothing said of how evenly distributed the time consumption is. Under those definitions, an operation that takes O(1) deterministic time may also be said to take O(1) amortized time. So the requirements don't forbid O(1) deterministic operations.

However, these definitions don't seem to be universally accepted, so perhaps the spec should be more explicit about this.

It's true that some hash table implementations can guarantee O(1) deterministic time on either insertion or deletion, and that implementers ought to be able to pursue that.

Kevin Wortman