I also do not understand why using different data structures is not under consideration. There are many algorithms and data structures for handling collisions so that hash table access remains efficient even with a high rate of collisions. Why not have the option to choose the data structure for buckets -- if you don't like alists, there are balanced trees, dynamic arrays, and others.
On Jan 1, 2012 11:57 PM, "John Cowan" <
address@hidden> wrote:
Peter Bex scripsit:
> Agreed. Changing datastructures is not an option.
Why not? It's a matter of replacing a datastructure whose worst-case
cost is quadratic with one whose worst-case cost is linear. Do we even
know what the break-even point is between a-lists with their higher
algorithmic complexity vs. hash tables with their higher constant
factors? I tried writing a little benchmark to determine this, but so
far without success.
> The patch ensures no two hash tables use the same offset, so even
> if the hash value of a given table were to leak out (which the user
> still should take every precaution to avoid!), it won't compromise the
> randomization of other hash tables.
What you are doing is imposing an additional cost on *all* users of hash
tables so as to make them more resistant to malicious attack. The vast
majority of hash tables do not need to deal with malicious data.
> > Once I know, I'll estimate the cost to fix it to save my brain
> > from remebering that I'm not supposed to use hash tables where
> > appropriate because they could degenerate into an issue.
>
> Indeed. If other languages have fixed it transparently, so can we.
We aren't Perl or Python, where hash tables are deeply embedded in
the implementation. Using a hash table in Scheme should always be an
informed choice, not a default one. Right now the information is lacking.
--
John Cowan address@hidden http://ccil.org/~cowan
I am he that buries his friends alive and drowns them and draws them
alive again from the water. I came from the end of a bag, but no bag
went over me. I am the friend of bears and the guest of eagles. I am
Ringwinner and Luckwearer; and I am Barrel-rider. --Bilbo to Smaug
_______________________________________________
Chicken-hackers mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/chicken-hackers