Did the benchmarks again using 100,000 keys while allocating 200,000 keys and the difference did start to show a bit more.

Benchmark: timing 10 iterations of with, without...
      with: 17 wallclock secs (13.56 usr +  0.24 sys = 13.80 CPU) @  0
+.72/s (n=10)
   without: 17 wallclock secs (15.34 usr +  0.02 sys = 15.36 CPU) @  0
+.65/s (n=10)
[download]

Tried it using the rand idea, but after 100000 repetitions it had only alocated 20469/32768 buckets and the benchmarks weren't different at all... Also tried even more keys, but started getting (Out of memory) errors. :-) Thanks for the responses