.TH "Hashtbl" 3o source: 2019-01-25 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

.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

.I val create 
: 
.B ?random:bool -> 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
The optional 
.B random
parameter (a boolean) controls whether
the internal organization of the hash table is randomized at each
execution of 
.B Hashtbl\&.create
or deterministic over all executions\&.
.sp
A hash table that is created with 
.B ~random:false
uses a
fixed hash function (
.B Hashtbl\&.hash
) to distribute keys among
buckets\&.  As a consequence, collisions between keys happen
deterministically\&.  In Web\-facing applications or other
security\-sensitive applications, the deterministic collision
patterns can be exploited by a malicious user to create a
denial\-of\-service attack: the attacker sends input crafted to
create many collisions in the table, slowing the application down\&.
.sp
A hash table that is created with 
.B ~random:true
uses the seeded
hash function 
.B Hashtbl\&.seeded_hash
with a seed that is randomly
chosen at hash table creation time\&.  In effect, the hash function
used is randomly selected among 
.B 2^{30}
different hash functions\&.
All these hash functions have different collision patterns,
rendering ineffective the denial\-of\-service attack described above\&.
However, because of randomization, enumerating all elements of the
hash table using 
.B Hashtbl\&.fold
or 
.B Hashtbl\&.iter
is no longer
deterministic: elements are enumerated in different orders at
different runs of the program\&.
.sp
If no 
.B ~random
parameter is given, hash tables are created
in non\-random mode by default\&.  This default can be changed
either programmatically by calling 
.B Hashtbl\&.randomize
or by
setting the 
.B R
flag in the 
.B OCAMLRUNPARAM
environment variable\&.

.sp
.B "Before4.00.0"
the 
.B random
parameter was not present and all
hash tables were created in non\-randomized mode\&.


.sp

.I val clear 
: 
.B ('a, 'b) t -> unit
.sp
Empty a hash table\&. Use 
.B reset
instead of 
.B clear
to shrink the
size of the bucket table to its initial size\&.

.sp

.I val reset 
: 
.B ('a, 'b) t -> unit
.sp
Empty a hash table and shrink the size of the bucket table
to its initial size\&.

.sp
.B "Since"
4.00.0

.sp

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

.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

.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

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

.B Hashtbl\&.find_opt tbl x
returns the current binding of 
.B x
in 
.B tbl
,
or 
.B None
if no such binding exists\&.

.sp
.B "Since"
4.05

.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

.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

.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

.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

.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
\&.
.sp
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
If the hash table was created in non\-randomized mode, the order
in which the bindings are enumerated is reproducible between
successive runs of the program, and even between minor versions
of OCaml\&.  For randomized hash tables, the order of enumeration
is entirely random\&.
.sp
The behavior is not defined if the hash table is modified
by 
.B f
during the iteration\&.

.sp

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

.B Hashtbl\&.filter_map_inplace f tbl
applies 
.B f
to all bindings in
table 
.B tbl
and update each binding depending on the result of
.B f
\&.  If 
.B f
returns 
.B None
, the binding is discarded\&.  If it
returns 
.B Some new_val
, the binding is update to associate the key
to 
.B new_val
\&.
.sp
Other comments for 
.B Hashtbl\&.iter
apply as well\&.

.sp
.B "Since"
4.03.0

.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
\&.
.sp
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
If the hash table was created in non\-randomized mode, the order
in which the bindings are enumerated is reproducible between
successive runs of the program, and even between minor versions
of OCaml\&.  For randomized hash tables, the order of enumeration
is entirely random\&.
.sp
The behavior is not defined if the hash table is modified
by 
.B f
during the iteration\&.

.sp

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

.B Hashtbl\&.length tbl
returns the number of bindings in 
.B tbl
\&.
It takes constant time\&.  Multiple bindings are counted once each, so
.B Hashtbl\&.length
gives the number of times 
.B Hashtbl\&.iter
calls its
first argument\&.

.sp

.I val randomize 
: 
.B unit -> unit
.sp
After a call to 
.B Hashtbl\&.randomize()
, hash tables are created in
randomized mode by default: 
.B Hashtbl\&.create
returns randomized
hash tables, unless the 
.B ~random:false
optional parameter is given\&.
The same effect can be achieved by setting the 
.B R
parameter in
the 
.B OCAMLRUNPARAM
environment variable\&.
.sp
It is recommended that applications or Web frameworks that need to
protect themselves against the denial\-of\-service attack described
in 
.B Hashtbl\&.create
call 
.B Hashtbl\&.randomize()
at initialization
time\&.
.sp
Note that once 
.B Hashtbl\&.randomize()
was called, there is no way
to revert to the non\-randomized default behavior of 
.B Hashtbl\&.create
\&.
This is intentional\&.  Non\-randomized hash tables can still be
created using 
.B Hashtbl\&.create ~random:false
\&.

