19.11 Module Hashtbl: hash tables and hash functions

Hash tables are hashed association tables, with in-place modification.
Generic interface
type ('a, 'b) t
The type of hash tables from type 'a to type 'b.
val create : int -> ('a,'b) t
Hashtbl.create n creates a new, empty hash table, with initial size n. For best results, n should be on the order of the expected number of elements that will be in the table. The table grows as needed, so n is just an initial guess.
val clear : ('a, 'b) t -> unit
Empty a hash table.
val add : ('a, 'b) t -> key:'a -> data:'b -> unit
Hashtbl.add tbl x y adds a binding of x to y in table tbl. Previous bindings for x are not removed, but simply hidden. That is, after performing Hashtbl.remove tbl x, the previous binding for x, if any, is restored. (Same behavior as with association lists.)
val find : ('a, 'b) t -> 'a -> 'b
Hashtbl.find tbl x returns the current binding of x in tbl, or raises Not_found if no such binding exists.
val find_all : ('a, 'b) t -> 'a -> 'b list
Hashtbl.find_all tbl x returns the list of all data associated with x in tbl. The current binding is returned first, then the previous bindings, in reverse order of introduction in the table.
val mem :  ('a, 'b) t -> 'a -> bool
Hashtbl.mem tbl x checks if x is bound in tbl.
val remove : ('a, 'b) t -> 'a -> unit
Hashtbl.remove tbl x removes the current binding of x in tbl, restoring the previous binding if it exists. It does nothing if x is not bound in tbl.
val replace : ('a, 'b) t -> key:'a -> data:'b -> unit
Hashtbl.replace tbl x y replaces the current binding of x in tbl by a binding of x to y. If x is unbound in tbl, a binding of x to y is added to tbl. This is functionally equivalent to Hashtbl.remove tbl x followed by Hashtbl.add tbl x y.
val iter : f:(key:'a -> data:'b -> unit) -> ('a, 'b) t -> unit
Hashtbl.iter f tbl applies f to all bindings in table tbl. f receives the key as first argument, and the associated value as second argument. The order in which the bindings are passed to f is unspecified. Each binding is presented exactly once to f.
The polymorphic hash primitive
val hash : 'a -> int
Hashtbl.hash x associates a positive integer to any value of any type. It is guaranteed that if x = y, then hash x = hash y. Moreover, hash always terminates, even on cyclic structures.
val hash_param : int -> int -> 'a -> int
Hashtbl.hash_param n m x computes a hash value for x, with the same properties as for hash. The two extra parameters n and m give more precise control over hashing. Hashing performs a depth-first, right-to-left traversal of the structure x, stopping after n meaningful nodes were encountered, or m nodes, meaningful or not, were encountered. Meaningful nodes are: integers; floating-point numbers; strings; characters; booleans; and constant constructors. Larger values of m and n means that more nodes are taken into account to compute the final hash value, and therefore collisions are less likely to happen. However, hashing takes longer. The parameters m and n govern the tradeoff between accuracy and speed.