1272 lines
18 KiB
HTML
1272 lines
18 KiB
HTML
|
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
<HTML><HEAD><TITLE>Man page of Hashtbl</TITLE>
|
|
</HEAD><BODY>
|
|
<H1>Hashtbl</H1>
|
|
Section: OCaml library (3o)<BR>Updated: 2020-01-30<BR><A HREF="#index">Index</A>
|
|
<A HREF="/cgi-bin/man/man2html">Return to Main Contents</A><HR>
|
|
|
|
<A NAME="lbAB"> </A>
|
|
<H2>NAME</H2>
|
|
|
|
Hashtbl - Hash tables and hash functions.
|
|
<A NAME="lbAC"> </A>
|
|
<H2>Module</H2>
|
|
|
|
Module Hashtbl
|
|
<A NAME="lbAD"> </A>
|
|
<H2>Documentation</H2>
|
|
|
|
<P>
|
|
Module
|
|
<B>Hashtbl</B>
|
|
|
|
<BR> :
|
|
<B>sig end</B>
|
|
|
|
<P>
|
|
<P>
|
|
Hash tables and hash functions.
|
|
<P>
|
|
Hash tables are hashed association tables, with in-place modification.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAE"> </A>
|
|
<H3>Generic interface</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<I>type </I>
|
|
|
|
<B>('a, 'b)</B>
|
|
|
|
<I>t </I>
|
|
|
|
<P>
|
|
<P>
|
|
The type of hash tables from type
|
|
<B>'a</B>
|
|
|
|
to type
|
|
<B>'b</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val create </I>
|
|
|
|
:
|
|
<B>?random:bool -> int -> ('a, 'b) t</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.create n</B>
|
|
|
|
creates a new, empty hash table, with
|
|
initial size
|
|
<B>n</B>
|
|
|
|
. For best results,
|
|
<B>n</B>
|
|
|
|
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</B>
|
|
|
|
is just an
|
|
initial guess.
|
|
<P>
|
|
The optional
|
|
<B>random</B>
|
|
|
|
parameter (a boolean) controls whether
|
|
the internal organization of the hash table is randomized at each
|
|
execution of
|
|
<B>Hashtbl.create</B>
|
|
|
|
or deterministic over all executions.
|
|
<P>
|
|
A hash table that is created with
|
|
<B>~random:false</B>
|
|
|
|
uses a
|
|
fixed hash function (
|
|
<B>Hashtbl.hash</B>
|
|
|
|
) 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.
|
|
<P>
|
|
A hash table that is created with
|
|
<B>~random:true</B>
|
|
|
|
uses the seeded
|
|
hash function
|
|
<B>Hashtbl.seeded_hash</B>
|
|
|
|
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}</B>
|
|
|
|
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</B>
|
|
|
|
or
|
|
<B>Hashtbl.iter</B>
|
|
|
|
is no longer
|
|
deterministic: elements are enumerated in different orders at
|
|
different runs of the program.
|
|
<P>
|
|
If no
|
|
<B>~random</B>
|
|
|
|
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</B>
|
|
|
|
or by
|
|
setting the
|
|
<B>R</B>
|
|
|
|
flag in the
|
|
<B>OCAMLRUNPARAM</B>
|
|
|
|
environment variable.
|
|
<P>
|
|
<P>
|
|
<B>Before4.00.0</B>
|
|
|
|
the
|
|
<B>random</B>
|
|
|
|
parameter was not present and all
|
|
hash tables were created in non-randomized mode.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val clear </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> unit</B>
|
|
|
|
<P>
|
|
Empty a hash table. Use
|
|
<B>reset</B>
|
|
|
|
instead of
|
|
<B>clear</B>
|
|
|
|
to shrink the
|
|
size of the bucket table to its initial size.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val reset </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> unit</B>
|
|
|
|
<P>
|
|
Empty a hash table and shrink the size of the bucket table
|
|
to its initial size.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val copy </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> ('a, 'b) t</B>
|
|
|
|
<P>
|
|
Return a copy of the given hashtable.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val add </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> 'a -> 'b -> unit</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.add tbl x y</B>
|
|
|
|
adds a binding of
|
|
<B>x</B>
|
|
|
|
to
|
|
<B>y</B>
|
|
|
|
in table
|
|
<B>tbl</B>
|
|
|
|
.
|
|
Previous bindings for
|
|
<B>x</B>
|
|
|
|
are not removed, but simply
|
|
hidden. That is, after performing
|
|
<B>Hashtbl.remove</B>
|
|
|
|
<B>tbl x</B>
|
|
|
|
,
|
|
the previous binding for
|
|
<B>x</B>
|
|
|
|
, if any, is restored.
|
|
(Same behavior as with association lists.)
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val find </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> 'a -> 'b</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.find tbl x</B>
|
|
|
|
returns the current binding of
|
|
<B>x</B>
|
|
|
|
in
|
|
<B>tbl</B>
|
|
|
|
,
|
|
or raises
|
|
<B>Not_found</B>
|
|
|
|
if no such binding exists.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val find_opt </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> 'a -> 'b option</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.find_opt tbl x</B>
|
|
|
|
returns the current binding of
|
|
<B>x</B>
|
|
|
|
in
|
|
<B>tbl</B>
|
|
|
|
,
|
|
or
|
|
<B>None</B>
|
|
|
|
if no such binding exists.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.05
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val find_all </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> 'a -> 'b list</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.find_all tbl x</B>
|
|
|
|
returns the list of all data
|
|
associated with
|
|
<B>x</B>
|
|
|
|
in
|
|
<B>tbl</B>
|
|
|
|
.
|
|
The current binding is returned first, then the previous
|
|
bindings, in reverse order of introduction in the table.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val mem </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> 'a -> bool</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.mem tbl x</B>
|
|
|
|
checks if
|
|
<B>x</B>
|
|
|
|
is bound in
|
|
<B>tbl</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val remove </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> 'a -> unit</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.remove tbl x</B>
|
|
|
|
removes the current binding of
|
|
<B>x</B>
|
|
|
|
in
|
|
<B>tbl</B>
|
|
|
|
,
|
|
restoring the previous binding if it exists.
|
|
It does nothing if
|
|
<B>x</B>
|
|
|
|
is not bound in
|
|
<B>tbl</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val replace </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> 'a -> 'b -> unit</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.replace tbl x y</B>
|
|
|
|
replaces the current binding of
|
|
<B>x</B>
|
|
|
|
in
|
|
<B>tbl</B>
|
|
|
|
by a binding of
|
|
<B>x</B>
|
|
|
|
to
|
|
<B>y</B>
|
|
|
|
. If
|
|
<B>x</B>
|
|
|
|
is unbound in
|
|
<B>tbl</B>
|
|
|
|
,
|
|
a binding of
|
|
<B>x</B>
|
|
|
|
to
|
|
<B>y</B>
|
|
|
|
is added to
|
|
<B>tbl</B>
|
|
|
|
.
|
|
This is functionally equivalent to
|
|
<B>Hashtbl.remove</B>
|
|
|
|
<B>tbl x</B>
|
|
|
|
followed by
|
|
<B>Hashtbl.add</B>
|
|
|
|
<B>tbl x y</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val iter </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> unit) -> ('a, 'b) t -> unit</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.iter f tbl</B>
|
|
|
|
applies
|
|
<B>f</B>
|
|
|
|
to all bindings in table
|
|
<B>tbl</B>
|
|
|
|
.
|
|
<B>f</B>
|
|
|
|
receives the key as first argument, and the associated value
|
|
as second argument. Each binding is presented exactly once to
|
|
<B>f</B>
|
|
|
|
.
|
|
<P>
|
|
The order in which the bindings are passed to
|
|
<B>f</B>
|
|
|
|
is unspecified.
|
|
However, if the table contains several bindings for the same key,
|
|
they are passed to
|
|
<B>f</B>
|
|
|
|
in reverse order of introduction, that is,
|
|
the most recent binding is passed first.
|
|
<P>
|
|
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.
|
|
<P>
|
|
The behavior is not defined if the hash table is modified
|
|
by
|
|
<B>f</B>
|
|
|
|
during the iteration.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val filter_map_inplace </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> 'b option) -> ('a, 'b) t -> unit</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.filter_map_inplace f tbl</B>
|
|
|
|
applies
|
|
<B>f</B>
|
|
|
|
to all bindings in
|
|
table
|
|
<B>tbl</B>
|
|
|
|
and update each binding depending on the result of
|
|
<B>f</B>
|
|
|
|
. If
|
|
<B>f</B>
|
|
|
|
returns
|
|
<B>None</B>
|
|
|
|
, the binding is discarded. If it
|
|
returns
|
|
<B>Some new_val</B>
|
|
|
|
, the binding is update to associate the key
|
|
to
|
|
<B>new_val</B>
|
|
|
|
.
|
|
<P>
|
|
Other comments for
|
|
<B>Hashtbl.iter</B>
|
|
|
|
apply as well.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.03.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val fold </I>
|
|
|
|
:
|
|
<B>('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.fold f tbl init</B>
|
|
|
|
computes
|
|
<B>(f kN dN ... (f k1 d1 init)...)</B>
|
|
|
|
,
|
|
where
|
|
<B>k1 ... kN</B>
|
|
|
|
are the keys of all bindings in
|
|
<B>tbl</B>
|
|
|
|
,
|
|
and
|
|
<B>d1 ... dN</B>
|
|
|
|
are the associated values.
|
|
Each binding is presented exactly once to
|
|
<B>f</B>
|
|
|
|
.
|
|
<P>
|
|
The order in which the bindings are passed to
|
|
<B>f</B>
|
|
|
|
is unspecified.
|
|
However, if the table contains several bindings for the same key,
|
|
they are passed to
|
|
<B>f</B>
|
|
|
|
in reverse order of introduction, that is,
|
|
the most recent binding is passed first.
|
|
<P>
|
|
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.
|
|
<P>
|
|
The behavior is not defined if the hash table is modified
|
|
by
|
|
<B>f</B>
|
|
|
|
during the iteration.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val length </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> int</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.length tbl</B>
|
|
|
|
returns the number of bindings in
|
|
<B>tbl</B>
|
|
|
|
.
|
|
It takes constant time. Multiple bindings are counted once each, so
|
|
<B>Hashtbl.length</B>
|
|
|
|
gives the number of times
|
|
<B>Hashtbl.iter</B>
|
|
|
|
calls its
|
|
first argument.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val randomize </I>
|
|
|
|
:
|
|
<B>unit -> unit</B>
|
|
|
|
<P>
|
|
After a call to
|
|
<B>Hashtbl.randomize()</B>
|
|
|
|
, hash tables are created in
|
|
randomized mode by default:
|
|
<B>Hashtbl.create</B>
|
|
|
|
returns randomized
|
|
hash tables, unless the
|
|
<B>~random:false</B>
|
|
|
|
optional parameter is given.
|
|
The same effect can be achieved by setting the
|
|
<B>R</B>
|
|
|
|
parameter in
|
|
the
|
|
<B>OCAMLRUNPARAM</B>
|
|
|
|
environment variable.
|
|
<P>
|
|
It is recommended that applications or Web frameworks that need to
|
|
protect themselves against the denial-of-service attack described
|
|
in
|
|
<B>Hashtbl.create</B>
|
|
|
|
call
|
|
<B>Hashtbl.randomize()</B>
|
|
|
|
at initialization
|
|
time.
|
|
<P>
|
|
Note that once
|
|
<B>Hashtbl.randomize()</B>
|
|
|
|
was called, there is no way
|
|
to revert to the non-randomized default behavior of
|
|
<B>Hashtbl.create</B>
|
|
|
|
.
|
|
This is intentional. Non-randomized hash tables can still be
|
|
created using
|
|
<B>Hashtbl.create ~random:false</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val is_randomized </I>
|
|
|
|
:
|
|
<B>unit -> bool</B>
|
|
|
|
<P>
|
|
return if the tables are currently created in randomized mode by default
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.03.0
|
|
<P>
|
|
<P>
|
|
<I>type statistics </I>
|
|
|
|
= {
|
|
<BR> num_bindings :
|
|
<B>int</B>
|
|
|
|
; (* Number of bindings present in the table.
|
|
Same value as returned by
|
|
<B>Hashtbl.length</B>
|
|
|
|
.
|
|
<BR> *)
|
|
<BR> num_buckets :
|
|
<B>int</B>
|
|
|
|
; (* Number of buckets in the table.
|
|
<BR> *)
|
|
<BR> max_bucket_length :
|
|
<B>int</B>
|
|
|
|
; (* Maximal number of bindings per bucket.
|
|
<BR> *)
|
|
<BR> bucket_histogram :
|
|
<B>int array</B>
|
|
|
|
; (* Histogram of bucket sizes. This array
|
|
<B>histo</B>
|
|
|
|
has
|
|
length
|
|
<B>max_bucket_length + 1</B>
|
|
|
|
. The value of
|
|
<B>histo.(i)</B>
|
|
|
|
is the number of buckets whose size is
|
|
<B>i</B>
|
|
|
|
.
|
|
<BR> *)
|
|
<BR> }
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val stats </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> statistics</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.stats tbl</B>
|
|
|
|
returns statistics about the table
|
|
<B>tbl</B>
|
|
|
|
:
|
|
number of buckets, size of the biggest bucket, distribution of
|
|
buckets by size.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAF"> </A>
|
|
<H3>Iterators</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val to_seq </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> ('a * 'b) Seq.t</B>
|
|
|
|
<P>
|
|
Iterate on the whole table. The order in which the bindings
|
|
appear in the sequence is unspecified. However, if the table contains
|
|
several bindings for the same key, they appear in reversed order of
|
|
introduction, that is, the most recent binding appears first.
|
|
<P>
|
|
The behavior is not defined if the hash table is modified
|
|
during the iteration.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.07
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val to_seq_keys </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> 'a Seq.t</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>Seq.map fst (to_seq m)</B>
|
|
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.07
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val to_seq_values </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> 'b Seq.t</B>
|
|
|
|
<P>
|
|
Same as
|
|
<B>Seq.map snd (to_seq m)</B>
|
|
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.07
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val add_seq </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> ('a * 'b) Seq.t -> unit</B>
|
|
|
|
<P>
|
|
Add the given bindings to the table, using
|
|
<B>Hashtbl.add</B>
|
|
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.07
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val replace_seq </I>
|
|
|
|
:
|
|
<B>('a, 'b) t -> ('a * 'b) Seq.t -> unit</B>
|
|
|
|
<P>
|
|
Add the given bindings to the table, using
|
|
<B>Hashtbl.replace</B>
|
|
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.07
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val of_seq </I>
|
|
|
|
:
|
|
<B>('a * 'b) Seq.t -> ('a, 'b) t</B>
|
|
|
|
<P>
|
|
Build a table from the given bindings. The bindings are added
|
|
in the same order they appear in the sequence, using
|
|
<B>Hashtbl.replace_seq</B>
|
|
|
|
,
|
|
which means that if two pairs have the same key, only the latest one
|
|
will appear in the table.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.07
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAG"> </A>
|
|
<H3>Functorial interface</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
The functorial interface allows the use of specific comparison
|
|
and hash functions, either for performance/security concerns,
|
|
or because keys are not hashable/comparable with the polymorphic builtins.
|
|
<P>
|
|
For instance, one might want to specialize a table for integer keys:
|
|
<B>module IntHash =</B>
|
|
|
|
|
|
|
|
<B>struct</B>
|
|
|
|
<B>type t = int</B>
|
|
|
|
<B>let equal i j = i=j</B>
|
|
|
|
<B>let hash i = i land max_int</B>
|
|
|
|
<B>end</B>
|
|
|
|
<B>module IntHashtbl = Hashtbl.Make(IntHash)</B>
|
|
|
|
|
|
|
|
<B>let h = IntHashtbl.create 17 in</B>
|
|
|
|
|
|
|
|
<B>IntHashtbl.add h 12 hello</B>
|
|
|
|
<B><P>
|
|
</B>
|
|
|
|
This creates a new module
|
|
<B>IntHashtbl</B>
|
|
|
|
, with a new type
|
|
<B>'a</B>
|
|
|
|
<B>IntHashtbl.t</B>
|
|
|
|
of tables from
|
|
<B>int</B>
|
|
|
|
to
|
|
<B>'a</B>
|
|
|
|
. In this example,
|
|
<B>h</B>
|
|
|
|
contains
|
|
<B>string</B>
|
|
|
|
values so its type is
|
|
<B>string IntHashtbl.t</B>
|
|
|
|
.
|
|
<P>
|
|
Note that the new type
|
|
<B>'a IntHashtbl.t</B>
|
|
|
|
is not compatible with
|
|
the type
|
|
<B>('a,'b) Hashtbl.t</B>
|
|
|
|
of the generic interface. For
|
|
example,
|
|
<B>Hashtbl.length h</B>
|
|
|
|
would not type-check, you must use
|
|
<B>IntHashtbl.length</B>
|
|
|
|
.
|
|
<P>
|
|
|
|
<I>module type HashedType = </I>
|
|
|
|
<B>sig end</B>
|
|
|
|
<P>
|
|
<P>
|
|
The input signature of the functor
|
|
<B>Hashtbl.Make</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<I>module type S = </I>
|
|
|
|
<B>sig end</B>
|
|
|
|
<P>
|
|
<P>
|
|
The output signature of the functor
|
|
<B>Hashtbl.Make</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<I>module Make : </I>
|
|
|
|
<B>functor (H : HashedType) -> sig end</B>
|
|
|
|
<P>
|
|
<P>
|
|
Functor building an implementation of the hashtable structure.
|
|
The functor
|
|
<B>Hashtbl.Make</B>
|
|
|
|
returns a structure containing
|
|
a type
|
|
<B>key</B>
|
|
|
|
of keys and a type
|
|
<B>'a t</B>
|
|
|
|
of hash tables
|
|
associating data of type
|
|
<B>'a</B>
|
|
|
|
to keys of type
|
|
<B>key</B>
|
|
|
|
.
|
|
The operations perform similarly to those of the generic
|
|
interface, but use the hashing and equality functions
|
|
specified in the functor argument
|
|
<B>H</B>
|
|
|
|
instead of generic
|
|
equality and hashing. Since the hash function is not seeded,
|
|
the
|
|
<B>create</B>
|
|
|
|
operation of the result structure always returns
|
|
non-randomized hash tables.
|
|
<P>
|
|
<P>
|
|
<I>module type SeededHashedType = </I>
|
|
|
|
<B>sig end</B>
|
|
|
|
<P>
|
|
<P>
|
|
The input signature of the functor
|
|
<B>Hashtbl.MakeSeeded</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<I>module type SeededS = </I>
|
|
|
|
<B>sig end</B>
|
|
|
|
<P>
|
|
<P>
|
|
The output signature of the functor
|
|
<B>Hashtbl.MakeSeeded</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<I>module MakeSeeded : </I>
|
|
|
|
<B>functor (H : SeededHashedType) -> sig end</B>
|
|
|
|
<P>
|
|
<P>
|
|
Functor building an implementation of the hashtable structure.
|
|
The functor
|
|
<B>Hashtbl.MakeSeeded</B>
|
|
|
|
returns a structure containing
|
|
a type
|
|
<B>key</B>
|
|
|
|
of keys and a type
|
|
<B>'a t</B>
|
|
|
|
of hash tables
|
|
associating data of type
|
|
<B>'a</B>
|
|
|
|
to keys of type
|
|
<B>key</B>
|
|
|
|
.
|
|
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</B>
|
|
|
|
instead of generic
|
|
equality and hashing. The
|
|
<B>create</B>
|
|
|
|
operation of the
|
|
result structure supports the
|
|
<B>~random</B>
|
|
|
|
optional parameter
|
|
and returns randomized hash tables if
|
|
<B>~random:true</B>
|
|
|
|
is passed
|
|
or if randomization is globally on (see
|
|
<B>Hashtbl.randomize</B>
|
|
|
|
).
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<A NAME="lbAH"> </A>
|
|
<H3>The polymorphic hash functions</H3>
|
|
|
|
<P>
|
|
<P>
|
|
|
|
<P>
|
|
<I>val hash </I>
|
|
|
|
:
|
|
<B>'a -> int</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.hash x</B>
|
|
|
|
associates a nonnegative integer to any value of
|
|
any type. It is guaranteed that
|
|
if
|
|
<B>x = y</B>
|
|
|
|
or
|
|
<B>Stdlib.compare x y = 0</B>
|
|
|
|
, then
|
|
<B>hash x = hash y</B>
|
|
|
|
.
|
|
Moreover,
|
|
<B>hash</B>
|
|
|
|
always terminates, even on cyclic structures.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val seeded_hash </I>
|
|
|
|
:
|
|
<B>int -> 'a -> int</B>
|
|
|
|
<P>
|
|
A variant of
|
|
<B>Hashtbl.hash</B>
|
|
|
|
that is further parameterized by
|
|
an integer seed.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val hash_param </I>
|
|
|
|
:
|
|
<B>int -> int -> 'a -> int</B>
|
|
|
|
<P>
|
|
<P>
|
|
<B>Hashtbl.hash_param meaningful total x</B>
|
|
|
|
computes a hash value for
|
|
<B>x</B>
|
|
|
|
,
|
|
with the same properties as for
|
|
<B>hash</B>
|
|
|
|
. The two extra integer
|
|
parameters
|
|
<B>meaningful</B>
|
|
|
|
and
|
|
<B>total</B>
|
|
|
|
give more precise control over
|
|
hashing. Hashing performs a breadth-first, left-to-right traversal
|
|
of the structure
|
|
<B>x</B>
|
|
|
|
, stopping after
|
|
<B>meaningful</B>
|
|
|
|
meaningful nodes
|
|
were encountered, or
|
|
<B>total</B>
|
|
|
|
nodes (meaningful or not) were
|
|
encountered. If
|
|
<B>total</B>
|
|
|
|
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</B>
|
|
|
|
and
|
|
<B>total</B>
|
|
|
|
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</B>
|
|
|
|
and
|
|
<B>total</B>
|
|
|
|
govern the tradeoff between accuracy and speed. As default
|
|
choices,
|
|
<B>Hashtbl.hash</B>
|
|
|
|
and
|
|
<B>Hashtbl.seeded_hash</B>
|
|
|
|
take
|
|
<B>meaningful = 10</B>
|
|
|
|
and
|
|
<B>total = 100</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<P>
|
|
<I>val seeded_hash_param </I>
|
|
|
|
:
|
|
<B>int -> int -> int -> 'a -> int</B>
|
|
|
|
<P>
|
|
A variant of
|
|
<B>Hashtbl.hash_param</B>
|
|
|
|
that is further parameterized by
|
|
an integer seed. Usage:
|
|
<B>Hashtbl.seeded_hash_param meaningful total seed x</B>
|
|
|
|
.
|
|
<P>
|
|
<P>
|
|
<B>Since</B>
|
|
|
|
4.00.0
|
|
<P>
|
|
<P>
|
|
<P>
|
|
|
|
<HR>
|
|
<A NAME="index"> </A><H2>Index</H2>
|
|
<DL>
|
|
<DT id="1"><A HREF="#lbAB">NAME</A><DD>
|
|
<DT id="2"><A HREF="#lbAC">Module</A><DD>
|
|
<DT id="3"><A HREF="#lbAD">Documentation</A><DD>
|
|
<DL>
|
|
<DT id="4"><A HREF="#lbAE">Generic interface</A><DD>
|
|
<DT id="5"><A HREF="#lbAF">Iterators</A><DD>
|
|
<DT id="6"><A HREF="#lbAG">Functorial interface</A><DD>
|
|
<DT id="7"><A HREF="#lbAH">The polymorphic hash functions</A><DD>
|
|
</DL>
|
|
</DL>
|
|
<HR>
|
|
This document was created by
|
|
<A HREF="/cgi-bin/man/man2html">man2html</A>,
|
|
using the manual pages.<BR>
|
|
Time: 00:05:45 GMT, March 31, 2021
|
|
</BODY>
|
|
</HTML>
|