Version française
Home     About     Download     Resources     Contact us    
Browse thread
RE: Alternative generic hash function
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Manuel Fahndrich <maf@m...>
Subject: RE: Alternative generic hash function
Thanks for all the answers. Yes, one clearly would need information
about mutable data fields at runtime in order to implement hash_pure.

Dmitri's suggestion on using block length and tag for computing the hash is
essentially the
0th approximation of hash_pure, since we know that the length and tag of a
block are immutable.

Noone has made any comments about the managing of explicit id's in order to
get around the problem I sketched. 
I've written a lot of code with such id generation and it is not an ideal
solution. First, there needs to be an id generator, which introduces a
global variable into your program. Second, what happens if you wrap around
in the id space (e.g. ints). I can speak from experience that wrap around
happens, namely when generating structures with id's repeatedly, where most
of them are garbage collected away. At any point, there are only few
structures live, but whenever we create a new one, we still need a fresh id.
In general, one would have to be able to reuse id's, and thus connect with
the garbage collector through weak pointers etc... It gets pretty
complicated.

My point is that the memory address of an object is an ideal id for equality
comparisons. The space of addresses is already managed by the language, such
that reusable id's can be generated cheaply. With copying garbage
collection, id's change over time, which is not a problem for equality
testing, but breaks hashing on them. The only reliable part of a
datastructure to use in computing a hash is the immutable part.

-Manuel

BTW, the same problem arises with the polymorphic comparison functions:

        Objective Caml version 3.00

# let x = ref 1;;
val x : int ref = {contents=1}
# let y = ref 5;;
val y : int ref = {contents=5}
# x < y;;
- : bool = true
# x := 10;;
- : unit = ()
# x < y;;
- : bool = false

Of course, using an analogous pure comparison operator would result in a
preorder, not a total order.




-----Original Message-----
From: Dmitri Lomov [mailto:dsl@tepkom.ru]
Sent: Thursday, May 25, 2000 12:38 AM
To: caml-list@pauillac.inria.fr
Cc: Manuel Fahndrich
Subject: Re: Alternative generic hash function


AFA I understand, Hastable.hash_pure will be hard to implement in run-time,
as now at run-time it is not known whether given data structure, or 
given data structure field is mutable or not.
Such information is not propagated to run-time by ocaml compiler.

Possibly your option here is to divide your data structure into mutable
and immutable parts, and than use Hashtable.hash on immutable part.
Then all will work well.

This, however, does not cover the example you present. 
But actually the nature of hashing assumes the hashed object has
some immutable part. For example, when hashing strings you do not assume 
to get the same hash value for mutable string if you change some character
of it.
In your example everything in an object changes - it does not have any 
immutable properties/elements/fields to "hook" hash to.

By the way, a rough hashing function for all O'Caml objects can be based
on block length and/or tag (they are accesible via Obj module).
Such hash function will tend to be very biased, due to biased
distribution of lengths and tags, but in very bad situations it 
may help.

I use such function in my (forthcoming :-)) dynamic code generation library 
for O'Caml to keep external references from code block. 

Regards,
Dmitri

Manuel Fahndrich wrote:
> 
> The generic hash function Hashtbl.hash traverses into mutable data
> structures. So I get different hash values depending on updates of the
data
> structure.
> 
> # let x = ref None;;
> val x : '_a option ref = {contents=None}
> # Hashtbl.hash x;;
> - : int = 0
> # x := Some 5;;
> - : unit = ()
> # Hashtbl.hash x;;
> - : int = 5
> 
> As was pointed out times before on this list, Hashtbl.hash is thus
> unsuitable for hashing on data structures that contain mutable data.
> 
> I'm wondering what the design rational is for this choice. I'd rather have
a
> generic hash function (Hashtbl.hash_pure) that never looks into mutable
> structures (skips refs and mutable fields of records and classes).
> The reason being that if I want to hash on data that contains references,
> I'm more likely to want to find the structure independent of the contents
of
> any mutable subparts.
> 
> So yes, a hashtable containing int refs would pointless, because it maps
> them all to the same bucket. But I frequently use hashing with equality
> being ==. Whenever I do this, I need to actually add some unique
identifier
> to the data structure just for the hashing operation. Having an alternate
> hash function (Hashtbl.hash_pure) would make such id's (and their
managment)
> unnecessary.
> 
> I see how the current working of Hashtbl.hash is useful for data
structures
> that contain mutable parts in the case where such structures don't change
> between the time they are stored and later looked up in the hash table.
But
> I'm wondering how often this actually arises.
> 
> Furthermore, using Hashtbl.hash_pure in place of Hashtbl.hash would not
> break any old code (except for performance), since all it does is make the
> equivalence classes bigger. On the other hand, using Hashtbl.hash with the
> misconception that it acts as Hashtbl.hash_pure breaks lots of code.
> 
> I rest my case.
> 
>         Manuel Fahndrich
 
_________________________________________________________________
Dmitri S. Lomov
mailto:dsl@tepkom.ru    ICQ#: 20524819 (Rusty)
http://users.tepkom.ru/dsl, http://young.tepkom.ru
ftp://young.tepkom.ru
+7 (812) 428-46-57 (b)   +7 (812) 295-94-15 (h)