From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <goswin-v-b@web.de>
X-Original-To: caml-list@sympa.inria.fr
Delivered-To: caml-list@sympa.inria.fr
Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83])
	by sympa.inria.fr (Postfix) with ESMTPS id 00B147EE6B
	for <caml-list@sympa.inria.fr>; Mon, 25 Nov 2013 14:51:26 +0100 (CET)
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  goswin-v-b@web.de) identity=pra; client-ip=212.227.15.4;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="goswin-v-b@web.de";
  x-sender="goswin-v-b@web.de"; x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  goswin-v-b@web.de) identity=mailfrom; client-ip=212.227.15.4;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="goswin-v-b@web.de";
  x-sender="goswin-v-b@web.de"; x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@mout.web.de) identity=helo;
  client-ip=212.227.15.4;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="goswin-v-b@web.de";
  x-sender="postmaster@mout.web.de";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AjwCAFlVk1LU4w8EnGdsb2JhbABZumuFToErFg4BAQEBAQYNCQkUKIIlAQEFOiskCxgJJQ8FKIgiARa1FB+IXI4wXhaDCoETA5gThi4SjnyBaA
X-IPAS-Result: AjwCAFlVk1LU4w8EnGdsb2JhbABZumuFToErFg4BAQEBAQYNCQkUKIIlAQEFOiskCxgJJQ8FKIgiARa1FB+IXI4wXhaDCoETA5gThi4SjnyBaA
X-IronPort-AV: E=Sophos;i="4.93,768,1378850400"; 
   d="scan'208";a="45243510"
Received: from mout.web.de ([212.227.15.4])
  by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES128-SHA; 25 Nov 2013 14:51:25 +0100
Received: from frosties.localnet ([37.49.32.119]) by smtp.web.de (mrweb002)
 with ESMTPSA (Nemesis) id 0MFLQi-1VqSLp0iZA-00ENb0 for <caml-list@inria.fr>;
 Mon, 25 Nov 2013 14:51:25 +0100
Received: from mrvn by frosties.localnet with local (Exim 4.80)
	(envelope-from <goswin-v-b@web.de>)
	id 1VkwZQ-0001ok-DM
	for caml-list@inria.fr; Mon, 25 Nov 2013 14:51:24 +0100
Date: Mon, 25 Nov 2013 14:51:24 +0100
From: Goswin von Brederlow <goswin-v-b@web.de>
To: caml-list@inria.fr
Message-ID: <20131125135124.GF3610@frosties>
References: <20131118204426.GA14731@annexia.org>
 <1384819720.4083.57.camel@zotac>
 <CAC3Lx=ZrsHau9NicrwTjz-Lt7R5ysdrh4S3KVMOc1vZAAhJpvA@mail.gmail.com>
 <CAPFanBGiuiYCe1Y8KKy+CB-P7xg6rkke0qU9CLpiB0xo89ziNQ@mail.gmail.com>
 <1384859953.62343.YahooMailNeo@web120403.mail.ne1.yahoo.com>
 <878uwinbqv.fsf@mid.deneb.enyo.de>
 <1384984030.11161.19.camel@zotac>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <1384984030.11161.19.camel@zotac>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Provags-ID:  V03:K0:aR6k8m5N/fi6Ob3Gj4suPmvFRUTRlr0HpnIUdsvLMnPTR+h161I
 dhl8HkdccstSNIfoJ1HsswJMxc0OrNdjZZzBS4LtrVDjs6zOV4+83B5Dq3wAYj1OPPzN1YT
 mI8DeAOP0XtNn4VgVxiqOS+kV8OglaNFnEhO4jCFKPFXUfuMbiUh5Q9IOEHX6jYike/kTi3
 Hof+1gzz92IXgJYlQfF7A==
Subject: Re: [Caml-list] Hardening [Perl's] hash function further

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