Functor MakeHash
functor MakeHash (H : HashedType) : HASH where type key = H.t = struct ... end
Hash tables.
Hash tables are hashed association tables, with in-place modification.
|
Input module H : HashedType
|
|
type t
The type of the hashtable keys.
val equal : t -> t -> bool
The equality predicate used to compare keys.
val hash : t -> int
A hashing function on keys, returning a non-negative
integer. It must be such that if two keys are equal according
to
equal, then they must have identical hash values as computed
by
hash.
Examples: suitable (
equal,
hash) pairs for arbitrary key
types include
(
(=),
Hashtbl.hash) for comparing objects by structure, and
(
(==),
Hashtbl.hash) for comparing objects by addresses
(e.g. for mutable or cyclic keys).
type key
The type of the hash table keys.
type 'a t
The type of hash tables from type
key to type
'a.
val create : int -> 'a t
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 t -> unit
Empty a hash table.
val add : 'a t -> key -> 'a -> unit
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
remove tbl x,
the previous binding for
x, if any, is restored.
(Same behavior as with association lists.)
val copy : 'a t -> 'a t
Return a copy of the given hashtable.
val find : 'a t -> key -> 'a
find tbl x returns the current binding of x in tbl,
or raises Not_found if no such binding exists.
val find_all : 'a t -> key -> 'a list
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 t -> 'a -> bool
mem tbl x checks if x is bound in tbl.
val remove : 'a t -> key -> unit
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 t -> key -> 'a -> unit
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
remove tbl x
followed by
add tbl x y.
val iter : (key -> 'a -> unit) -> 'a t -> unit
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.
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
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.
The order in which the bindings are passed to
f is unspecified. Each binding is presented exactly once
to f.