[Haskell-cafe] can there be (hash-table using) O(n) version of this (I think currently) n log n algo?

[Bulat Ziganshin]

Hello Thomas,

Saturday, July 18, 2009, 2:24:21 AM, you wrote:

> Further, is there a hashtable implementation for haskell that doesn't
> live in IO? Maybe in ST or something?

import Prelude hiding (lookup)
import qualified Data.HashTable
import Data.Array
import qualified Data.List as List


data HT a b = HT (a->Int) (Array Int [(a,b)])

-- size is the size of array (we implement a closed hash)
-- hash is the hash function (a->Int)
-- list is assoclist of items to put in hash
create size hash list = HT hashfunc
                           (accumArray (flip (:))
                                       []
                                       (0, arrsize-1)
                                       (map (\(a,b) -> (hashfunc a,(a,b))) list)
                           )

  where arrsize     =  head$ filter (>size)$ iterate (\x->3*x+1) 1
        hashfunc a  =  hash a `mod` arrsize


lookup a (HT hash arr) = List.lookup a (arr!hash a)


main = do let assoclist = [("one", 1), ("two", 2), ("three", 3)]
              hash = create 10 (fromEnum . Data.HashTable.hashString) assoclist
          print (lookup "one" hash)
          print (lookup "zero" hash)


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com