1MoreLabels.Hashtbl(3)            OCaml library           MoreLabels.Hashtbl(3)
2
3
4

NAME

6       MoreLabels.Hashtbl - no description
7

Module

9       Module   MoreLabels.Hashtbl
10

Documentation

12       Module Hashtbl
13        : sig end
14
15
16
17
18
19
20
21
22
23       Hash tables and hash functions.
24
25       Hash tables are hashed association tables, with in-place modification.
26
27   Generic interface
28       type ('a, 'b) t = ('a, 'b) Hashtbl.t
29
30
31       The type of hash tables from type 'a to type 'b .
32
33
34
35       val create : ?random:bool -> int -> ('a, 'b) t
36
37
38       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
43       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
47       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
56       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
67       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
72
73       Before4.00.0 the ~ random parameter was not present and all hash tables
74       were created in non-randomized mode.
75
76
77
78
79       val clear : ('a, 'b) t -> unit
80
81       Empty a hash table. Use reset instead of clear to shrink  the  size  of
82       the bucket table to its initial size.
83
84
85
86       val reset : ('a, 'b) t -> unit
87
88       Empty  a hash table and shrink the size of the bucket table to its ini‐
89       tial size.
90
91
92       Since 4.00.0
93
94
95
96       val copy : ('a, 'b) t -> ('a, 'b) t
97
98       Return a copy of the given hashtable.
99
100
101
102       val add : ('a, 'b) t -> key:'a -> data:'b -> unit
103
104
105       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
111
112
113       val find : ('a, 'b) t -> 'a -> 'b
114
115
116       Hashtbl.find tbl x returns the current binding of x in tbl , or  raises
117       Not_found if no such binding exists.
118
119
120
121       val find_opt : ('a, 'b) t -> 'a -> 'b option
122
123
124       Hashtbl.find_opt  tbl  x  returns  the current binding of x in tbl , or
125       None if no such binding exists.
126
127
128       Since 4.05
129
130
131
132       val find_all : ('a, 'b) t -> 'a -> 'b list
133
134
135       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
139
140
141       val mem : ('a, 'b) t -> 'a -> bool
142
143
144       Hashtbl.mem tbl x checks if x is bound in tbl .
145
146
147
148       val remove : ('a, 'b) t -> 'a -> unit
149
150
151       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
155
156
157       val replace : ('a, 'b) t -> key:'a -> data:'b -> unit
158
159
160       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
166
167
168       val iter : f:(key:'a -> data:'b -> unit) -> ('a, 'b) t -> unit
169
170
171       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
175       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
180       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
185       The behavior is not specified if the hash table is modified by f during
186       the iteration.
187
188
189
190       val filter_map_inplace : f:(key:'a -> data:'b -> 'b option) -> ('a, 'b)
191       t -> unit
192
193
194       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
199       Other comments for MoreLabels.Hashtbl.iter apply as well.
200
201
202       Since 4.03.0
203
204
205
206       val  fold  : f:(key:'a -> data:'b -> 'c -> 'c) -> ('a, 'b) t -> init:'c
207       -> 'c
208
209
210       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
214       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
219       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
224       The behavior is not specified if the hash table is modified by f during
225       the iteration.
226
227
228
229       val length : ('a, 'b) t -> int
230
231
232       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
237
238
239       val randomize : unit -> unit
240
241       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
247       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
251       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
256
257       Since 4.00.0
258
259
260
261       val is_randomized : unit -> bool
262
263       Return  true  if the tables are currently created in randomized mode by
264       default, false otherwise.
265
266
267       Since 4.03.0
268
269
270
271       val rebuild : ?random:bool -> ('a, 'b) t -> ('a, 'b) t
272
273       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
280
281       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
287
288       Since 4.12.0
289
290
291       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
305
306       Since 4.00.0
307
308
309
310       val stats : ('a, 'b) t -> statistics
311
312
313       Hashtbl.stats tbl returns statistics about the table tbl  :  number  of
314       buckets, size of the biggest bucket, distribution of buckets by size.
315
316
317       Since 4.00.0
318
319
320
321
322   Hash tables and Sequences
323       val to_seq : ('a, 'b) t -> ('a * 'b) Seq.t
324
325       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
330       The behavior is not specified if the hash table is modified during  the
331       iteration.
332
333
334       Since 4.07
335
336
337
338       val to_seq_keys : ('a, 'b) t -> 'a Seq.t
339
340       Same as Seq.map fst (to_seq m)
341
342
343
344       Since 4.07
345
346
347
348       val to_seq_values : ('a, 'b) t -> 'b Seq.t
349
350       Same as Seq.map snd (to_seq m)
351
352
353
354       Since 4.07
355
356
357
358       val add_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
359
360       Add the given bindings to the table, using MoreLabels.Hashtbl.add
361
362
363
364       Since 4.07
365
366
367
368       val replace_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
369
370       Add the given bindings to the table, using MoreLabels.Hashtbl.replace
371
372
373
374       Since 4.07
375
376
377
378       val of_seq : ('a * 'b) Seq.t -> ('a, 'b) t
379
380       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
385
386       Since 4.07
387
388
389
390
391   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
396       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
404               module IntHashtbl = Hashtbl.Make(IntHash)
405
406               let h = IntHashtbl.create 17 in
407               IntHashtbl.add h 12 "hello"
408
409
410       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
414       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
418       module type HashedType = sig end
419
420
421       The input signature of the functor MoreLabels.Hashtbl.Make .
422
423
424       module type S = sig end
425
426
427       The output signature of the functor MoreLabels.Hashtbl.Make .
428
429
430       module Make : functor (H : HashedType) -> sig end
431
432
433       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
442
443       module type SeededHashedType = sig end
444
445
446       The input signature of the functor MoreLabels.Hashtbl.MakeSeeded .
447
448
449       Since 4.00.0
450
451
452       module type SeededS = sig end
453
454
455       The output signature of the functor MoreLabels.Hashtbl.MakeSeeded .
456
457
458       Since 4.00.0
459
460
461       module MakeSeeded : functor (H : SeededHashedType) -> sig end
462
463
464       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
474
475       Since 4.00.0
476
477
478
479
480   The polymorphic hash functions
481       val hash : 'a -> int
482
483
484       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
489
490
491       val seeded_hash : int -> 'a -> int
492
493       A  variant  of MoreLabels.Hashtbl.hash that is further parameterized by
494       an integer seed.
495
496
497       Since 4.00.0
498
499
500
501       val hash_param : int -> int -> 'a -> int
502
503
504       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
520
521
522       val seeded_hash_param : int -> int -> int -> 'a -> int
523
524       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
528
529       Since 4.00.0
530
531
532
533
534
535OCamldoc                          2023-01-23             MoreLabels.Hashtbl(3)
Impressum