tim.one at comcast.net
Sun Jun 1 21:19:55 CEST 2003
> i suppose the best idea would be to read the papers...
> ...without doing so, i would guess that they advocate using one-way
> hashes (like those used in cryptography) so that it is difficult to
> find a text that gives a specific hash.
Nope, they advocate picking a *different*-- but still cheap --hash function
every time the program starts. General ways to do this have been studied
extensively, under the general name "universal hashing", starting about 20
years ago. Picking a new hash function requires a little crypto-strength
randomness at the start, so that the hash function being used can't be
guessed from, e.g., the time the program started.
I advocate using app-appropriate data structures instead (e.g., many mapping
gimmicks have worst-case log-time behavior on insertion and lookup, and
aren't vulnerable to any set of keys; OTOH, with very rare exceptions they
have much worse expected-case behavior than hash tables -- pick your poison
based on what's fatal to your app).
More information about the Python-list