Physical identity based alternative to Hashtbl.hash
hash, ocaml, referenceequals
Solution
If you are using the word "object" in the sense of OCaml's `< ... >` object types, then you can use `Oo.id` to get a unique integer identity for each instance. Otherwise the answer to "is there a general proxy for value identity" is "no". In this case my advice would be to start with `Hashtbl.hash`, evaluate whether it fits your need, and otherwise design your own hashing function.
You can also play with `Hashtbl.hash_param` (see documentation) to turn knob on value traversals during hashing. Note that the Hashtbl code uses linked lists for bucket of same-hash values, so having lots of hash conflicts will trigger linear search behavior. It may be better to move to other implementations using binary search trees for conflict buckets. But then again, you should evaluate your situation before moving to more complex (and with worse performances in the "good case") solutions.
Problem
I'm trying to derive a Graphviz file describing a structured value. This is for diagnostic purposes so I want my graph to mirror the actual structure in memory as closely as possible. I'm using the below to map values to Graphviz vertices so that I can reuse a vertex when a value has two or more inbound references: ``` let same = (==) module StateIdentity : Hashtbl.HashedType = struct type t = R.meta_t state let hash = Hashtbl.hash let equal = same end module StateHashtbl = Hashtbl.Make (StateIdentity) ``` The documentation for `Hashtbl.hash` suggests that it is suitable for use both when `StateIdentity.equal = (=)` and when `StateIdentity.equal = (==)` but I'd like to ensure that hash table access is as close to O(1) as possible so would rather not have `Hashtbl.hash` walking a (potentially large in this case) object graph on every lookup. I know Ocaml moves references around, but is there an O(1) proxy for reference identity available in Ocaml? The answer to Hashtable of mutable variable in Ocaml suggests not. I'm loathe to attach serial numbers to states, since this is diagnostic code so any errors I make doing that have the potential to mask other bugs.