Data.HashTable.hashInt seems somewhat sub-optimal

[Simon.Frankau at barclayscapital.com]

Jan-Willem Maessen wrote:
[snip]
> Simon.Frankau at barclayscapital.com wrote:
> > 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"

I was under the impression that sign extension means this is not the
case:

import Data.Int
import Data.Word
import Data.Bits

golden :: Int32
golden = -1640531527

mulHi :: Int32 -> Int32 -> Int32
mulHi a b = fromIntegral (r `shiftR` 32)
    where r :: Int64
          r = fromIntegral a * fromIntegral b

golden' :: Word32
golden' = -1640531527

mulHi' :: Word32 -> Word32 -> Word32
mulHi' a b = fromIntegral (r `shiftR` 32)
    where r :: Word64
          r = fromIntegral a * fromIntegral b

*Main> :l /temp/test.hs
[1 of 1] Compiling Main             ( /temp/test.hs, interpreted)
Ok, modules loaded: Main.
*Main> mulHi golden 100000
-38197
*Main> mulHi' golden' 100000
61803

(Given we're not using Knuth's algorithm, this is probably rather
academic, though.)

[snip]
> > 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.

Ok. My understanding of a sensible way to hash a list would be something
like this:

hashList = foldl' f base
    where f m x = hashA x `op` hashB m

'op' is normally, say, addition. For the new hashString, hashA is the
low bits of a multiplication, and hashB is hashInt. Making hashB into
'id' is a really bad thing, since then you can commute items in a list
and get the same hash. Making hashA into 'id' seems less bad to me, at
least for non-nested lists (and looks like it is how the old hashString
worked). However, if hashB is your implementation of hashInt, hashA
needs to be good, otherwise hash collisions may result.

I think this is *really* non-obvious from the user's point of view.
Ideally the interface would expose two non-commuting hash functions to
make hashing tree-like structures better, but as you say, you're not
designing the interface from scratch, and so users have to work in a
framework where they are supplied with a single integer-hashing
function, and are implicitly required to implement another for all
non-trivial hashing work.

>From the point of view of a user of a library, I think someone would
expect the built-in hash function to be robust. That is, something that
doesn't map small integers to small integers. If the user wants high
performance, they'll be writing custom hash functions based on
domain-specific knowledge. The library function should be there for
people who don't want to implement their own hashes.

[snip]
> >  * Put a rotation step in.
> 
> Rotation, of course, just moves the problem elsewhere.

It does, but if you're gluing intermediate hash results together with an
addition, the problem goes away. It is rather usage-dependent,
admittedly, and thus probably not a good idea for a general-purpose,
library-exported hash function.

[snip]
> 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.*

I'm not sure that the intended usage pattern is obvious to me from the
documentation, but I'm willing to believe that's my problem rather than
yours. Certainly the changes you've made are an improvement on the
previous version. Given I'm not providing a viable alternative, it seems
best to commit your changes.

Thanks,
	Simon Frankau.
------------------------------------------------------------------------
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.
------------------------------------------------------------------------