> Is it possible in OCaml to have a hash table that can insert and retrieve
> values without walking over their structure?  I tried to hack something
> together using Obj.magic (working from Hashtbl.ml and the size.ml example
> by Filliatre) but it doesn't work for me and I'm concerned that the garbage
> collector might be making the magic values obsolete.  

You are right: copying of values by the garbage collection makes this 
approach infeasible.

> I have a hash table
> a of strings and I'd like to avoid traversing their length on every lookup.
> Do I have to explicitly use integers instead?

This is certainly a good idea.