Module MoreLabels.Hashtbl
Contents
Instructions: Use this module in your project
In the IDE (CLion, Visual Studio Code, Xcode, etc.) you use for your DkSDK project:
Add the following to your project's
dependencies/CMakeLists.txt:DkSDKProject_DeclareAvailable(ocaml CONSTRAINT "= 4.14.0" FINDLIBS str unix runtime_events threads dynlink) DkSDKProject_MakeAvailable(ocaml)Add the
Findlib::ocamllibrary to any desired targets insrc/*/CMakeLists.txt:target_link_libraries(YourPackage_YourLibraryName # ... existing libraries, if any ... Findlib::ocaml)Click your IDE's
Buildbutton
Not using DkSDK?
FIRST, do one or all of the following:
Run:
opam install ocaml.4.14.0Edit your
dune-projectand add:(package (name YourExistingPackage) (depends ; ... existing dependenices ... (ocaml (>= 4.14.0))))Then run:
dune build *.opam # if this fails, run: dune buildEdit your
<package>.opamfile and add:depends: [ # ... existing dependencies ... "ocaml" {>= "4.14.0"} ]Then run:
opam install . --deps-only
FINALLY, add the library to any desired (library)and/or (executable) targets in your **/dune files:
(library
(name YourLibrary)
; ... existing library options ...
(libraries
; ... existing libraries ...
))
(executable
(name YourExecutable)
; ... existing executable options ...
(libraries
; ... existing libraries ...
))Generic interface
type``(!'a, !'b) t`` = ``('a,'b)``Hashtbl.t
The type of hash tables from type 'a to type 'b.
valcreate : ``?random:bool->``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.
The optional ~``random parameter (a boolean) controls whether the
internal organization of the hash table is randomized at each execution
of Hashtbl.create or deterministic over all executions.
A hash table that is created with ~``random set to false uses a
fixed hash function (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.
A hash table that is created with ~``random set to true uses the
seeded hash function seeded_hash with a seed that
is randomly chosen at hash table creation time. In effect, the hash
function used is randomly selected among 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 fold or iter is no longer
deterministic: elements are enumerated in different orders at different
runs of the program.
If no ~``random parameter is given, hash tables are created in
non-random mode by default. This default can be changed either
programmatically by calling randomize or by setting
the R flag in the OCAMLRUNPARAM environment variable.
-
before 4.00.0
the
~``randomparameter was not present and all hash tables were created in non-randomized mode.
valclear : ``('a,'b)``t->unit
Empty a hash table. Use reset instead of clear to shrink the size of
the bucket table to its initial size.
valreset : ``('a,'b)``t->unit
Empty a hash table and shrink the size of the bucket table to its initial size.
- since 4.00.0
valadd : ``('a,'b)``t->``key:'a->``data:'b->unit
Hashtbl.add tbl ~key ~data adds a binding of key to data in table
tbl. Previous bindings for key are not removed, but simply hidden.
That is, after performing remove tbl key, the
previous binding for key, if any, is restored. (Same behavior as with
association lists.)
valfind : ``('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.
valfind_opt : ``('a,'b)``t->'a->'boption
Hashtbl.find_opt tbl x returns the current binding of x in tbl, or
None if no such binding exists.
- since 4.05
valfind_all : ``('a,'b)``t->'a->'blist
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.
valmem : ``('a,'b)``t->'a->bool
Hashtbl.mem tbl x checks if x is bound in tbl.
valremove : ``('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.
valreplace : ``('a,'b)``t->``key:'a->``data:'b->unit
valiter : ``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. Each binding is presented exactly once to f.
The order in which the bindings are passed to f is unspecified.
However, if the table contains several bindings for the same key, they
are passed to f in reverse order of introduction, that is, the most
recent binding is passed first.
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.
The behavior is not specified if the hash table is modified by f
during the iteration.
valfilter_map_inplace : ``f:``(``key:'a->``data:'b->'boption``)``->``('a,'b)``t->unit
Hashtbl.filter_map_inplace ~f tbl applies f to all bindings in table
tbl and update each binding depending on the result of f. If f
returns None, the binding is discarded. If it returns Some new_val,
the binding is update to associate the key to new_val.
Other comments for iter apply as well.
- since 4.03.0
valfold : ``f:``(``key:'a->``data:'b->'c->'c)``->``('a,'b)``t->``init:'c->'c
Hashtbl.fold ~f tbl ~init computes (f kN dN ... (f k1 d1 init)...),
where k1 ... kN are the keys of all bindings in tbl, and d1 ... dN
are the associated values. Each binding is presented exactly once to
f.
The order in which the bindings are passed to f is unspecified.
However, if the table contains several bindings for the same key, they
are passed to f in reverse order of introduction, that is, the most
recent binding is passed first.
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.
The behavior is not specified if the hash table is modified by f
during the iteration.
vallength : ``('a,'b)``t->int
Hashtbl.length tbl returns the number of bindings in tbl. It takes
constant time. Multiple bindings are counted once each, so
Hashtbl.length gives the number of times Hashtbl.iter calls its
first argument.
valrandomize : ``unit->unit
After a call to Hashtbl.randomize(), hash tables are created in
randomized mode by default: create returns randomized
hash tables, unless the ~random:false optional parameter is given. The
same effect can be achieved by setting the R parameter in the
OCAMLRUNPARAM environment variable.
It is recommended that applications or Web frameworks that need to
protect themselves against the denial-of-service attack described in
create call Hashtbl.randomize() at initialization
time.
Note that once Hashtbl.randomize() was called, there is no way to
revert to the non-randomized default behavior of
create. This is intentional. Non-randomized hash tables
can still be created using Hashtbl.create ~random:false.
- since 4.00.0
valis_randomized : ``unit->bool
Return true if the tables are currently created in randomized mode by
default, false otherwise.
- since 4.03.0
Return a copy of the given hashtable. Unlike copy,
rebuild h re-hashes all the (key, value) entries of
the original table h. The returned hash table is randomized if h was
randomized, or the optional random parameter is true, or if the
default is to create randomized hash tables; see create
for more information.
rebuild can safely be used to import a hash table
built by an old version of the Hashtbl module, then marshaled to
persistent storage. After unmarshaling, apply rebuild
to produce a hash table for the current version of the Hashtbl
module.
- since 4.12.0
typestatistics`` =Hashtbl.statistics= ``{
num_bindings : int;(* Number of bindings present in the table. Same value as returned by
length.*)
num_buckets : int;(* Number of buckets in the table.
*)
max_bucket_length : int;(* Maximal number of bindings per bucket.
*)
bucket_histogram : ``int array``;(* Histogram of bucket sizes. This array
histohas lengthmax_bucket_length + 1. The value ofhisto.(i)is the number of buckets whose size isi.*)
}
- since 4.00.0
valstats : ``('a,'b)``t->statistics
Hashtbl.stats tbl returns statistics about the table tbl: number of
buckets, size of the biggest bucket, distribution of buckets by size.
- since 4.00.0
Hash tables and Sequences
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.
The behavior is not specified if the hash table is modified during the iteration.
- since 4.07
Add the given bindings to the table, using add
- since 4.07
Add the given bindings to the table, using replace
- since 4.07
Build a table from the given bindings. The bindings are added in the
same order they appear in the sequence, using
replace_seq, which means that if two pairs have
the same key, only the latest one will appear in the table.
- since 4.07
Functorial interface
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.
For instance, one might want to specialize a table for integer keys:
module IntHash =
struct
type t = int
let equal i j = i=j
let hash i = i land max_int
end
module IntHashtbl = Hashtbl.Make(IntHash)
let h = IntHashtbl.create 17 in
IntHashtbl.add h 12 "hello"This creates a new module IntHashtbl, with a new type
'a IntHashtbl.t of tables from int to 'a. In this example, h
contains string values so its type is string IntHashtbl.t.
Note that the new type 'a IntHashtbl.t is not compatible with the type
('a,'b) Hashtbl.t of the generic interface. For example,
Hashtbl.length h would not type-check, you must use
IntHashtbl.length.
moduletypeHashedType=sig...end
The input signature of the functor
Make.
moduleMake(H:HashedType) :Swithtypekey=H.tandtype``'at='aHashtbl.Make(H).t
Functor building an implementation of the hashtable structure. The
functor Hashtbl.Make returns a structure containing a type key of
keys and a type 'a t of hash tables associating data of type 'a to
keys of type key. The operations perform similarly to those of the
generic interface, but use the hashing and equality functions specified
in the functor argument H instead of generic equality and hashing.
Since the hash function is not seeded, the create operation of the
result structure always returns non-randomized hash tables.
moduletypeSeededHashedType=sig...end
The input signature of the functor
MakeSeeded.
moduletypeSeededS=sig...end
The output signature of the functor
MakeSeeded.
moduleMakeSeeded(H:SeededHashedType) :SeededSwithtypekey=H.tandtype``'at='aHashtbl.MakeSeeded(H).t
Functor building an implementation of the hashtable structure. The
functor Hashtbl.MakeSeeded returns a structure containing a type key
of keys and a type 'a t of hash tables associating data of type 'a
to keys of type key. The operations perform similarly to those of the
generic interface, but use the seeded hashing and equality functions
specified in the functor argument H instead of generic equality and
hashing. The create operation of the result structure supports the
~``random optional parameter and returns randomized hash tables if
~random:true is passed or if randomization is globally on (see
Hashtbl.randomize).
The polymorphic hash functions
valhash :'a->int
Hashtbl.hash x associates a nonnegative integer to any value of any
type. It is guaranteed that if x = y or Stdlib.compare x y = 0, then
hash x = hash y. Moreover, hash always terminates, even on cyclic
structures.
valseeded_hash : ``int->'a->int
A variant of hash that is further parameterized by an
integer seed.
- since 4.00.0
valhash_param : ``int->``int->'a->int
Hashtbl.hash_param meaningful total x computes a hash value for x,
with the same properties as for hash. The two extra integer parameters
meaningful and total give more precise control over hashing. Hashing
performs a breadth-first, left-to-right traversal of the structure x,
stopping after meaningful meaningful nodes were encountered, or
total nodes (meaningful or not) were encountered. If 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 meaningful and 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 meaningful and total govern the tradeoff between accuracy
and speed. As default choices, hash and
seeded_hash take meaningful = 10 and
total = 100.
valseeded_hash_param : ``int->``int->``int->'a->int
A variant of hash_param that is further
parameterized by an integer seed. Usage:
Hashtbl.seeded_hash_param meaningful total seed x.
- since 4.00.0
