Data.HashTable.hashInt seems somewhat sub-optimal

[Jan-Willem Maessen]

On Aug 30, 2007, at 9:56 AM, <Simon.Frankau at barclayscapital.com> wrote:

> Jan-Willem Maessen wrote:
>> Sigh.
>>
>> I've included a fix below, but I don't have a standard GHC checkout
>> available to me (only the test sandbox I used to get the code in the
>> first place) so I haven't generated a patch.  Note the mentioned
>> "reasonability tests", which hopefully should forestall such obvious
>> infelicities in future.
>
> Hi.
>
> Sorry to be a bit negative, but I don't think the hash function you
> suggest is good for a number of reasons:
>
> 1) I don't think you're implementing the algorithm Thorkil Naur
> suggests. I believe (although I haven't had the time to check) that  
> the
> scheme is equivalent to using the output of mulLo, not mulHi. So, we
> lose whatever theoretical underpinnings the original has.

Thorkil's scheme (from Knuth) used the higher-order bits.  As I noted  
in my previous email, we're using the low-order bits to index the  
hash table.  This was forced on me by legacy hash functions.

A compromise position here (mentioned in my last mail) might be to  
post-multiply any incoming hash, and then pick off the high-order  
bits.  This penalizes programmers who take the time to write a decent  
hash function for their data type.

> 2) Signed multiplication is being used. I think unsigned  
> multiplication
> is probably necessary to get the intended behaviour. For example, with
> unsigned multiplication, multiplying by the original 'golden' and  
> taking
> the the top 32 bits is equivalent to multiplying by the golden ratio,
> while with signed multiplication it is equivalent to multiplying by  
> the
> golden ratio minus one.

Actually, I've simply used the bits directly.  Signed twos-complement  
multiplication is the same as unsigned twos-complement multiplication  
(with all the unintuitive overflow behavior that entails).  viz:

 > Numeric.showHex ((0x80000001 :: Int32) * 2) ""
"2"

 > Numeric.showHex ((0xa0000000 :: Int32) * 2) ""
"40000000"

> 3) The original code was equivalent to a multiplication by a fixed  
> point
> number less than one.

Yes, and the low order bits of the hash are computed based only on  
the low order bits of the input data.

> The new code is equivalent to multiplying by a
> fixed point number slightly greater than one. I think this misses an
> important behaviour which hash functions should have: They should  
> smear
> out ranges of integers.

Let's keep the intended application in mind: we're going to be taking  
low-order bits from the hashed data.  We only need enough smearing to  
guarantee that this happens.  That said, I'll quickly agree that we'd  
like more smearing than that if we can get it.

> Why? People tend to hash lists with a fold
> which, for example, hashes the previous result, and then xors in or  
> adds
> the new value.

This is in general a rotten way to hash a list of things, which is  
why presentations of hashing don't use it for hashing strings.   
Interestingly Knuth does not cover this topic in detail and mentions  
the use of addition or xor offhandedly.

> If the hashes of small integers are small integers, we
> have the situation where transposing two elements of a list of small
> integers, and making a minor adjustment to one of those values will
> result in a clash. In other words, we're not making effective use  
> of the
> available range of numbers. Hence, for example, the use of 'magic' in
> hashString.

We effectively have a choice here:
   1) Use a decent hash for individual elements, and combine them in  
a simple way (eg sum)
   2) Use a decent method for combining elements

I've tried to use (2).  Indeed, if I were designing the library from  
scratch I'd include a function for combining hashes together.

> I understand your concerns that
>
> A) The hash function should be cheap to evaluate, and need not be
> particularly strong.
>
> However, It should not be unnecessarily weak. A decent hash should  
> allow
> small sets of values (e.g. short lists of ints) to hash to unique
> values. If they do not, scaling falls apart, since rehashing with  
> larger
> table sizes will not necessarily shorten the longer hash chains. I  
> think
> we can find a hash function with better behaviour which is still cheap
> to evaluate.

I think I've demonstrated that they do.  (Actually, I tried an  
additional test last night in which I had testp draw only from  
['a'..'z'], and that worked well too, especially with Ian's  
simplified function using + instead of xor.)  Perhaps you disagree?   
But I'm happy to entertain suggestions of cheap hash functions.   
Recall that you can create a hash table with any hash function you  
like; testing better hash functions with Data.HashTable is really  
pretty easy and doesn't require the source code to the library at all!

