On Sat, Sep 12, 2015 at 4:51 AM, John Cowan <xxxxxx@mercury.ccil.org> wrote:

Kevin Wortman scripsit:

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

I should have said _dynamic_ perfect hash from the beginning,

or more generally hash table variants which allow deterministic

O(1) time access. I'm not sure what most people "normally" want,

but I've made used Cuckoo hashes where access time was crucial,

while I've never used a static perfect hash.

This is minor compared to the fact that the hash functions don't

take salt as an input. Hash collision attacks are well understood

and have been fixed in Perl [1], and care was taken to fix this in

Chicken's internal hash tables as well [2]. It seems irresponsible

to design an API that prevents such security precautions.

[1] http://blog.booking.com/hardening-perls-hash-function.html

[2] http://lists.nongnu.org/archive/html/chicken-hackers/2012-01/msg00020.html

Alex