From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <ruml@parc.com>
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id 2A76ABB81
	for <caml-list@yquem.inria.fr>; Sun, 14 Nov 2004 23:30:08 +0100 (CET)
Received: from alpha.xerox.com (alpha.Xerox.COM [13.1.64.93])
	by concorde.inria.fr (8.13.0/8.13.0) with SMTP id iAEMU6IJ031078
	for <caml-list@yquem.inria.fr>; Sun, 14 Nov 2004 23:30:07 +0100
Received: from katsura.parc.xerox.com ([13.2.18.21]) by alpha.xerox.com with SMTP id <175999(2)>; Sun, 14 Nov 2004 14:29:54 PST
Received: (from ruml@localhost)
	by katsura.parc.xerox.com (8.12.8/8.12.8/PARC RedHat Custom Submit 1.3) id iAEMTrTZ032409;
	Sun, 14 Nov 2004 14:29:53 -0800
From: Wheeler Ruml <ruml@parc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-ID: <16791.56417.334890.765954@katsura.parc.xerox.com>
Date: Sun, 14 Nov 2004 14:29:53 PST
To: caml-list@yquem.inria.fr
Subject: Hashtbls with physical equality?
X-Mailer: VM 7.07 under 21.4 (patch 12) "Portable Code" XEmacs Lucid
X-Miltered: at concorde with ID 4197DC6E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; wheeler:01 ocaml:01 hash:01 hashtbl:01 filliatre:01 garbage:01 hash:01 traversing:01 integers:01 warmly:01 wheeler:01 integers:01 pointers:01 word-aligned:01 resize:01 
X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.0.0
X-Spam-Level: 

Is it possible in OCaml to have a hash table that can insert and retrieve
values without walking over their structure?  I tried to hack something
together using Obj.magic (working from Hashtbl.ml and the size.ml example
by Filliatre) but it doesn't work for me and I'm concerned that the garbage
collector might be making the magic values obsolete.  I have a hash table
of strings and I'd like to avoid traversing their length on every lookup.
Do I have to explicitly use integers instead?

And hints or advice would be warmly welcome!  Please respond directly to me
as well as to the list, as I can't keep up with the volume and am not a
regular subscriber.  Thanks very much,

Wheeler
-- 
Wheeler Ruml, Palo Alto Research Center, Rm 1522, 650-812-4329 voice
ruml@parc.com, http://www.parc.com/ruml           650-812-4334 fax
------------ excerpt of my attempt --------------------

let hash x =
  (* want both integers and pointers (presumably word-aligned) to have
     well-spread lower bits *)
  let y = ((Obj.magic x) : int) in
    y lxor (y lsr 16)

    
let add h key info =
  let i = (hash key) mod (Array.length h.data) in
  let bucket = Cons(key, info, h.data.(i)) in
  h.data.(i) <- bucket;
  h.size <- succ h.size;
  if h.size > Array.length h.data lsl 1 then resize h

    
let rec find_rec key = function
    Empty ->
      raise Not_found
  | Cons(k, d, rest) ->
      if key == k then d else find_rec key rest

	
let find h key =
  match h.data.((hash key) mod (Array.length h.data)) with
    Empty -> raise Not_found
  | Cons(k1, d1, rest1) ->
      if key == k1 then d1 else find_rec key rest1

------------------------------------------------------------