> B) If the low bits are zero, it would be nice if the low bits of the
> hash weren't always zero.
>
> A scheme using mulLo doesn't have good behaviour here. Possible
> variations which are quick to evaluate and have this property are:
>  * xor/add together the output of mulHi and mulLo

This is worth a try, since we're (sort of) doing the work anyhow.  [I  
say sort of because on many architectures mulHi and mulLo are  
independent instructions, though I believe on x86 one instruction  
does both.]

>  * Put a rotation step in.

Rotation, of course, just moves the problem elsewhere.

> The downside to these is that these 'adjustments' could well break  
> neat
> behaviour seen in the theory. I'm afraid I don't have the time to test
> these alternatives.
>
> So, I'm sorry I don't really have anything particularly  
> constructive to
> say, but I thought it still worth mentioning what I think are  
> weaknesses
> in the scheme.

I agree that it's not without flaws (no cheap hash is, and the high- 
order zeros are definitely a concern).  But I'll reiterate that I  
believe it's pretty good *for the intended application* while  
agreeing that *something better probably exists.*

-Jan

>
> Thanks,
> 	Simon Frankau.
>
>> On Aug 26, 2007, at 1:42 PM, Thorkil Naur wrote:
>>
>>> Hello,
>> [snip]
>>> In the 2nd edition of Knuth's The Art of Computer Programming, Vol
>>> 3, Sorting
>>> and Searching there is a discussion of hash functions on pp.
>>> 514-520. One of
>>> the techniques suggested for hashing a one-word (i.e. essentially
>>> fixed-size)
>>> key is the following multiplicative scheme:
>>>
>>>   h(K) = floor ( M*(((A/w)*K)) mod 1) )
>>>
>>> where w is the word-size (say, 2^32), M is the desired limit of the
>>> hash
>>> function (for efficiency, probably a suitable power of 2) and,
>>> finally, A is
>>> some integer constant. What happens here is that we consider the
>>> (word) K as
>>> a fraction with the binary point at the left end of the word rather
>
>>> than at
>>> the right, thus getting a fraction with a value between 0 and 1.
>>> This value
>>> we then multiply by A and cut off the integer part, once again
>>> getting a
>>> fractional value between 0 and 1. And finally, we multiply by M and
>
>>> cut away
>>> the fractional part to get an integer value between 0 and M-1. And,
>
>>> sure,
>>> Knuth suggests various variants of selecting the multiplier A
>>> related to the
>>> golden ratio (sqrt(5)-1)/2 = 0.6180... to gain suitable spreading
>>> of hashes
>>> for keys in arithmetic progressions. (K, K+d, K+2d, ...).
>>
>> In the fix below I ended up using twice the golden ratio (a value of
>> A greater than one).  The inverse of the golden ratio (which is 1 +
>> golden) didn't work well at all.
>>
>>> But what we are dealing with in the hashString function is what
>>> Knuth would
>>> call a multiword or variable-length key. Such cases, Knuth
>>> suggests, "can be
>>> handled by multiple-precision extensions of [e.g. the
>>> multiplicative scheme]
>>> above, but it is generally adequate to speed things up by combining
>
>>> the
>>> individual words together into a single word, then doing a single
>>> multiplication ... as above."
>>
>> But combining things into a single word requires having a good
>> combining mechanism, which is hard in general---particularly with a
>> type like Char that appears to have a large range but in practice
>> only has a very small one.
>>
>>> Neither of the above definitions of f implement a multiple-
>>> precision extension
>>> of the multiplicative hashing scheme that involves the golden
> ration.
>>
>> [snip]
>> I actually did do a bakeoff between multiple hashing schemes, and
>> have a version of Data.HashTable that requires separate import of a
>> hashing technique.  The multiplicative hash worked better in the
>> bakeoff than either the modulus hash used in older versions of the
>> library, or a couple of versions of the Bob Jenkins hash.
>>
>> Could I convince someone with a checked out repository to cut and
>> paste this into Data.HashTable and generate a patch / check it in?
>>
>> Thanks,
>>
>> -Jan
>>
>>
>> Here's the fix:
>>
>>
>> --  
>>
> ---------------------------------------------------------------------- 
> --
>
>> -----
>> -- Sample hash functions
>>
>> -- $hash_functions
>> --
>> -- This implementation of hash tables uses the low-order /n/ bits  
>> of  
>> the hash
>> -- value for a key, where /n/ varies as the hash table grows.  A good
>
>> hash
>> -- function therefore will give an even distribution regardless of
> /n/.
>> --
>> -- If your keyspace is integrals such that the low-order bits between
>> -- keys are highly variable, then you could get away with using  
>> 'fromIntegral'
>> -- as the hash function.
>> --
>> -- We provide some sample hash functions for 'Int' and 'String'  
>> below.
>>
>> golden :: Int32
>> golden = 1013904242 -- = round ((sqrt 5 - 1) * 2^32) :: Int32
>> -- was -1640531527 = round ((sqrt 5 - 1) * 2^31) :: Int32
>> -- but that has bad mulHi properties (even adding 2^32 to get its  
>> inverse)
>> -- Whereas the above works well and contains no hash duplications for
>> -- [-32767..65536]
>>
>> hashInt32 :: Int32 -> Int32
>> hashInt32 x = mulHi x golden + x
>>
>> -- | A sample (and useful) hash function for Int and Int32,
>> -- implemented by extracting the uppermost 32 bits of the 64-bit
>> -- result of multiplying by a 33-bit constant.  The constant is from
>> -- Knuth, derived from the golden ratio:
>> -- > golden = round ((sqrt 5 - 1) * 2^32)
>> -- We get good key uniqueness on small inputs
>> -- (a problem with previous versions):
>> --  (length $ group $ sort $ map hashInt [-32767..65536]) == 65536  
>> +  
>> 32768
>> --
>> hashInt :: Int -> Int32
>> hashInt x = hashInt32 (fromIntegral x)
>>
>> -- hi 32 bits of a x-bit * 32 bit -> 64-bit multiply
>> mulHi :: Int32 -> Int32 -> Int32
>> mulHi a b = fromIntegral (r `shiftR` 32)
>>    where r :: Int64
>>          r = fromIntegral a * fromIntegral b
>>
>> -- | A sample hash function for Strings.  We keep multiplying by the
>> -- golden ratio and adding.  The implementation is:
>> --
>> -- > hashString = foldl' f golden
>> -- >   where f m c = fromIntegral (fromEnum c) * magic + hashInt32 m
>> -- >         magic = 0xdeadbeef
>> --
>> -- Where hashInt32 works just as hashInt shown above.
>> --
>> -- Knuth argues that repeated multiplication by the golden ratio
>> -- will minimize gaps in the hash space, and thus it's a good choice
>> -- for combining together multiple keys to form one.
>> --
>> -- Here we know that individual characters c are often small, and  
>> this
>> -- produces frequent collisions if we use fromEnum c alone.  A
>> -- particular problem are the shorter low ASCII and ISO-8859-1
>> -- character strings.  We pre-multiply by a magic twiddle factor to
>> -- obtain a good distribution.  In fact, given the following test:
>> --
>> -- > testp :: Int32 -> Int
>> -- > testp k = (n - ) . length . group . sort . map hs . take n $ ls
>> -- >   where ls = [] : [c : l | l <- ls, c <- ['\0'..'\xff']]
>> -- >         hs = foldl' f golden
>> -- >         f m c = fromIntegral (fromEnum c) * k + hashInt32 m
>> -- >         n = 100000
>> --
>> -- We discover that testp magic = 0.
>>
>> hashString :: String -> Int32
>> hashString = foldl' f golden
>>    where f m c = fromIntegral (fromEnum c) * magic + hashInt32 m
>>          magic = 0xdeadbeef
> ---------------------------------------------------------------------- 
> --
> For important statutory and regulatory disclosures and more  
> information about Barclays Capital, please visit our web site at  
> http://www.barcap.com.
>
> Internet communications are not secure and therefore the Barclays  
> Group does not accept legal responsibility for the contents of this  
> message.  Although the Barclays Group operates anti-virus  
> programmes, it does not accept responsibility for any damage  
> whatsoever that is caused by viruses being passed.  Any views or  
> opinions presented are solely those of the author and do not  
> necessarily represent those of the Barclays Group.  Replies to this  
> email may be monitored by the Barclays Group for operational or  
> business reasons.
>
> Barclays Capital is the investment banking division of Barclays  
> Bank PLC, a company registered in England (number 1026167) with its  
> registered office at 1 Churchill Place, London, E14 5HP. This email  
> may relate to or be sent from other members of the Barclays Group.
> ---------------------------------------------------------------------- 
> --