From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 8D9547EE6B for ; Mon, 25 Nov 2013 15:43:42 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of yminsky@janestreet.com) identity=pra; client-ip=38.105.200.229; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yminsky@janestreet.com"; x-sender="yminsky@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of yminsky@janestreet.com designates 38.105.200.229 as permitted sender) identity=mailfrom; client-ip=38.105.200.229; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yminsky@janestreet.com"; x-sender="yminsky@janestreet.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@tot-dmz-mxout1.janestreet.com) identity=helo; client-ip=38.105.200.229; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="yminsky@janestreet.com"; x-sender="postmaster@tot-dmz-mxout1.janestreet.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArsBADlhk1ImacjlnGdsb2JhbABZgz9TqTuSbIEiHg4BAQEBAQYNCQkUKIIlAQEFQAEBIwkLAQ8LCw0NISISAQUBChIGExKHXQMPAwIIoQaLEIRSAQWEbAMfh0MRBo4wVweEM4lFjlKBMI52GCmEcYFL X-IPAS-Result: ArsBADlhk1ImacjlnGdsb2JhbABZgz9TqTuSbIEiHg4BAQEBAQYNCQkUKIIlAQEFQAEBIwkLAQ8LCw0NISISAQUBChIGExKHXQMPAwIIoQaLEIRSAQWEbAMfh0MRBo4wVweEM4lFjlKBMI52GCmEcYFL X-IronPort-AV: E=Sophos;i="4.93,768,1378850400"; d="scan'208";a="37798877" Received: from mx5.janestreet.com (HELO tot-dmz-mxout1.janestreet.com) ([38.105.200.229]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 25 Nov 2013 15:43:41 +0100 Received: from tot-oib-smtp1.delacy.com ([172.27.22.15] helo=tot-smtp) by tot-dmz-mxout1.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1VkxNz-0000KK-1l for caml-list@inria.fr; Mon, 25 Nov 2013 09:43:39 -0500 Received: from tot-dmz-mxgoog1.delacy.com ([172.27.224.14] helo=mxgoog2.janestreet.com) by tot-smtp with esmtps (TLSv1:AES256-SHA:256) (Exim 4.72) (envelope-from ) id 1VkxNw-0002fP-0l for caml-list@inria.fr; Mon, 25 Nov 2013 09:43:36 -0500 Received: from mail-lb0-f173.google.com ([209.85.217.173]) by mxgoog2.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1VkxNv-0004Se-Ng for caml-list@inria.fr; Mon, 25 Nov 2013 09:43:35 -0500 Received: by mail-lb0-f173.google.com with SMTP id u14so3245844lbd.18 for ; Mon, 25 Nov 2013 06:43:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=SJrDbT6PaXuvhMyTZAAa+JWeoLpLL7JrrXUeFg4r6qs=; b=vNsMTjKF606hsPWw5zvpTamFMt5IsaFcJUaoH2ziNmcVEcl07Dcbw+bOI6BW62BmBn hvCnvdnXQVOxV0Jkg5uWqzCJ34zfKfJwDHG9UWhS+XZcRVgWoHzLIBu97rQw/E9LuRym uKS3oCpMa4LKFiljFpovhbG00z7HT4XIWE2E0= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=SJrDbT6PaXuvhMyTZAAa+JWeoLpLL7JrrXUeFg4r6qs=; b=NGfqfzpp2dyVN6BvESsscWn3ZP+WLdVzDMQN7Bu607hzarCkJozIQFbDS8XRSq4N4/ lHJmlGXfdTmVwAbg1UU3ExkAFqiDPubiNaYa4thGHV8vQb4AZ+OMXwuJq8CWe18xLSmX M4Nl+0cA5uV5XvhI04dF9Nkd1p/pGaqtKuuW5wNidxOCqsvQuipCFWrEkheKa0oXHZFU 9CbYbuu8iVAn1fUca650dbjzxjLGOEnwtcDm/oRowjSDBkqRUbHmC5OxZWbRb5y4yWYo 8gB9MxMSP77Iqs2L/PC8ePsC6CsujJiiYk0lDq6H4TDnu+cqBDSSMq0BnbslP8wst9SX 231g== X-Gm-Message-State: ALoCoQncT2i5jlwcsRT6syxb2cpQFZXZvtveg/Haa3DHEhKNX03c/g66lsct7m4Ob1L8+GTP8XnMt2KdfMcyRVSpsCakp2unDKRD9H//mBOYRnXTC0lYqzZ4jwatIvyWhjEGpAYG1Yzmr0G3lp7UM6+eX8YkRDxPFA== X-Received: by 10.112.200.100 with SMTP id jr4mr1690225lbc.36.1385390615069; Mon, 25 Nov 2013 06:43:35 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.112.200.100 with SMTP id jr4mr1690210lbc.36.1385390614943; Mon, 25 Nov 2013 06:43:34 -0800 (PST) Received: by 10.112.6.162 with HTTP; Mon, 25 Nov 2013 06:43:34 -0800 (PST) In-Reply-To: <20131125135124.GF3610@frosties> References: <20131118204426.GA14731@annexia.org> <1384819720.4083.57.camel@zotac> <1384859953.62343.YahooMailNeo@web120403.mail.ne1.yahoo.com> <878uwinbqv.fsf@mid.deneb.enyo.de> <1384984030.11161.19.camel@zotac> <20131125135124.GF3610@frosties> Date: Mon, 25 Nov 2013 09:43:34 -0500 Message-ID: From: Yaron Minsky To: Goswin von Brederlow Cc: "caml-list@inria.fr" Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: [Caml-list] Hardening [Perl's] hash function further For what it's worth, Core's Hashtbl module uses AVL trees for the buckets, so the behavior on large numbers of collisions degrades to logarithmic rather than linear. y On Mon, Nov 25, 2013 at 8:51 AM, Goswin von Brederlow wrote: > On Wed, Nov 20, 2013 at 10:47:10PM +0100, Gerd Stolpmann wrote: >> Generally, I think it is better to change the hash table algorithm in >> situations where data from untrusted sources is processed. That means >> using balanced trees for the buckets. Consumes more RAM, but is provably >> safe. (Or, at minimum, limit the length of the buckets.) >> >> Gerd > > If you truely have hash collisions then you can't limit the length of > the buckets. There is no way to make 2 keys with identical hash not > land in the same bucket. > > Or did you mean use a list up to N items and then switch to a tree? > > MfG > Goswin > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs