English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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 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 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