hash functions and other comments Alex Shinn (08 Sep 2015 06:19 UTC)
Re: hash functions and other comments John Cowan (08 Sep 2015 12:57 UTC)
Re: hash functions and other comments Alex Shinn (08 Sep 2015 13:32 UTC)
Re: hash functions and other comments John Cowan (08 Sep 2015 14:59 UTC)
Re: hash functions and other comments Alex Shinn (09 Sep 2015 04:29 UTC)
Re: hash functions and other comments John Cowan (09 Sep 2015 13:18 UTC)
Re: hash functions and other comments Alex Shinn (10 Sep 2015 02:09 UTC)
Re: hash functions and other comments John Cowan (10 Sep 2015 03:46 UTC)
Re: hash functions and other comments Arthur A. Gleckler (10 Sep 2015 03:56 UTC)
Re: hash functions and other comments Alex Shinn (10 Sep 2015 10:05 UTC)
Re: hash functions and other comments Kevin Wortman (11 Sep 2015 19:01 UTC)
Re: hash functions and other comments John Cowan (11 Sep 2015 19:51 UTC)
Re: hash functions and other comments Alex Shinn (12 Sep 2015 06:29 UTC)
Re: hash functions and other comments John Cowan (12 Sep 2015 22:16 UTC)
Re: hash functions and other comments Alex Shinn (15 Sep 2015 03:23 UTC)
Re: hash functions and other comments John Cowan (15 Sep 2015 11:31 UTC)
Re: hash functions and other comments Alex Shinn (15 Sep 2015 12:57 UTC)
Re: hash functions and other comments Alex Shinn (16 Sep 2015 03:01 UTC)

Re: hash functions and other comments John Cowan 11 Sep 2015 19:51 UTC

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