Equality in Ocaml hashtables

Question

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

# 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 h a 1;;
# Hashtbl.add h b 2;;
# Hashtbl.find h a;;
- : int = 2
# Hashtbl.find h b;;
- : int = 2

I'd like a hashtable that can distinguish between a and b. Is that possible?

Answer 1

You can use custom hashtables:

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 Thomas and cago's answers is functionally correct. One issue that may trouble you if you use their solution as-is is that you will get more collisions than expected if you hash many keys that are equal for (=) and different for (==). Indeed, all keys that are equal for (=) have the same hash for Hashtbl.hash, and end up in the same bucket, where they are they recognized as different (since you asked for (==) to be used as equality function) and create different bindings. In the worst cases, the hash-table will behave with the same complexity as an association list (which, by the way, is another data structure that you could be using, and then you wouldn't have to worry about providing a hash function).

If you can accept the key of a value changing occasionally (and therefore the value being impossible to retrieve from the hash-table, since the binding is then in the wrong bucket), you can use the following low-level function as 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)));
}

You would then use:

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