Data.HashTable

Johannes Waldmann waldmann at imn.htwk-leipzig.de
Thu Mar 6 09:28:12 EST 2008


Hello.

When I insert 50 values in an empty hashtable,
I get longest chains of length 10. Like this:

import Data.HashTable ( HashTable )
import qualified Data.HashTable as H
import System.Random

main = do
     t <- H.new ( == ) H.hashInt
     sequence $ replicate 50 $ do
         x <- randomRIO ( 0 , 1000 )
         H.update t x ()
     lc <- H.longestChain t
     print lc

output:
[(831,()),(346,()),(773,()),(475,()),(812,()),(307,()),(113,()),(637,()),(100,())]

This is not what I expected (quite the contrary).
Did I miss something here? The access time is linear in
the length of the longest chain?
Perhaps the initial table (produced by "new") is too small,
so the table is always overloaded?


Looking at
http://java.sun.com/javase/6/docs/api/java/util/HashMap.html
they start out with table size 16 by default
*and* (more importantly) they have a constructor that allows
to set the initial table size and the load factor.


Best regards, Johannes Waldmann.


More information about the Libraries mailing list