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)
|
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