Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Hashtbls with physical equality?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-11-14 (22:30)
From: Wheeler Ruml <ruml@p...>
Subject: Hashtbls with physical equality?
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 and the 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 Ruml, Palo Alto Research Center, Rm 1522, 650-812-4329 voice,           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 in
  let bucket = Cons(key, info, in <- bucket;
  h.size <- succ h.size;
  if h.size > Array.length 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 key) mod (Array.length with
    Empty -> raise Not_found
  | Cons(k1, d1, rest1) ->
      if key == k1 then d1 else find_rec key rest1