> On 13 Jan 2016, at 19:31, Nicolas Cellier > <[email protected]> wrote: > > Note that Squeak has reduced the number of collisions for floats by not > erasing the most significant bits of each word. > I've tested the squeak implementation with Andres Valloud tool in VW, it does > not perform so bad for the sets I tested in term of collisions... > > Float>>hash > "Hash is reimplemented because = is implemented. Both words of the float > are used. (The bitShift:'s ensure that the intermediate results do not become > a large integer.) Care is taken to answer same hash as an equal Integer." > > (self isFinite and: [self fractionPart = 0.0]) ifTrue: [^self truncated > hash]. > ^ ((self basicAt: 1) bitShift: -4) + > ((self basicAt: 2) bitShift: -4) > > I also changed Fraction to use a hashMultiply and made a more explicit > isAnExactFloat test. > > Fraction>>hash > "Hash is reimplemented because = is implemented." > > "Care is taken that a Fraction equal to a Float also has an equal hash" > self isAnExactFloat ifTrue: [^self asExactFloat hash]. > > "Else, I cannot be exactly equal to a Float, use own hash algorithm." > ^numerator hash hashMultiply bitXor: denominator hash > > Fraction>>isAnExactFloat > "Answer true if this Fraction can be converted exactly to a Float" > ^ denominator isPowerOfTwo > and: ["I have a reasonable significand: not too big" > numerator highBitOfMagnitude <= Float precision > and: ["I have a reasonable exponent: not too small" > Float emin + denominator highBitOfMagnitude <= Float > precision]] > > Fraction>>asExactFloat > "When we know that this Fraction is an exact Float, this conversion is > much faster than asFloat." > > ^numerator asFloat timesTwoPower: 1 - denominator highBit > > Not that Fraction should allways be reduced (this is an invariant of the > class, I hope well defined in class comment). > > Integer hash is not that good because the risk of occupying consecutive > buckets is high... I wonder if returning ^self hashMultiply would not arrange > things here and reduce the requirements for spreading hashMultiply everywhere > else?
The risk does not really lie in occupying consecutive buckets. The risk is rather that integers used as keys could have a pattern that cause bucket collisions. For example, if all key are multiple of 100, and the bucket count is 2, 4, 5, 10, 20, 25 or 50. It would make more sense to solve this problem by using multiplyHash in the bucket data structure classes, instead of having to pay this computation cost in SmallInteger. Also, using it in SmallInteger would not dispense from using it in the #hash method of classes that use SmallInteger, because it matters that each component of the hash is processed a different number of times by multiplyHash.
