From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,SPF_FAIL autolearn=disabled version=3.1.3 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id EB974BC69 for ; Mon, 14 Jan 2008 15:45:15 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAMQDi0fAXQImh2dsb2JhbACQCgEBAQgKKZds X-IronPort-AV: E=Sophos;i="4.24,282,1196636400"; d="scan'208";a="6020064" Received: from discorde.inria.fr ([192.93.2.38]) by mail2-smtp-roc.national.inria.fr with ESMTP; 14 Jan 2008 15:45:15 +0100 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id m0EEj9mu019985 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Mon, 14 Jan 2008 15:45:15 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAMQDi0dQW+UCh2dsb2JhbACQCgEBAQgKKZds X-IronPort-AV: E=Sophos;i="4.24,282,1196636400"; d="scan'208";a="6020062" Received: from main.gmane.org (HELO ciao.gmane.org) ([80.91.229.2]) by mail2-smtp-roc.national.inria.fr with ESMTP; 14 Jan 2008 15:45:09 +0100 Received: from list by ciao.gmane.org with local (Exim 4.43) id 1JEQYj-0000H0-I1 for caml-list@inria.fr; Mon, 14 Jan 2008 14:45:05 +0000 Received: from 206-248-165-105.dsl.teksavvy.com ([206.248.165.105]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 14 Jan 2008 14:45:05 +0000 Received: from monnier by 206-248-165-105.dsl.teksavvy.com with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 14 Jan 2008 14:45:05 +0000 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr From: Stefan Monnier Subject: Re: Hash clash in polymorphic variants Date: Mon, 14 Jan 2008 09:44:58 -0500 Message-ID: References: <200801101709.14110.jon@ffconsultancy.com> <200801111114.03876.ober.14@osu.edu> <000c01c85481$7f727120$6c7ba8c0@countertenor> <200801140720.02094.ober.14@osu.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: 206-248-165-105.dsl.teksavvy.com User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.50 (gnu/linux) Cancel-Lock: sha1:GOW8Ba4R4xKYgmvzBVO44/5bjig= Sender: news X-Miltered: at discorde with ID 478B7575.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; hash:01 variants:01 hash:01 hashing:01 inputs:01 inputs:01 polymorphic:01 compile:01 clash:05 problem:05 meant:06 function:08 function:08 collision:09 umontreal:13 > What I meant was simply that instead of using some fixed hash function, one > could use a perfect hashing function which is optimal for its known set of > inputs, and won't ever generate a collision. The problem is that the set of inputs is not know at compile time, only at link time. Stefan