.sp
.B "Since"
4.00.0

.sp

.I val is_randomized 
: 
.B unit -> bool
.sp
return if the tables are currently created in randomized mode by default

.sp
.B "Since"
4.03.0

.sp
.I type statistics 
= {
 num_bindings : 
.B int
;  (* Number of bindings present in the table\&.
Same value as returned by 
.B Hashtbl\&.length
\&.
 *) 
 num_buckets : 
.B int
;  (* Number of buckets in the table\&.
 *) 
 max_bucket_length : 
.B int
;  (* Maximal number of bindings per bucket\&.
 *) 
 bucket_histogram : 
.B int array
;  (* Histogram of bucket sizes\&.  This array 
.B histo
has
length 
.B max_bucket_length + 1
\&.  The value of
.B histo\&.(i)
is the number of buckets whose size is 
.B i
\&.
 *) 
 }

.sp
.B "Since"
4.00.0

.sp

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

.B Hashtbl\&.stats tbl
returns statistics about the table 
.B tbl
:
number of buckets, size of the biggest bucket, distribution of
buckets by size\&.

.sp
.B "Since"
4.00.0

.sp

.PP

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

.PP

.PP

.B === The functorial interface allows the use of specific comparison
.B     and hash functions, either for performance/security concerns,
.B     or because keys are not hashable/comparable with the polymorphic builtins\&.
.B 
.B     For instance, one might want to specialize a table for integer keys:
.B     
.B       module IntHash =
.B         struct
.B           type t = int
.B           let equal i j = i=j
.B           let hash i = i land max_int
.B         end
.B 
.B       module IntHashtbl = Hashtbl\&.Make(IntHash)
.B 
.B       let h = IntHashtbl\&.create 17 in
.B       IntHashtbl\&.add h 12 "hello"
.B     
.B 
.B     This creates a new module IntHashtbl, with a new type \&'a
.B     IntHashtbl\&.t of tables from int to \&'a\&. In this example, h
.B     contains string values so its type is string IntHashtbl\&.t\&.
.B 
.B     Note that the new type \&'a IntHashtbl\&.t is not compatible with
.B     the type (\&'a,\&'b) Hashtbl\&.t of the generic interface\&. For
.B     example, Hashtbl\&.length h would not type\-check, you must use
.B     IntHashtbl\&.length\&. ===

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

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

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

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

.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\&.  Since the hash function is not seeded,
the 
.B create
operation of the result structure always returns
non\-randomized hash tables\&.

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

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

.sp
.B "Since"
4.00.0

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

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

.sp
.B "Since"
4.00.0

.sp
.I module MakeSeeded : 
.B functor (H : SeededHashedType) -> sig  end

.sp
Functor building an implementation of the hashtable structure\&.
The functor 
.B Hashtbl\&.MakeSeeded
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 seeded hashing and equality functions
specified in the functor argument 
.B H
instead of generic
equality and hashing\&.  The 
.B create
operation of the
result structure supports the 
.B ~random
optional parameter
and returns randomized hash tables if 
.B ~random:true
is passed
or if randomization is globally on (see 
.B Hashtbl\&.randomize
)\&.

.sp
.B "Since"
4.00.0

.sp

.PP

.B === 
.B The polymorphic hash functions
.B  ===

.PP

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

.B Hashtbl\&.hash x
associates a nonnegative 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

.I val seeded_hash 
: 
.B int -> 'a -> int
.sp
A variant of 
.B Hashtbl\&.hash
that is further parameterized by
an integer seed\&.

.sp
.B "Since"
4.00.0

.sp

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

.B Hashtbl\&.hash_param meaningful total x
computes a hash value for 
.B x
,
with the same properties as for 
.B hash
\&. The two extra integer
parameters 
.B meaningful
and 
.B total
give more precise control over
hashing\&. Hashing performs a breadth\-first, left\-to\-right traversal
of the structure 
.B x
, stopping after 
.B meaningful
meaningful nodes
were encountered, or 
.B total
nodes (meaningful or not) were
encountered\&.  If 
.B total
as specified by the user exceeds a certain
value, currently 256, then it is capped to that value\&.
Meaningful nodes are: integers; floating\-point
numbers; strings; characters; booleans; and constant
constructors\&. Larger values of 
.B meaningful
and 
.B total
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 meaningful
and 
.B total
govern the tradeoff between accuracy and speed\&.  As default
choices, 
.B Hashtbl\&.hash
and 
.B Hashtbl\&.seeded_hash
take
.B meaningful = 10
and 
.B total = 100
\&.

.sp

.I val seeded_hash_param 
: 
.B int -> int -> int -> 'a -> int
.sp
A variant of 
.B Hashtbl\&.hash_param
that is further parameterized by
an integer seed\&.  Usage:
.B Hashtbl\&.seeded_hash_param meaningful total seed x
\&.

.sp
.B "Since"
4.00.0

.sp