From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q19En4nB021889 for ; Thu, 9 Feb 2012 15:49:04 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Am0FADbcM0/U4xEKk2dsb2JhbABEnkeQYCIBAQEBCQkLCRQDJIFyAQEEASdHCwULBQYlIUUSBhMJCAGHagMGugSLTAYaAwkDBwQHPQGDOBY3C08HDIMwBI03F5pF X-IronPort-AV: E=Sophos;i="4.73,390,1325458800"; d="scan'208";a="130745904" Received: from moutng.kundenserver.de ([212.227.17.10]) by mail4-smtp-sop.national.inria.fr with ESMTP; 09 Feb 2012 15:48:58 +0100 Received: from office1.lan.sumadev.de (dslb-094-219-216-005.pools.arcor-ip.net [94.219.216.5]) by mrelayeu.kundenserver.de (node=mreu4) with ESMTP (Nemesis) id 0MEg2P-1RkEu646Lh-00FVhP; Thu, 09 Feb 2012 15:48:56 +0100 Received: from gps.dynxs.de (localhost [127.0.0.1]) by office1.lan.sumadev.de (Postfix) with ESMTP id 348BEC0D03; Thu, 9 Feb 2012 15:48:55 +0100 (CET) Received: from 84.58.2.219 (SquirrelMail authenticated user gerd) by gps.dynxs.de with HTTP; Thu, 9 Feb 2012 15:48:55 +0100 Message-ID: In-Reply-To: <87bop8qgzn.fsf@frosties.localnet> References: <1325263446.5036.104.camel@samsung> <87zkd531kl.fsf@frosties.localnet> <403c4e4bb2cfce801aad217c80365879.squirrel@gps.dynxs.de> <8739alfys0.fsf@frosties.localnet> <20120208114630.4dcd531d@lri.fr> <87bop8qgzn.fsf@frosties.localnet> Date: Thu, 9 Feb 2012 15:48:55 +0100 From: "Gerd Stolpmann" To: "Goswin von Brederlow" Cc: "AUGER Cdric" , caml-list@inria.fr User-Agent: SquirrelMail/1.4.21 MIME-Version: 1.0 Content-Type: text/plain;charset=iso-8859-1 X-Priority: 3 (Normal) Importance: Normal X-Provags-ID: V02:K0:kV4ujqOJILUJQlNgsFjdr1g/NrYktD3RsLO8z94poNR qu5cKwTCN2x0YziksHthyX50T5n+BLMAMDpDAT/aWFRX4EBVOA WRwNDBho3KSy1cnT/KG4WVYvOsgC6Fs3/m7yX+RLH6Eg08nD5G t11Lcep4BqDsrlDcnQJrom2Yq3lPCFyU3XwfWvXepQY2SSfWXg FwF/YWeE3scSW8TFOQGNGLrob2zyHNOKx3TCZHwP4hTUXQu0/S 2q4omFOZKFqfu4OVRDq1JfVOdH4CJ1cp7M+/XK3TV21Rb61oxr ieg6f4I3TBcOWhWkzwjcY6ptxgktMafsWD2VF8GY2fnsMwYBuj zBwUPzSDFVC1kSt0APIzrrJH35u+20foV9t3Pn33g+pV0T36a0 U94iltNBKSiRQ== Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id q19En4nB021889 Subject: Re: [Caml-list] Hashtbl and security > AUGER Cédric writes: > >> More seriously, hashtables are here to store values, so you don't want >> want to have a hash value bigger than (2^30)-1. >> >> In fact even such a value is too big for that purpouse IMHO, since on a >> 4Gio RAM computer, it will take half it to store the table, assuming >> each entry only takes 4 octets, that is it would be ok only for storing >> just the structure of the table (each entry has to be a pointer), >> so that in practice, either your table is ridiculously big to store >> too few values either it is relevant to have such a size and in this >> case your computer will spend all its time to swap since you won't >> have enough RAM. > > But I have 128GB ram. :) That allows for a hashtable of size 2^33 > entries pointing at simple values (e.g. ints) without swapping. And ram > sizes get bigger and bigger. Fully agreed. The limitation to 30 bits is already unpractical for such large computers. Maybe we need a second hash function val Hashtbl.wide_hash : 'a -> int without this constraint (on 64 bit systems). Btw, you can already define your own hash functions, just use the functorized interface. And you are not limited to 30 bits. It's a bit inconvenient only. Gerd > > [Doesn't a Hashtbl of ints store the ints directly? That would allow > 2^34 entries.] > >> Clearly you cannot a bijection from 63 bits >> integers to 31 bits integers; so there are a lot of collisions. I do >> not have a 64 arch, but I guesse that if you hash "2^48+168" you will >> get "168". I guess such a function is ways to be ideal, since when >> playing with bitvectors having two integers which differs by only one >> bit is very common, but at least it is a fast function, and has a good >> repartition (you have 2^32 collisions exactly per bucket). > > Ignoring the upper bits makes for a verry verry poor hash function. Also > means it is 100% trivial to create a DOS by tuneing your input values to > only differ in the upper bits. > > MfG > Goswin > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > > > -- Gerd Stolpmann, Darmstadt, Germany gerd@gerd-stolpmann.de Creator of GODI and camlcity.org. Contact details: http://www.camlcity.org/contact.html Company homepage: http://www.gerd-stolpmann.de *** Searching for new projects! Need consulting for system *** programming in Ocaml? Gerd Stolpmann can help you.