.TH "Hashtbl" 3o 2012-06-26 OCamldoc "OCaml library"
.SH NAME
Hashtbl \- Hash tables and hash functions.
.SH Module
Module   Hashtbl
.SH Documentation
.sp
Module
.BI "Hashtbl"
 : 
.B sig  end

.sp
Hash tables and hash functions\&.
.sp
Hash tables are hashed association tables, with in\-place modification\&.
.sp

.sp

.sp
.sp

.PP

.B === 
.B Generic interface
.B  ===

.PP
.I type 
.B ('a, 'b)
.I t 

.sp
The type of hash tables from type 
.B \&'a
to type 
.B \&'b
\&.
.sp

.sp

.I val create 
: 
.B int -> ('a, 'b) t
.sp

.B Hashtbl\&.create n
creates a new, empty hash table, with
initial size 
.B n
\&.  For best results, 
.B n
should be on the
order of the expected number of elements that will be in
the table\&.  The table grows as needed, so 
.B n
is just an
initial guess\&.
.sp

.sp

.I val clear 
: 
.B ('a, 'b) t -> unit
.sp
Empty a hash table\&.
.sp

.sp

.I val add 
: 
.B ('a, 'b) t -> 'a -> 'b -> unit
.sp

.B Hashtbl\&.add tbl x y
adds a binding of 
.B x
to 
.B y
in table 
.B tbl
\&.
Previous bindings for 
.B x
are not removed, but simply
hidden\&. That is, after performing 
.B Hashtbl\&.remove
.B  tbl x
,
the previous binding for 
.B x
, if any, is restored\&.
(Same behavior as with association lists\&.)
.sp

.sp

.I val copy 
: 
.B ('a, 'b) t -> ('a, 'b) t
.sp
Return a copy of the given hashtable\&.
.sp

.sp

.I val find 
: 
.B ('a, 'b) t -> 'a -> 'b
.sp

.B Hashtbl\&.find tbl x
returns the current binding of 
.B x
in 
.B tbl
,
or raises 
.B Not_found
if no such binding exists\&.
.sp

.sp

.I val find_all 
: 
.B ('a, 'b) t -> 'a -> 'b list
.sp

.B Hashtbl\&.find_all tbl x
returns the list of all data
associated with 
.B x
in 
.B tbl
\&.
The current binding is returned first, then the previous
bindings, in reverse order of introduction in the table\&.
.sp

.sp

.I val mem 
: 
.B ('a, 'b) t -> 'a -> bool
.sp

.B Hashtbl\&.mem tbl x
checks if 
.B x
is bound in 
.B tbl
\&.
.sp

.sp

.I val remove 
: 
.B ('a, 'b) t -> 'a -> unit
.sp

.B Hashtbl\&.remove tbl x
removes the current binding of 
.B x
in 
.B tbl
,
restoring the previous binding if it exists\&.
It does nothing if 
.B x
is not bound in 
.B tbl
\&.
.sp

.sp

.I val replace 
: 
.B ('a, 'b) t -> 'a -> 'b -> unit
.sp

.B Hashtbl\&.replace tbl x y
replaces the current binding of 
.B x
in 
.B tbl
by a binding of 
.B x
to 
.B y
\&.  If 
.B x
is unbound in 
.B tbl
,
a binding of 
.B x
to 
.B y
is added to 
.B tbl
\&.
This is functionally equivalent to 
.B Hashtbl\&.remove
.B  tbl x
followed by 
.B Hashtbl\&.add
.B  tbl x y
\&.
.sp

.sp

.I val iter 
: 
.B ('a -> 'b -> unit) -> ('a, 'b) t -> unit
.sp

.B Hashtbl\&.iter f tbl
applies 
.B f
to all bindings in table 
.B tbl
\&.
.B f
receives the key as first argument, and the associated value
as second argument\&. Each binding is presented exactly once to 
.B f
\&.
The order in which the bindings are passed to 
.B f
is unspecified\&.
However, if the table contains several bindings for the same key,
they are passed to 
.B f
in reverse order of introduction, that is,
the most recent binding is passed first\&.
.sp

.sp

.I val fold 
: 
.B ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
.sp

.B Hashtbl\&.fold f tbl init
computes
.B (f kN dN \&.\&.\&. (f k1 d1 init)\&.\&.\&.)
,
where 
.B k1 \&.\&.\&. kN
are the keys of all bindings in 
.B tbl
,
and 
.B d1 \&.\&.\&. dN
are the associated values\&.
Each binding is presented exactly once to 
.B f
\&.
The order in which the bindings are passed to 
.B f
is unspecified\&.
However, if the table contains several bindings for the same key,
they are passed to 
.B f
in reverse order of introduction, that is,
the most recent binding is passed first\&.
.sp

.sp

.I val length 
: 
.B ('a, 'b) t -> int
.sp

.B Hashtbl\&.length tbl
returns the number of bindings in 
.B tbl
\&.
Multiple bindings are counted multiply, so 
.B Hashtbl\&.length
gives the number of times 
.B Hashtbl\&.iter
calls its first argument\&.
.sp

.sp

.PP

.B === 
.B Functorial interface
.B  ===

.PP
.I module type HashedType = 
.B sig  end

.sp
The input signature of the functor 
.B Hashtbl\&.Make
\&.
.sp

.sp
.I module type S = 
.B sig  end

.sp
The output signature of the functor 
.B Hashtbl\&.Make
\&.
.sp

.sp
.I module Make : 
.B functor (H : HashedType) -> sig  end

.sp
Functor building an implementation of the hashtable structure\&.
The functor 
.B Hashtbl\&.Make
returns a structure containing
a type 
.B key
of keys and a type 
.B \&'a t
of hash tables
associating data of type 
.B \&'a
to keys of type 
.B key
\&.
The operations perform similarly to those of the generic
interface, but use the hashing and equality functions
specified in the functor argument 
.B H
instead of generic
equality and hashing\&.
.sp

.sp

.PP

.B === 
.B The polymorphic hash primitive
.B  ===

.PP

.I val hash 
: 
.B 'a -> int
.sp

.B Hashtbl\&.hash x
associates a positive integer to any value of
any type\&. It is guaranteed that
if 
.B x = y
or 
.B Pervasives\&.compare x y = 0
, then 
.B hash x = hash y
\&.
Moreover, 
.B hash
always terminates, even on cyclic
structures\&.
.sp

.sp

.I val hash_param 
: 
.B int -> int -> 'a -> int
.sp

.B Hashtbl\&.hash_param n m x
computes a hash value for 
.B x
, with the
same properties as for 
.B hash
\&. The two extra parameters 
.B n
and
.B m
give more precise control over hashing\&. Hashing performs a
depth\-first, right\-to\-left traversal of the structure 
.B x
, stopping
after 
.B n
meaningful nodes were encountered, or 
.B m
nodes,
meaningful or not, were encountered\&. Meaningful nodes are: integers;
floating\-point numbers; strings; characters; booleans; and constant
constructors\&. Larger values of 
.B m
and 
.B 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 
.B m
and 
.B n
govern the tradeoff between accuracy and speed\&.
.sp

.sp