Equality in Ohaml hashtables

Question

Are there hashtables in Ocaml that use == instead of = when testing for key equality? For instance:

 # type foo = A of int;; # let a = A(1);; # let b = A(1);; # a == b;; - : bool = false # a = b;; - : bool = true # let h = Hashtbl.create 8;; # Hashtbl.add ha 1;; # Hashtbl.add hb 2;; # Hashtbl.find ha;; - : int = 2 # Hashtbl.find hb;; - : int = 2 

I need a hash table that can distinguish between a and b . Is it possible?

Answer 1

You can use custom hash tables:

 module H = Hashtbl.Make(struct type t = foo let equal = (==) let hash = Hashtbl.hash end) 

And then use H instead of Hashtbl in your code.

Answer 2

The solution in the answers of Thomas and Kago is functionally correct. One of the problems that may bother you if you use their solution as is is that you will get more collisions than expected if you haveh many keys that are equal for (=) and different for (==) . Indeed, all keys equal to (=) have the same hash for Hashtbl.hash and end with the same bucket where they are recognized as different (since you asked (==) be used as an equality function) and create different bindings . In the worst cases, the hash table will behave with the same complexity as the list of associations (which, by the way, is another data structure that you could use, and then you do not have to worry about providing a hash function).

If you can sometimes accept a key from a value that changes (and therefore the value cannot be extracted from the hash table, since the binding is then in the wrong bucket), you can use the following low-level function as a hash:

 external address_of_value: 'a -> int = "address_of_value" 

Implemented in C as:

 #include "caml/mlvalues.h" value address_of_value(value v) { return (Val_long(((unsigned long)v)/sizeof(long))); } 

Then you would use:

 module H = Hashtbl.Make(struct type t = foo let equal = (==) let hash = address_of_value end);;