Front page | perl.perl5.porters |
Postings from October 2003
> The criteria is too conservative (MJD has done some maths and estimates
> that it should be longest linked list > 1.6)
No no! 1.6 is the length of the *average* list. About 1/4 of the
lists will be longer than this, even in the most typical case.
It's like the average salary in a company. The average salary might
be around $20,000, but it would be very unusual if there weren't a
large number of people paid more than that, and even a few outliers
who were paid a *lot* more.
For a hash with 2^20 = 1048576 buckets and the same number of keys, if
the hash function is working perfectly, we should expect about:
385,749 empty buckets (37 %)
385,749 lists of 1 key each (37 %)
192,875 lists of 2 keys each (18 %)
64,292 lists of 3 keys each ( 6 %)
16,073 lists of 4 keys each ( 1.5%)
3,215 lists of 5 keys each ( 0.3%)
623 lists of 6--10 keys each
For a hash with 2^30 = 1073741824 buckets and the same number of keys,
we should expect to see buckets with up to 13 keys each, and about 10
buckets with 11 keys each, even though the average nonempty bucket
will still have only 1.6 items in it.
Thread Previous