Victor Schubert’s personal page

Hash collisions in OCaml polymorphic variants

Polymorphic variants in OCaml compile down to integers (if they don’t have arguments). As opposed to IDs chosen sequentially for non-polymorphic variants, these integers are chosen by hashing the value’s name. For example, value `Foo is given the integer value 3505894.

As with any hashing algorithm, the algorithm used here is subject to collisions, for example according to this thread on the Caml mailing list values `Eric_Cooper, `azdwbie and `c7diagq all hash to integer value -332323982.

Thankfully this will not cause issues in practice as the OCaml compiler is smart enough to fail whenever collisions occur within a polymorphic variant type. Trying this with the OCaml REPL fails as follows.

# type collision = [`Eric_Cooper | `azdwbie];;
Error: Variant tags `azdwbie and `Eric_Cooper have the same hash value.
       Change one of them.