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 q19DMNXA017026 for ; Thu, 9 Feb 2012 14:22:23 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnMDAEnIM0/ZSMDdjmdsb2JhbABDryQiAQEBAQkLCQkSBSSBcgEBBAEyAUYFCwshJQ8BBCghE4d8A7Myi0wGGgMJAwcEBAQGBAcCAhsBAwgBFAYECINfhB0EmneNHA X-IronPort-AV: E=Sophos;i="4.73,390,1325458800"; d="scan'208";a="130731841" Received: from fmmailgate01.web.de ([217.72.192.221]) by mail4-smtp-sop.national.inria.fr with ESMTP; 09 Feb 2012 14:22:05 +0100 Received: from moweb001.kundenserver.de (moweb001.kundenserver.de [172.19.20.114]) by fmmailgate01.web.de (Postfix) with ESMTP id 125C51AA01029 for ; Thu, 9 Feb 2012 14:22:05 +0100 (CET) Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb001) with ESMTPA (Nemesis) id 0Lsy7e-1Sex1C2zGc-012Smu; Thu, 09 Feb 2012 14:22:04 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.77) (envelope-from ) id 1RvTwq-0000DI-3M; Thu, 09 Feb 2012 14:22:04 +0100 From: Goswin von Brederlow To: AUGER Cdric Cc: Goswin von Brederlow , "Gerd Stolpmann" , caml-list@inria.fr In-Reply-To: <20120208114630.4dcd531d@lri.fr> ("AUGER Cdric"'s message of "Wed, 8 Feb 2012 11:46:30 +0100") References: <1325263446.5036.104.camel@samsung> <87zkd531kl.fsf@frosties.localnet> <403c4e4bb2cfce801aad217c80365879.squirrel@gps.dynxs.de> <8739alfys0.fsf@frosties.localnet> <20120208114630.4dcd531d@lri.fr> User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE) Date: Thu, 09 Feb 2012 14:22:04 +0100 Message-ID: <87bop8qgzn.fsf@frosties.localnet> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Provags-ID: V02:K0:BXttXpNdfXTJ1NENRegzk5ZqCejEw3uB+CUR6ftHGzP S3pm+cRJNSY3UrIFjTc5IRB2IgBWiP5PPHztnPji7S2j0UYSlN 04YPhO1+Dhw1akXgK1ytxkDxTJbLHmLXZvrYnHsqnuOmk/Y0Qd rLCEMDWEwTATIp1wfnwpGq+mxPsLt+xAqO4Z0VrHpzxVsm18sG uZ39s1Bh27DbszuCLVQ1A== 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. [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