Kevin Wortman scripsit:

> an operation that takes O(1) deterministic time may also be
> said to take O(1) amortized time.

"[...] You must give three crosses to two or three pictures.  You must
give two crosses to four or five —"

"Do you mean *only* two crosses?" said Clara.  "Or may I count the
three-cross pictures among the two-cross pictures?"

"Of course you may", said her aunt.  "Anyone that has *three* eyes,
may be said to have *two* eyes, I suppose?"

    —Lewis Carroll, _A Tangled Tale_, Knot 5

<https://ebooks.adelaide.edu.au/c/carroll/lewis/tangled/knot5.html>

> So the requirements don't forbid O(1)
> deterministic operations.

No indeed.  However, generating a perfect hash takes essentially unbounded
time, which is forbidden by the constraints.  My feeling is that perfect
hash tables are a different thing from ordinary hash tables: you normally
want all possible keys delivered to the library when the hash table is
created, rather than through ad hoc mutations..

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
When I wrote it I was more than a little febrile with foodpoisoning
from an antique carrot that I foolishly ate out of an illjudged faith
in the benignancy of vegetables.  --And Rosta