From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q18AhbDS021213 for ; Wed, 8 Feb 2012 11:43:40 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsATAChRMk/RVda2imdsb2JhbABAA6I1AY0lCCIBAQEKCQ0ZBiOBcgEBAQQSAiwBOAEDDAEFBQsNLiISAQUBHAYTIqNQCo5hhR2JMgIFC4s8BgIBAgIJAgIBBgcEBgELAQgFAwMJBQwCDIQbCzeDIgSNIogKjh49gVOCMA X-IronPort-AV: E=Sophos;i="4.73,383,1325458800"; d="scan'208";a="143364208" Received: from mail-tul01m020-f182.google.com ([209.85.214.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 08 Feb 2012 11:43:39 +0100 Received: by obcwo16 with SMTP id wo16so1149390obc.27 for ; Wed, 08 Feb 2012 02:43:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=bXfLiScjrNzbqpleJ4ljHlM6/QxmdV0W3DVZt6pwhmE=; b=D/GOoLTCQ81te/1cug5dWw+JHXY6yo3c+GMPcD5AHVx2w30VtIagzUxskFFk3CgEjG Wu06H1OqyP249CL2iyr4lMYOYXQI984HRHW5gej1f8skoXftoyyw8LQwuFveFvkMPNWY HYjTyRkrTUrx+H0M3G41JubhbIMZzI4wSMVSs= MIME-Version: 1.0 Received: by 10.182.141.9 with SMTP id rk9mr15408020obb.50.1328697818462; Wed, 08 Feb 2012 02:43:38 -0800 (PST) Sender: philippe.wang.lists@gmail.com Received: by 10.182.6.40 with HTTP; Wed, 8 Feb 2012 02:43:38 -0800 (PST) In-Reply-To: <8739alfys0.fsf@frosties.localnet> References: <1325263446.5036.104.camel@samsung> <87zkd531kl.fsf@frosties.localnet> <403c4e4bb2cfce801aad217c80365879.squirrel@gps.dynxs.de> <8739alfys0.fsf@frosties.localnet> Date: Wed, 8 Feb 2012 11:43:38 +0100 X-Google-Sender-Auth: bO9UANdnVuO_EoGiGqXAwkF8EqU Message-ID: From: Philippe Wang To: Goswin von Brederlow Cc: Gerd Stolpmann , caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id q18AhbDS021213 Subject: Re: [Caml-list] Hashtbl and security On Wed, Feb 8, 2012 at 10:41 AM, Goswin von Brederlow wrote: > [...] > Maybe the size of the hashtable indeed isn't the problem but the hash > function. Here is something odd: > > # for i = 1 to 63 do Printf.printf "%d %d\n" (1 lsl i) (Hashtbl.hash (1 lsl i)) done;; > 2 2 > 4 4 > 8 8 > 16 16 > 32 32 > 64 64 > 128 128 > 256 256 > 512 512 > 1024 1024 > 2048 2048 > 4096 4096 > 8192 8192 > 16384 16384 > 32768 32768 > 65536 65536 > 131072 131072 > 262144 262144 > 524288 524288 > 1048576 1048576 > 2097152 2097152 > 4194304 4194304 > 8388608 8388608 > 16777216 16777216 > 33554432 33554432 > 67108864 67108864 > 134217728 134217728 > 268435456 268435456 > 536870912 536870912 > 1073741824 0 > 2147483648 0 > 4294967296 0 > 8589934592 0 > 17179869184 0 > 34359738368 0 > 68719476736 0 > 137438953472 0 > 274877906944 0 > 549755813888 0 > 1099511627776 0 > 2199023255552 0 > 4398046511104 0 > 8796093022208 0 > 17592186044416 0 > 35184372088832 0 > 70368744177664 0 > 140737488355328 0 > 281474976710656 0 > 562949953421312 0 > 1125899906842624 0 > 2251799813685248 0 > 4503599627370496 0 > 9007199254740992 0 > 18014398509481984 0 > 36028797018963968 0 > 72057594037927936 0 > 144115188075855872 0 > 288230376151711744 0 > 576460752303423488 0 > 1152921504606846976 0 > 2305843009213693952 0 > -4611686018427387904 0 > 0 0 > - : unit = () > > Is every value over a billion hashed to 0? > > MfG >        Goswin > Hi, you're making it look worse than it really is: $ ocaml Objective Caml version 3.12.0 # Hashtbl.hash 1000000001;; - : int = 1000000001 # Hashtbl.hash 1073741824;; - : int = 0 # Hashtbl.hash 1073741825;; - : int = 1 # Hashtbl.hash 1073741826;; - : int = 2 # Hashtbl.hash 1073741829;; - : int = 5 # Hashtbl.hash 1073741830;; - : int = 6 # Hashtbl.hash 9007199254740994;; - : int = 2 # Hashtbl.hash 9007199254740990;; - : int = 1073741822 Cheers, -- Philippe Wang    mail@philippewang.info