[plt-scheme] Hash Table implementation

At Fri, 3 Aug 2007 13:18:55 -0400, "David Einstein" wrote:
> Inspired by Jens and Grant, I decided to try my hand at some of the Project
> Euler problems using PLT scheme, to see what it was capable of.  It has
> proven itself capable on the few problems that I have completed so far, but
> I just ran into what appears to be a bug of sorts.  It appears that the
> hash-table implementation does not expand as more keys are added, and so if
> the table reaches a certain size things slow down dramatically.

It does expand, but there seems to be an issue with the hashing
function for rationals.

If I add

 (let ([v (make-vector 10)])
   (vector-set-performance-stats! v)
   (printf "~s ~s\n" (vector-ref v 8) (vector-ref v 9)))

to the end of the program and run only the 100000 example, I see

  223979 136477950

The first number means 223K hashes --- which is about right,
considering hat the table is re-hashed each time it grows. But the
second number means around 1k steps to find an empty bucket (for double
hashing), which is clearly too many.

In contrast, if I add `string->number' to the result of `randfrac', I
see

  224001 175341

which is about as many hashes (of course), but less than 1 extra step
per key to find an empty bucket, which is the way it's supposed to be.

Offhand, I'm not sure why the hash function for exact rationals turns
out to be so bad, but I can try to tune it.

Matthew