-----------------------------------------------------------------------------
-- |
-- Module      :  Data.HashTable.Multiplicative
-- Copyright   :  (c) Jan-Willem Maessen 2006
--                (c) The University of Glasgow 2003
-- License     :  BSD-style (see the file libraries/base/LICENSE)
--
-- Maintainer  :  libraries@haskell.org
-- Stability   :  provisional
-- Portability :  portable
--
-- Multiplicative hashing.  Separates hashing technique from table
-- management technique.  Multiplicative hashing appears to be faster
-- in practice than the modulus-based hashing technique used in the
-- original Data.HashTable and found in Data.HashTable.Modulus.
--
-----------------------------------------------------------------------------
module Data.HashTable.Multiplicative (hashInt, hashString) where

import Data.Bits
import Data.Int  ( Int32, Int64 )
import Data.List ( foldl' )
import Data.Char ( ord )

-- -----------------------------------------------------------------------------
-- 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 'id'
-- as the hash function.
--
-- We provide some sample hash functions for 'Int' and 'String' below.

golden :: Int32
golden = -1640531527

-- | 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 32-bit constant.  The constant is from
-- Knuth, derived from the golden ratio:
-- > golden = round ((sqrt 5 - 1) * 2^31) :: Int
hashInt :: Int -> Int32
hashInt x = mulHi (fromIntegral x) golden

-- 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 :: Int64

-- | A sample hash function for Strings.  We keep multiplying by the
-- golden ratio and adding.  The implementation is:
--
-- > hashString = foldl' f 0
-- >   where f m c = fromIntegral (ord c) + mulHi m golden
--
-- Note that this has not been extensively tested for reasonability,
-- but Knuth argues that repeated multiplication by the golden ratio
-- will minimize gaps in the hash space.
hashString :: String -> Int32
hashString = foldl' f 0
  where f m c = fromIntegral (ord c) + mulHi m golden