scala/scala — pull request #61 by axel22 (2011-12-19 15:51:33+00:00)
Title: Fix #5293 - changed the way hashcode is improved in hash sets.

The hash code is further improved by using a special value in the hash sets
called a `seed`. For sequential hash tables, this value depends on the size
of the hash table. It determines the number of bits the hashcode should be
rotated. This ensures that hash tables with different sizes use different
bits to compute the position of the element. This way traversing the elements
of the source hash table will yield them in the order where they had similar
hashcodes (and hence, positions) in the source table, but different ones in
the destination table.

Ideally, in the future we want to be able to have a family of hash functions
and assign a different hash function from that family to each hash table
instance. That would statistically almost completely eliminate the possibility
that the hash table element traversal causes excessive collisions.

I should probably @mention extempore here.