1MoreLabels.Hashtbl(3) OCaml library MoreLabels.Hashtbl(3)
2
6 MoreLabels.Hashtbl - no description
7
9 Module MoreLabels.Hashtbl
10
12 Module Hashtbl
13 : sig end
14 Hash tables and hash functions.
24 Hash tables are hashed association tables, with in-place modification.
26 Generic interface
28 type ('a, 'b) t = ('a, 'b) Hashtbl.t
29 The type of hash tables from type 'a to type 'b .
32 val create : ?random:bool -> int -> ('a, 'b) t
36 Hashtbl.create n creates a new, empty hash table, with initial size n .
39 For best results, n should be on the order of the expected number of
40 elements that will be in the table. The table grows as needed, so n is
41 just an initial guess.
42 The optional ~ random parameter (a boolean) controls whether the inter‐
44 nal organization of the hash table is randomized at each execution of
45 Hashtbl.create or deterministic over all executions.
46 A hash table that is created with ~ random set to false uses a fixed
48 hash function ( MoreLabels.Hashtbl.hash ) to distribute keys among
49 buckets. As a consequence, collisions between keys happen determinis‐
50 tically. In Web-facing applications or other security-sensitive appli‐
51 cations, the deterministic collision patterns can be exploited by a ma‐
52 licious user to create a denial-of-service attack: the attacker sends
53 input crafted to create many collisions in the table, slowing the ap‐
54 plication down.
55 A hash table that is created with ~ random set to true uses the seeded
57 hash function MoreLabels.Hashtbl.seeded_hash with a seed that is ran‐
58 domly chosen at hash table creation time. In effect, the hash function
59 used is randomly selected among 2^{30} different hash functions. All
60 these hash functions have different collision patterns, rendering inef‐
61 fective the denial-of-service attack described above. However, because
62 of randomization, enumerating all elements of the hash table using
63 MoreLabels.Hashtbl.fold or MoreLabels.Hashtbl.iter is no longer deter‐
64 ministic: elements are enumerated in different orders at different runs
65 of the program.
66 If no ~ random parameter is given, hash tables are created in non-ran‐
68 dom mode by default. This default can be changed either programmati‐
69 cally by calling MoreLabels.Hashtbl.randomize or by setting the R flag
70 in the OCAMLRUNPARAM environment variable.
71 Before4.00.0 the ~ random parameter was not present and all hash tables
74 were created in non-randomized mode.
75 val clear : ('a, 'b) t -> unit
80 Empty a hash table. Use reset instead of clear to shrink the size of
82 the bucket table to its initial size.
83 val reset : ('a, 'b) t -> unit
87 Empty a hash table and shrink the size of the bucket table to its ini‐
89 tial size.
90 Since 4.00.0
93 val copy : ('a, 'b) t -> ('a, 'b) t
97 Return a copy of the given hashtable.
99 val add : ('a, 'b) t -> key:'a -> data:'b -> unit
103 Hashtbl.add tbl ~key ~data adds a binding of key to data in table tbl .
106 Previous bindings for key are not removed, but simply hidden. That is,
107 after performing MoreLabels.Hashtbl.remove tbl key , the previous bind‐
108 ing for key , if any, is restored. (Same behavior as with association
109 lists.)
110 val find : ('a, 'b) t -> 'a -> 'b
114 Hashtbl.find tbl x returns the current binding of x in tbl , or raises
117 Not_found if no such binding exists.
118 val find_opt : ('a, 'b) t -> 'a -> 'b option
122 Hashtbl.find_opt tbl x returns the current binding of x in tbl , or
125 None if no such binding exists.
126 Since 4.05
129 val find_all : ('a, 'b) t -> 'a -> 'b list
133 Hashtbl.find_all tbl x returns the list of all data associated with x
136 in tbl . The current binding is returned first, then the previous
137 bindings, in reverse order of introduction in the table.
138 val mem : ('a, 'b) t -> 'a -> bool
142 Hashtbl.mem tbl x checks if x is bound in tbl .
145 val remove : ('a, 'b) t -> 'a -> unit
149 Hashtbl.remove tbl x removes the current binding of x in tbl , restor‐
152 ing the previous binding if it exists. It does nothing if x is not
153 bound in tbl .
154 val replace : ('a, 'b) t -> key:'a -> data:'b -> unit
158 Hashtbl.replace tbl ~key ~data replaces the current binding of key in
161 tbl by a binding of key to data . If key is unbound in tbl , a binding
162 of key to data is added to tbl . This is functionally equivalent to
163 MoreLabels.Hashtbl.remove tbl key followed by MoreLabels.Hashtbl.add
164 tbl key data .
165 val iter : f:(key:'a -> data:'b -> unit) -> ('a, 'b) t -> unit
169 Hashtbl.iter ~f tbl applies f to all bindings in table tbl . f re‐
172 ceives the key as first argument, and the associated value as second
173 argument. Each binding is presented exactly once to f .
174 The order in which the bindings are passed to f is unspecified. How‐
176 ever, if the table contains several bindings for the same key, they are
177 passed to f in reverse order of introduction, that is, the most recent
178 binding is passed first.
179 If the hash table was created in non-randomized mode, the order in
181 which the bindings are enumerated is reproducible between successive
182 runs of the program, and even between minor versions of OCaml. For
183 randomized hash tables, the order of enumeration is entirely random.
184 The behavior is not specified if the hash table is modified by f during
186 the iteration.
187 val filter_map_inplace : f:(key:'a -> data:'b -> 'b option) -> ('a, 'b)
191 t -> unit
192 Hashtbl.filter_map_inplace ~f tbl applies f to all bindings in table
195 tbl and update each binding depending on the result of f . If f re‐
196 turns None , the binding is discarded. If it returns Some new_val ,
197 the binding is update to associate the key to new_val .
198 Other comments for MoreLabels.Hashtbl.iter apply as well.
200 Since 4.03.0
203 val fold : f:(key:'a -> data:'b -> 'c -> 'c) -> ('a, 'b) t -> init:'c
207 -> 'c
208 Hashtbl.fold ~f tbl ~init computes (f kN dN ... (f k1 d1 init)...) ,
211 where k1 ... kN are the keys of all bindings in tbl , and d1 ... dN are
212 the associated values. Each binding is presented exactly once to f .
213 The order in which the bindings are passed to f is unspecified. How‐
215 ever, if the table contains several bindings for the same key, they are
216 passed to f in reverse order of introduction, that is, the most recent
217 binding is passed first.
218 If the hash table was created in non-randomized mode, the order in
220 which the bindings are enumerated is reproducible between successive
221 runs of the program, and even between minor versions of OCaml. For
222 randomized hash tables, the order of enumeration is entirely random.
223 The behavior is not specified if the hash table is modified by f during
225 the iteration.
226 val length : ('a, 'b) t -> int
230 Hashtbl.length tbl returns the number of bindings in tbl . It takes
233 constant time. Multiple bindings are counted once each, so
234 Hashtbl.length gives the number of times Hashtbl.iter calls its first
235 argument.
236 val randomize : unit -> unit
240 After a call to Hashtbl.randomize() , hash tables are created in ran‐
242 domized mode by default: MoreLabels.Hashtbl.create returns randomized
243 hash tables, unless the ~random:false optional parameter is given. The
244 same effect can be achieved by setting the R parameter in the OCAMLRUN‐
245 PARAM environment variable.
246 It is recommended that applications or Web frameworks that need to pro‐
248 tect themselves against the denial-of-service attack described in More‐
249 Labels.Hashtbl.create call Hashtbl.randomize() at initialization time.
250 Note that once Hashtbl.randomize() was called, there is no way to re‐
252 vert to the non-randomized default behavior of MoreLabels.Hashtbl.cre‐
253 ate . This is intentional. Non-randomized hash tables can still be
254 created using Hashtbl.create ~random:false .
255 Since 4.00.0
258 val is_randomized : unit -> bool
262 Return true if the tables are currently created in randomized mode by
264 default, false otherwise.
265 Since 4.03.0
268 val rebuild : ?random:bool -> ('a, 'b) t -> ('a, 'b) t
272 Return a copy of the given hashtable. Unlike MoreLabels.Hashtbl.copy ,
274 MoreLabels.Hashtbl.rebuild h re-hashes all the (key, value) entries of
275 the original table h . The returned hash table is randomized if h was
276 randomized, or the optional random parameter is true, or if the default
277 is to create randomized hash tables; see MoreLabels.Hashtbl.create for
278 more information.
279 MoreLabels.Hashtbl.rebuild can safely be used to import a hash table
282 built by an old version of the MoreLabels.Hashtbl module, then mar‐
283 shaled to persistent storage. After unmarshaling, apply MoreLa‐
284 bels.Hashtbl.rebuild to produce a hash table for the current version of
285 the MoreLabels.Hashtbl module.
286 Since 4.12.0
289 type statistics = Hashtbl.statistics = {
292 num_bindings : int ; (* Number of bindings present in the table.
293 Same value as returned by MoreLabels.Hashtbl.length .
294 *)
295 num_buckets : int ; (* Number of buckets in the table.
296 *)
297 max_bucket_length : int ; (* Maximal number of bindings per bucket.
298 *)
299 bucket_histogram : int array ; (* Histogram of bucket sizes. This
300 array histo has length max_bucket_length + 1 . The value of histo.(i)
301 is the number of buckets whose size is i .
302 *)
303 }
304 Since 4.00.0
307 val stats : ('a, 'b) t -> statistics
311 Hashtbl.stats tbl returns statistics about the table tbl : number of
314 buckets, size of the biggest bucket, distribution of buckets by size.
315 Since 4.00.0
318 Hash tables and Sequences
323 val to_seq : ('a, 'b) t -> ('a * 'b) Seq.t
324 Iterate on the whole table. The order in which the bindings appear in
326 the sequence is unspecified. However, if the table contains several
327 bindings for the same key, they appear in reversed order of introduc‐
328 tion, that is, the most recent binding appears first.
329 The behavior is not specified if the hash table is modified during the
331 iteration.
332 Since 4.07
335 val to_seq_keys : ('a, 'b) t -> 'a Seq.t
339 Same as Seq.map fst (to_seq m)
341 Since 4.07
345 val to_seq_values : ('a, 'b) t -> 'b Seq.t
349 Same as Seq.map snd (to_seq m)
351 Since 4.07
355 val add_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
359 Add the given bindings to the table, using MoreLabels.Hashtbl.add
361 Since 4.07
365 val replace_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
369 Add the given bindings to the table, using MoreLabels.Hashtbl.replace
371 Since 4.07
375 val of_seq : ('a * 'b) Seq.t -> ('a, 'b) t
379 Build a table from the given bindings. The bindings are added in the
381 same order they appear in the sequence, using MoreLabels.Hashtbl.re‐
382 place_seq , which means that if two pairs have the same key, only the
383 latest one will appear in the table.
384 Since 4.07
387 Functorial interface
392 The functorial interface allows the use of specific comparison and hash
393 functions, either for performance/security concerns, or because keys
394 are not hashable/comparable with the polymorphic builtins.
395 For instance, one might want to specialize a table for integer keys:
397 module IntHash =
398 struct
399 type t = int
400 let equal i j = i=j
401 let hash i = i land max_int
402 end
403 module IntHashtbl = Hashtbl.Make(IntHash)
405 let h = IntHashtbl.create 17 in
407 IntHashtbl.add h 12 "hello"
408 This creates a new module IntHashtbl , with a new type 'a
411 IntHashtbl.t of tables from int to 'a . In this example, h con‐
412 tains string values so its type is string IntHashtbl.t .
413 Note that the new type 'a IntHashtbl.t is not compatible with the type
415 ('a,'b) Hashtbl.t of the generic interface. For example, Hashtbl.length
416 h would not type-check, you must use IntHashtbl.length .
417 module type HashedType = sig end
419 The input signature of the functor MoreLabels.Hashtbl.Make .
422 module type S = sig end
425 The output signature of the functor MoreLabels.Hashtbl.Make .
428 module Make : functor (H : HashedType) -> sig end
431 Functor building an implementation of the hashtable structure. The
434 functor Hashtbl.Make returns a structure containing a type key of keys
435 and a type 'a t of hash tables associating data of type 'a to keys of
436 type key . The operations perform similarly to those of the generic
437 interface, but use the hashing and equality functions specified in the
438 functor argument H instead of generic equality and hashing. Since the
439 hash function is not seeded, the create operation of the result struc‐
440 ture always returns non-randomized hash tables.
441 module type SeededHashedType = sig end
444 The input signature of the functor MoreLabels.Hashtbl.MakeSeeded .
447 Since 4.00.0
450 module type SeededS = sig end
453 The output signature of the functor MoreLabels.Hashtbl.MakeSeeded .
456 Since 4.00.0
459 module MakeSeeded : functor (H : SeededHashedType) -> sig end
462 Functor building an implementation of the hashtable structure. The
465 functor Hashtbl.MakeSeeded returns a structure containing a type key of
466 keys and a type 'a t of hash tables associating data of type 'a to keys
467 of type key . The operations perform similarly to those of the generic
468 interface, but use the seeded hashing and equality functions specified
469 in the functor argument H instead of generic equality and hashing. The
470 create operation of the result structure supports the ~ random optional
471 parameter and returns randomized hash tables if ~random:true is passed
472 or if randomization is globally on (see MoreLabels.Hashtbl.randomize ).
473 Since 4.00.0
476 The polymorphic hash functions
481 val hash : 'a -> int
482 Hashtbl.hash x associates a nonnegative integer to any value of any
485 type. It is guaranteed that if x = y or Stdlib.compare x y = 0 , then
486 hash x = hash y . Moreover, hash always terminates, even on cyclic
487 structures.
488 val seeded_hash : int -> 'a -> int
492 A variant of MoreLabels.Hashtbl.hash that is further parameterized by
494 an integer seed.
495 Since 4.00.0
498 val hash_param : int -> int -> 'a -> int
502 Hashtbl.hash_param meaningful total x computes a hash value for x ,
505 with the same properties as for hash . The two extra integer parameters
506 meaningful and total give more precise control over hashing. Hashing
507 performs a breadth-first, left-to-right traversal of the structure x ,
508 stopping after meaningful meaningful nodes were encountered, or total
509 nodes (meaningful or not) were encountered. If total as specified by
510 the user exceeds a certain value, currently 256, then it is capped to
511 that value. Meaningful nodes are: integers; floating-point numbers;
512 strings; characters; booleans; and constant constructors. Larger values
513 of meaningful and total means that more nodes are taken into account to
514 compute the final hash value, and therefore collisions are less likely
515 to happen. However, hashing takes longer. The parameters meaningful
516 and total govern the tradeoff between accuracy and speed. As default
517 choices, MoreLabels.Hashtbl.hash and MoreLabels.Hashtbl.seeded_hash
518 take meaningful = 10 and total = 100 .
519 val seeded_hash_param : int -> int -> int -> 'a -> int
523 A variant of MoreLabels.Hashtbl.hash_param that is further parameter‐
525 ized by an integer seed. Usage: Hashtbl.seeded_hash_param meaningful
526 total seed x .
527 Since 4.00.0
530OCamldoc 2023-01-23 MoreLabels.Hashtbl(3)