1Stdlib.Hashtbl(3) OCaml library Stdlib.Hashtbl(3)
2
6 Stdlib.Hashtbl - no description
7
9 Module Stdlib.Hashtbl
10
12 Module Hashtbl
13 : (module Stdlib__Hashtbl)
14 Generic interface
24 type ('a, 'b) t
25 The type of hash tables from type 'a to type 'b .
28 val create : ?random:bool -> int -> ('a, 'b) t
32 Hashtbl.create n creates a new, empty hash table, with initial size n .
35 For best results, n should be on the order of the expected number of
36 elements that will be in the table. The table grows as needed, so n is
37 just an initial guess.
38 The optional ~ random parameter (a boolean) controls whether the inter‐
40 nal organization of the hash table is randomized at each execution of
41 Hashtbl.create or deterministic over all executions.
42 A hash table that is created with ~ random set to false uses a fixed
44 hash function ( Hashtbl.hash ) to distribute keys among buckets. As a
45 consequence, collisions between keys happen deterministically. In
46 Web-facing applications or other security-sensitive applications, the
47 deterministic collision patterns can be exploited by a malicious user
48 to create a denial-of-service attack: the attacker sends input crafted
49 to create many collisions in the table, slowing the application down.
50 A hash table that is created with ~ random set to true uses the seeded
52 hash function Hashtbl.seeded_hash with a seed that is randomly chosen
53 at hash table creation time. In effect, the hash function used is ran‐
54 domly selected among 2^{30} different hash functions. All these hash
55 functions have different collision patterns, rendering ineffective the
56 denial-of-service attack described above. However, because of random‐
57 ization, enumerating all elements of the hash table using Hashtbl.fold
58 or Hashtbl.iter is no longer deterministic: elements are enumerated in
59 different orders at different runs of the program.
60 If no ~ random parameter is given, hash tables are created in non-ran‐
62 dom mode by default. This default can be changed either programmati‐
63 cally by calling Hashtbl.randomize or by setting the R flag in the
64 OCAMLRUNPARAM environment variable.
65 Before4.00.0 the ~ random parameter was not present and all hash tables
68 were created in non-randomized mode.
69 val clear : ('a, 'b) t -> unit
74 Empty a hash table. Use reset instead of clear to shrink the size of
76 the bucket table to its initial size.
77 val reset : ('a, 'b) t -> unit
81 Empty a hash table and shrink the size of the bucket table to its ini‐
83 tial size.
84 Since 4.00.0
87 val copy : ('a, 'b) t -> ('a, 'b) t
91 Return a copy of the given hashtable.
93 val add : ('a, 'b) t -> 'a -> 'b -> unit
97 Hashtbl.add tbl key data adds a binding of key to data in table tbl .
100 Previous bindings for key are not removed, but simply hidden. That is,
101 after performing Hashtbl.remove tbl key , the previous binding for key
102 , if any, is restored. (Same behavior as with association lists.)
103 val find : ('a, 'b) t -> 'a -> 'b
107 Hashtbl.find tbl x returns the current binding of x in tbl , or raises
110 Not_found if no such binding exists.
111 val find_opt : ('a, 'b) t -> 'a -> 'b option
115 Hashtbl.find_opt tbl x returns the current binding of x in tbl , or
118 None if no such binding exists.
119 Since 4.05
122 val find_all : ('a, 'b) t -> 'a -> 'b list
126 Hashtbl.find_all tbl x returns the list of all data associated with x
129 in tbl . The current binding is returned first, then the previous
130 bindings, in reverse order of introduction in the table.
131 val mem : ('a, 'b) t -> 'a -> bool
135 Hashtbl.mem tbl x checks if x is bound in tbl .
138 val remove : ('a, 'b) t -> 'a -> unit
142 Hashtbl.remove tbl x removes the current binding of x in tbl , restor‐
145 ing the previous binding if it exists. It does nothing if x is not
146 bound in tbl .
147 val replace : ('a, 'b) t -> 'a -> 'b -> unit
151 Hashtbl.replace tbl key data replaces the current binding of key in tbl
154 by a binding of key to data . If key is unbound in tbl , a binding of
155 key to data is added to tbl . This is functionally equivalent to
156 Hashtbl.remove tbl key followed by Hashtbl.add tbl key data .
157 val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
161 Hashtbl.iter f tbl applies f to all bindings in table tbl . f receives
164 the key as first argument, and the associated value as second argument.
165 Each binding is presented exactly once to f .
166 The order in which the bindings are passed to f is unspecified. How‐
168 ever, if the table contains several bindings for the same key, they are
169 passed to f in reverse order of introduction, that is, the most recent
170 binding is passed first.
171 If the hash table was created in non-randomized mode, the order in
173 which the bindings are enumerated is reproducible between successive
174 runs of the program, and even between minor versions of OCaml. For
175 randomized hash tables, the order of enumeration is entirely random.
176 The behavior is not specified if the hash table is modified by f during
178 the iteration.
179 val filter_map_inplace : ('a -> 'b -> 'b option) -> ('a, 'b) t -> unit
183 Hashtbl.filter_map_inplace f tbl applies f to all bindings in table tbl
186 and update each binding depending on the result of f . If f returns
187 None , the binding is discarded. If it returns Some new_val , the
188 binding is update to associate the key to new_val .
189 Other comments for Hashtbl.iter apply as well.
191 Since 4.03.0
194 val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
198 Hashtbl.fold f tbl init computes (f kN dN ... (f k1 d1 init)...) ,
201 where k1 ... kN are the keys of all bindings in tbl , and d1 ... dN are
202 the associated values. Each binding is presented exactly once to f .
203 The order in which the bindings are passed to f is unspecified. How‐
205 ever, if the table contains several bindings for the same key, they are
206 passed to f in reverse order of introduction, that is, the most recent
207 binding is passed first.
208 If the hash table was created in non-randomized mode, the order in
210 which the bindings are enumerated is reproducible between successive
211 runs of the program, and even between minor versions of OCaml. For
212 randomized hash tables, the order of enumeration is entirely random.
213 The behavior is not specified if the hash table is modified by f during
215 the iteration.
216 val length : ('a, 'b) t -> int
220 Hashtbl.length tbl returns the number of bindings in tbl . It takes
223 constant time. Multiple bindings are counted once each, so
224 Hashtbl.length gives the number of times Hashtbl.iter calls its first
225 argument.
226 val randomize : unit -> unit
230 After a call to Hashtbl.randomize() , hash tables are created in ran‐
232 domized mode by default: Hashtbl.create returns randomized hash tables,
233 unless the ~random:false optional parameter is given. The same effect
234 can be achieved by setting the R parameter in the OCAMLRUNPARAM envi‐
235 ronment variable.
236 It is recommended that applications or Web frameworks that need to pro‐
238 tect themselves against the denial-of-service attack described in
239 Hashtbl.create call Hashtbl.randomize() at initialization time.
240 Note that once Hashtbl.randomize() was called, there is no way to re‐
242 vert to the non-randomized default behavior of Hashtbl.create . This
243 is intentional. Non-randomized hash tables can still be created using
244 Hashtbl.create ~random:false .
245 Since 4.00.0
248 val is_randomized : unit -> bool
252 Return true if the tables are currently created in randomized mode by
254 default, false otherwise.
255 Since 4.03.0
258 val rebuild : ?random:bool -> ('a, 'b) t -> ('a, 'b) t
262 Return a copy of the given hashtable. Unlike Hashtbl.copy ,
264 Hashtbl.rebuild h re-hashes all the (key, value) entries of the origi‐
265 nal table h . The returned hash table is randomized if h was random‐
266 ized, or the optional random parameter is true, or if the default is to
267 create randomized hash tables; see Hashtbl.create for more information.
268 Hashtbl.rebuild can safely be used to import a hash table built by an
271 old version of the Hashtbl module, then marshaled to persistent stor‐
272 age. After unmarshaling, apply Hashtbl.rebuild to produce a hash table
273 for the current version of the Hashtbl module.
274 Since 4.12.0
277 type statistics = {
280 num_bindings : int ; (* Number of bindings present in the table.
281 Same value as returned by Hashtbl.length .
282 *)
283 num_buckets : int ; (* Number of buckets in the table.
284 *)
285 max_bucket_length : int ; (* Maximal number of bindings per bucket.
286 *)
287 bucket_histogram : int array ; (* Histogram of bucket sizes. This
288 array histo has length max_bucket_length + 1 . The value of histo.(i)
289 is the number of buckets whose size is i .
290 *)
291 }
292 Since 4.00.0
295 val stats : ('a, 'b) t -> statistics
299 Hashtbl.stats tbl returns statistics about the table tbl : number of
302 buckets, size of the biggest bucket, distribution of buckets by size.
303 Since 4.00.0
306 Hash tables and Sequences
311 val to_seq : ('a, 'b) t -> ('a * 'b) Seq.t
312 Iterate on the whole table. The order in which the bindings appear in
314 the sequence is unspecified. However, if the table contains several
315 bindings for the same key, they appear in reversed order of introduc‐
316 tion, that is, the most recent binding appears first.
317 The behavior is not specified if the hash table is modified during the
319 iteration.
320 Since 4.07
323 val to_seq_keys : ('a, 'b) t -> 'a Seq.t
327 Same as Seq.map fst (to_seq m)
329 Since 4.07
333 val to_seq_values : ('a, 'b) t -> 'b Seq.t
337 Same as Seq.map snd (to_seq m)
339 Since 4.07
343 val add_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
347 Add the given bindings to the table, using Hashtbl.add
349 Since 4.07
353 val replace_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
357 Add the given bindings to the table, using Hashtbl.replace
359 Since 4.07
363 val of_seq : ('a * 'b) Seq.t -> ('a, 'b) t
367 Build a table from the given bindings. The bindings are added in the
369 same order they appear in the sequence, using Hashtbl.replace_seq ,
370 which means that if two pairs have the same key, only the latest one
371 will appear in the table.
372 Since 4.07
375 Functorial interface
380 The functorial interface allows the use of specific comparison and hash
381 functions, either for performance/security concerns, or because keys
382 are not hashable/comparable with the polymorphic builtins.
383 For instance, one might want to specialize a table for integer keys:
385 module IntHash =
386 struct
387 type t = int
388 let equal i j = i=j
389 let hash i = i land max_int
390 end
391 module IntHashtbl = Hashtbl.Make(IntHash)
393 let h = IntHashtbl.create 17 in
395 IntHashtbl.add h 12 "hello"
396 This creates a new module IntHashtbl , with a new type 'a
399 IntHashtbl.t of tables from int to 'a . In this example, h contains
400 string values so its type is string IntHashtbl.t .
401 Note that the new type 'a IntHashtbl.t is not compatible with the type
403 ('a,'b) Hashtbl.t of the generic interface. For example, Hashtbl.length
404 h would not type-check, you must use IntHashtbl.length .
405 module type HashedType = sig end
407 The input signature of the functor Hashtbl.Make .
410 module type S = sig end
413 The output signature of the functor Hashtbl.Make .
416 module Make : functor (H : HashedType) -> sig end
419 Functor building an implementation of the hashtable structure. The
422 functor Hashtbl.Make returns a structure containing a type key of keys
423 and a type 'a t of hash tables associating data of type 'a to keys of
424 type key . The operations perform similarly to those of the generic
425 interface, but use the hashing and equality functions specified in the
426 functor argument H instead of generic equality and hashing. Since the
427 hash function is not seeded, the create operation of the result struc‐
428 ture always returns non-randomized hash tables.
429 module type SeededHashedType = sig end
432 The input signature of the functor Hashtbl.MakeSeeded .
435 Since 4.00.0
438 module type SeededS = sig end
441 The output signature of the functor Hashtbl.MakeSeeded .
444 Since 4.00.0
447 module MakeSeeded : functor (H : SeededHashedType) -> sig end
450 Functor building an implementation of the hashtable structure. The
453 functor Hashtbl.MakeSeeded returns a structure containing a type key of
454 keys and a type 'a t of hash tables associating data of type 'a to keys
455 of type key . The operations perform similarly to those of the generic
456 interface, but use the seeded hashing and equality functions specified
457 in the functor argument H instead of generic equality and hashing. The
458 create operation of the result structure supports the ~ random optional
459 parameter and returns randomized hash tables if ~random:true is passed
460 or if randomization is globally on (see Hashtbl.randomize ).
461 Since 4.00.0
464 The polymorphic hash functions
469 val hash : 'a -> int
470 Hashtbl.hash x associates a nonnegative integer to any value of any
473 type. It is guaranteed that if x = y or Stdlib.compare x y = 0 , then
474 hash x = hash y . Moreover, hash always terminates, even on cyclic
475 structures.
476 val seeded_hash : int -> 'a -> int
480 A variant of Hashtbl.hash that is further parameterized by an integer
482 seed.
483 Since 4.00.0
486 val hash_param : int -> int -> 'a -> int
490 Hashtbl.hash_param meaningful total x computes a hash value for x ,
493 with the same properties as for hash . The two extra integer parameters
494 meaningful and total give more precise control over hashing. Hashing
495 performs a breadth-first, left-to-right traversal of the structure x ,
496 stopping after meaningful meaningful nodes were encountered, or total
497 nodes (meaningful or not) were encountered. If total as specified by
498 the user exceeds a certain value, currently 256, then it is capped to
499 that value. Meaningful nodes are: integers; floating-point numbers;
500 strings; characters; booleans; and constant constructors. Larger values
501 of meaningful and total means that more nodes are taken into account to
502 compute the final hash value, and therefore collisions are less likely
503 to happen. However, hashing takes longer. The parameters meaningful
504 and total govern the tradeoff between accuracy and speed. As default
505 choices, Hashtbl.hash and Hashtbl.seeded_hash take meaningful = 10 and
506 total = 100 .
507 val seeded_hash_param : int -> int -> int -> 'a -> int
511 A variant of Hashtbl.hash_param that is further parameterized by an in‐
513 teger seed. Usage: Hashtbl.seeded_hash_param meaningful total seed x .
514 Since 4.00.0
517OCamldoc 2023-01-23 Stdlib.Hashtbl(3)