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 Unsynchronized accesses
28 Unsynchronized accesses to a hash table may lead to an invalid hash ta‐
30 ble state. Thus, concurrent accesses to a hash tables must be synchro‐
31 nized (for instance with a Mutex.t ).
32 Generic interface
34 type ('a, 'b) t = ('a, 'b) Hashtbl.t
35 The type of hash tables from type 'a to type 'b .
38 val create : ?random:bool -> int -> ('a, 'b) t
42 Hashtbl.create n creates a new, empty hash table, with initial size n .
45 For best results, n should be on the order of the expected number of
46 elements that will be in the table. The table grows as needed, so n is
47 just an initial guess.
48 The optional ~random parameter (a boolean) controls whether the inter‐
50 nal organization of the hash table is randomized at each execution of
51 Hashtbl.create or deterministic over all executions.
52 A hash table that is created with ~random set to false uses a fixed
54 hash function ( MoreLabels.Hashtbl.hash ) to distribute keys among
55 buckets. As a consequence, collisions between keys happen determinis‐
56 tically. In Web-facing applications or other security-sensitive appli‐
57 cations, the deterministic collision patterns can be exploited by a ma‐
58 licious user to create a denial-of-service attack: the attacker sends
59 input crafted to create many collisions in the table, slowing the ap‐
60 plication down.
61 A hash table that is created with ~random set to true uses the seeded
63 hash function MoreLabels.Hashtbl.seeded_hash with a seed that is ran‐
64 domly chosen at hash table creation time. In effect, the hash function
65 used is randomly selected among 2^{30} different hash functions. All
66 these hash functions have different collision patterns, rendering inef‐
67 fective the denial-of-service attack described above. However, because
68 of randomization, enumerating all elements of the hash table using
69 MoreLabels.Hashtbl.fold or MoreLabels.Hashtbl.iter is no longer deter‐
70 ministic: elements are enumerated in different orders at different runs
71 of the program.
72 If no ~random parameter is given, hash tables are created in non-random
74 mode by default. This default can be changed either programmatically
75 by calling MoreLabels.Hashtbl.randomize or by setting the R flag in the
76 OCAMLRUNPARAM environment variable.
77 Before4.00.0 the ~random parameter was not present and all hash tables
80 were created in non-randomized mode.
81 val clear : ('a, 'b) t -> unit
86 Empty a hash table. Use reset instead of clear to shrink the size of
88 the bucket table to its initial size.
89 val reset : ('a, 'b) t -> unit
93 Empty a hash table and shrink the size of the bucket table to its ini‐
95 tial size.
96 Since 4.00.0
99 val copy : ('a, 'b) t -> ('a, 'b) t
103 Return a copy of the given hashtable.
105 val add : ('a, 'b) t -> key:'a -> data:'b -> unit
109 Hashtbl.add tbl ~key ~data adds a binding of key to data in table tbl .
112 Previous bindings for key are not removed, but simply hidden. That is,
113 after performing MoreLabels.Hashtbl.remove tbl key , the previous bind‐
114 ing for key , if any, is restored. (Same behavior as with association
115 lists.)
116 val find : ('a, 'b) t -> 'a -> 'b
120 Hashtbl.find tbl x returns the current binding of x in tbl , or raises
123 Not_found if no such binding exists.
124 val find_opt : ('a, 'b) t -> 'a -> 'b option
128 Hashtbl.find_opt tbl x returns the current binding of x in tbl , or
131 None if no such binding exists.
132 Since 4.05
135 val find_all : ('a, 'b) t -> 'a -> 'b list
139 Hashtbl.find_all tbl x returns the list of all data associated with x
142 in tbl . The current binding is returned first, then the previous
143 bindings, in reverse order of introduction in the table.
144 val mem : ('a, 'b) t -> 'a -> bool
148 Hashtbl.mem tbl x checks if x is bound in tbl .
151 val remove : ('a, 'b) t -> 'a -> unit
155 Hashtbl.remove tbl x removes the current binding of x in tbl , restor‐
158 ing the previous binding if it exists. It does nothing if x is not
159 bound in tbl .
160 val replace : ('a, 'b) t -> key:'a -> data:'b -> unit
164 Hashtbl.replace tbl ~key ~data replaces the current binding of key in
167 tbl by a binding of key to data . If key is unbound in tbl , a binding
168 of key to data is added to tbl . This is functionally equivalent to
169 MoreLabels.Hashtbl.remove tbl key followed by MoreLabels.Hashtbl.add
170 tbl key data .
171 val iter : f:(key:'a -> data:'b -> unit) -> ('a, 'b) t -> unit
175 Hashtbl.iter ~f tbl applies f to all bindings in table tbl . f re‐
178 ceives the key as first argument, and the associated value as second
179 argument. Each binding is presented exactly once to f .
180 The order in which the bindings are passed to f is unspecified. How‐
182 ever, if the table contains several bindings for the same key, they are
183 passed to f in reverse order of introduction, that is, the most recent
184 binding is passed first.
185 If the hash table was created in non-randomized mode, the order in
187 which the bindings are enumerated is reproducible between successive
188 runs of the program, and even between minor versions of OCaml. For
189 randomized hash tables, the order of enumeration is entirely random.
190 The behavior is not specified if the hash table is modified by f during
192 the iteration.
193 val filter_map_inplace : f:(key:'a -> data:'b -> 'b option) -> ('a, 'b)
197 t -> unit
198 Hashtbl.filter_map_inplace ~f tbl applies f to all bindings in table
201 tbl and update each binding depending on the result of f . If f re‐
202 turns None , the binding is discarded. If it returns Some new_val ,
203 the binding is update to associate the key to new_val .
204 Other comments for MoreLabels.Hashtbl.iter apply as well.
206 Since 4.03.0
209 val fold : f:(key:'a -> data:'b -> 'c -> 'c) -> ('a, 'b) t -> init:'c
213 -> 'c
214 Hashtbl.fold ~f tbl ~init computes (f kN dN ... (f k1 d1 init)...) ,
217 where k1 ... kN are the keys of all bindings in tbl , and d1 ... dN are
218 the associated values. Each binding is presented exactly once to f .
219 The order in which the bindings are passed to f is unspecified. How‐
221 ever, if the table contains several bindings for the same key, they are
222 passed to f in reverse order of introduction, that is, the most recent
223 binding is passed first.
224 If the hash table was created in non-randomized mode, the order in
226 which the bindings are enumerated is reproducible between successive
227 runs of the program, and even between minor versions of OCaml. For
228 randomized hash tables, the order of enumeration is entirely random.
229 The behavior is not specified if the hash table is modified by f during
231 the iteration.
232 val length : ('a, 'b) t -> int
236 Hashtbl.length tbl returns the number of bindings in tbl . It takes
239 constant time. Multiple bindings are counted once each, so
240 Hashtbl.length gives the number of times Hashtbl.iter calls its first
241 argument.
242 val randomize : unit -> unit
246 After a call to Hashtbl.randomize() , hash tables are created in ran‐
248 domized mode by default: MoreLabels.Hashtbl.create returns randomized
249 hash tables, unless the ~random:false optional parameter is given. The
250 same effect can be achieved by setting the R parameter in the OCAMLRUN‐
251 PARAM environment variable.
252 It is recommended that applications or Web frameworks that need to pro‐
254 tect themselves against the denial-of-service attack described in More‐
255 Labels.Hashtbl.create call Hashtbl.randomize() at initialization time
256 before any domains are created.
257 Note that once Hashtbl.randomize() was called, there is no way to re‐
259 vert to the non-randomized default behavior of MoreLabels.Hashtbl.cre‐
260 ate . This is intentional. Non-randomized hash tables can still be
261 created using Hashtbl.create ~random:false .
262 Since 4.00.0
265 val is_randomized : unit -> bool
269 Return true if the tables are currently created in randomized mode by
271 default, false otherwise.
272 Since 4.03.0
275 val rebuild : ?random:bool -> ('a, 'b) t -> ('a, 'b) t
279 Return a copy of the given hashtable. Unlike MoreLabels.Hashtbl.copy ,
281 MoreLabels.Hashtbl.rebuild h re-hashes all the (key, value) entries of
282 the original table h . The returned hash table is randomized if h was
283 randomized, or the optional random parameter is true, or if the default
284 is to create randomized hash tables; see MoreLabels.Hashtbl.create for
285 more information.
286 MoreLabels.Hashtbl.rebuild can safely be used to import a hash table
289 built by an old version of the MoreLabels.Hashtbl module, then mar‐
290 shaled to persistent storage. After unmarshaling, apply MoreLa‐
291 bels.Hashtbl.rebuild to produce a hash table for the current version of
292 the MoreLabels.Hashtbl module.
293 Since 4.12.0
296 type statistics = Hashtbl.statistics = {
299 num_bindings : int ; (* Number of bindings present in the table.
300 Same value as returned by MoreLabels.Hashtbl.length .
301 *)
302 num_buckets : int ; (* Number of buckets in the table.
303 *)
304 max_bucket_length : int ; (* Maximal number of bindings per bucket.
305 *)
306 bucket_histogram : int array ; (* Histogram of bucket sizes. This
307 array histo has length max_bucket_length + 1 . The value of histo.(i)
308 is the number of buckets whose size is i .
309 *)
310 }
311 Since 4.00.0
314 val stats : ('a, 'b) t -> statistics
318 Hashtbl.stats tbl returns statistics about the table tbl : number of
321 buckets, size of the biggest bucket, distribution of buckets by size.
322 Since 4.00.0
325 Hash tables and Sequences
330 val to_seq : ('a, 'b) t -> ('a * 'b) Seq.t
331 Iterate on the whole table. The order in which the bindings appear in
333 the sequence is unspecified. However, if the table contains several
334 bindings for the same key, they appear in reversed order of introduc‐
335 tion, that is, the most recent binding appears first.
336 The behavior is not specified if the hash table is modified during the
338 iteration.
339 Since 4.07
342 val to_seq_keys : ('a, 'b) t -> 'a Seq.t
346 Same as Seq.map fst (to_seq m)
348 Since 4.07
352 val to_seq_values : ('a, 'b) t -> 'b Seq.t
356 Same as Seq.map snd (to_seq m)
358 Since 4.07
362 val add_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
366 Add the given bindings to the table, using MoreLabels.Hashtbl.add
368 Since 4.07
372 val replace_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
376 Add the given bindings to the table, using MoreLabels.Hashtbl.replace
378 Since 4.07
382 val of_seq : ('a * 'b) Seq.t -> ('a, 'b) t
386 Build a table from the given bindings. The bindings are added in the
388 same order they appear in the sequence, using MoreLabels.Hashtbl.re‐
389 place_seq , which means that if two pairs have the same key, only the
390 latest one will appear in the table.
391 Since 4.07
394 Functorial interface
399 The functorial interface allows the use of specific comparison and hash
400 functions, either for performance/security concerns, or because keys
401 are not hashable/comparable with the polymorphic builtins.
402 For instance, one might want to specialize a table for integer keys:
404 module IntHash =
405 struct
406 type t = int
407 let equal i j = i=j
408 let hash i = i land max_int
409 end
410 module IntHashtbl = Hashtbl.Make(IntHash)
412 let h = IntHashtbl.create 17 in
414 IntHashtbl.add h 12 "hello"
415 This creates a new module IntHashtbl , with a new type 'a
418 IntHashtbl.t of tables from int to 'a . In this example, h con‐
419 tains string values so its type is string IntHashtbl.t .
420 Note that the new type 'a IntHashtbl.t is not compatible with the type
422 ('a,'b) Hashtbl.t of the generic interface. For example, Hashtbl.length
423 h would not type-check, you must use IntHashtbl.length .
424 module type HashedType = sig end
426 The input signature of the functor MoreLabels.Hashtbl.Make .
429 module type S = sig end
432 The output signature of the functor MoreLabels.Hashtbl.Make .
435 module Make : functor (H : HashedType) -> sig end
438 Functor building an implementation of the hashtable structure. The
441 functor Hashtbl.Make returns a structure containing a type key of keys
442 and a type 'a t of hash tables associating data of type 'a to keys of
443 type key . The operations perform similarly to those of the generic
444 interface, but use the hashing and equality functions specified in the
445 functor argument H instead of generic equality and hashing. Since the
446 hash function is not seeded, the create operation of the result struc‐
447 ture always returns non-randomized hash tables.
448 module type SeededHashedType = sig end
451 The input signature of the functor MoreLabels.Hashtbl.MakeSeeded .
454 Since 4.00.0
457 module type SeededS = sig end
460 The output signature of the functor MoreLabels.Hashtbl.MakeSeeded .
463 Since 4.00.0
466 module MakeSeeded : functor (H : SeededHashedType) -> sig end
469 Functor building an implementation of the hashtable structure. The
472 functor Hashtbl.MakeSeeded returns a structure containing a type key of
473 keys and a type 'a t of hash tables associating data of type 'a to keys
474 of type key . The operations perform similarly to those of the generic
475 interface, but use the seeded hashing and equality functions specified
476 in the functor argument H instead of generic equality and hashing. The
477 create operation of the result structure supports the ~random optional
478 parameter and returns randomized hash tables if ~random:true is passed
479 or if randomization is globally on (see MoreLabels.Hashtbl.randomize ).
480 Since 4.00.0
483 The polymorphic hash functions
488 val hash : 'a -> int
489 Hashtbl.hash x associates a nonnegative integer to any value of any
492 type. It is guaranteed that if x = y or Stdlib.compare x y = 0 , then
493 hash x = hash y . Moreover, hash always terminates, even on cyclic
494 structures.
495 val seeded_hash : int -> 'a -> int
499 A variant of MoreLabels.Hashtbl.hash that is further parameterized by
501 an integer seed.
502 Since 4.00.0
505 val hash_param : int -> int -> 'a -> int
509 Hashtbl.hash_param meaningful total x computes a hash value for x ,
512 with the same properties as for hash . The two extra integer parameters
513 meaningful and total give more precise control over hashing. Hashing
514 performs a breadth-first, left-to-right traversal of the structure x ,
515 stopping after meaningful meaningful nodes were encountered, or total
516 nodes (meaningful or not) were encountered. If total as specified by
517 the user exceeds a certain value, currently 256, then it is capped to
518 that value. Meaningful nodes are: integers; floating-point numbers;
519 strings; characters; booleans; and constant constructors. Larger values
520 of meaningful and total means that more nodes are taken into account to
521 compute the final hash value, and therefore collisions are less likely
522 to happen. However, hashing takes longer. The parameters meaningful
523 and total govern the tradeoff between accuracy and speed. As default
524 choices, MoreLabels.Hashtbl.hash and MoreLabels.Hashtbl.seeded_hash
525 take meaningful = 10 and total = 100 .
526 val seeded_hash_param : int -> int -> int -> 'a -> int
530 A variant of MoreLabels.Hashtbl.hash_param that is further parameter‐
532 ized by an integer seed. Usage: Hashtbl.seeded_hash_param meaningful
533 total seed x .
534 Since 4.00.0
537OCamldoc 2023-07-20 MoreLabels.Hashtbl(3)