From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by sympa.inria.fr (Postfix) with ESMTPS id 989597EEB3 for ; Thu, 17 Jan 2013 16:35:34 +0100 (CET) Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jeannin@cs.cornell.edu) identity=pra; client-ip=128.84.103.138; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="jeannin@cs.cornell.edu"; x-sender="jeannin@cs.cornell.edu"; x-conformance=sidf_compatible Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of jeannin@cs.cornell.edu) identity=mailfrom; client-ip=128.84.103.138; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="jeannin@cs.cornell.edu"; x-sender="jeannin@cs.cornell.edu"; x-conformance=sidf_compatible Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@exch-hub1.cs.cornell.edu) identity=helo; client-ip=128.84.103.138; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="jeannin@cs.cornell.edu"; x-sender="postmaster@exch-hub1.cs.cornell.edu"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Al8BAIMZ+FCAVGeKiWdsb2JhbABEukWDdg4BAQEVEhQFIoIgPUA9FhgDAgECAUsNCAEBiBWaM5gyh1GROAOILDWTFo1x X-IronPort-AV: E=Sophos;i="4.84,486,1355094000"; d="scan'208";a="168814936" Received: from mail-hub-1.cs.cornell.edu (HELO exch-hub1.cs.cornell.edu) ([128.84.103.138]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-MD5; 17 Jan 2013 16:35:33 +0100 Received: from [128.84.98.62] (128.84.98.62) by mail.cs.cornell.edu (128.84.103.140) with Microsoft SMTP Server (TLS) id 8.3.279.5; Thu, 17 Jan 2013 10:35:32 -0500 Message-ID: <50F81A48.4080901@cs.cornell.edu> Date: Thu, 17 Jan 2013 10:35:36 -0500 From: Jean-Baptiste Jeannin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.2) Gecko/20120216 Thunderbird/10.0.2 MIME-Version: 1.0 To: "caml-list@inria.fr" Content-Type: text/plain; charset="ISO-8859-1"; format=flowed Content-Transfer-Encoding: 7bit Subject: [Caml-list] Hash function: complexity and circular structures Hello, The default OCaml function (Hashtbl.hash) says that it "always terminates, even on cyclic structures.". I would be curious to know what its complexity is, both on a finite list and on a cyclic list (created by let rec l = 1 :: l for example). Is the algorithm that is being used published anywhere? Also, this hashing function seems to be returning 0 on any cyclic list (at least the ones I tried). Is this normal? Does anyone know any better hashing function on cyclic lists? # Hashtbl.hash [ 1 ; 2 ];; - : int = 131199 # let rec ones = 1 :: ones;; val ones : int list = [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; ...] # Hashtbl.hash ones;; - : int = 0 # Hashtbl.hash (5 :: 4 :: ones);; - : int = 0 Thank you, Jean-Baptiste Jeannin