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 Unsynchronized accesses
24 Unsynchronized accesses to a hash table may lead to an invalid hash ta‐
26 ble state. Thus, concurrent accesses to a hash tables must be synchro‐
27 nized (for instance with a Mutex.t ).
28 Generic interface
30 type ('a, 'b) t
31 The type of hash tables from type 'a to type 'b .
34 val create : ?random:bool -> int -> ('a, 'b) t
38 Hashtbl.create n creates a new, empty hash table, with initial size n .
41 For best results, n should be on the order of the expected number of
42 elements that will be in the table. The table grows as needed, so n is
43 just an initial guess.
44 The optional ~random parameter (a boolean) controls whether the inter‐
46 nal organization of the hash table is randomized at each execution of
47 Hashtbl.create or deterministic over all executions.
48 A hash table that is created with ~random set to false uses a fixed
50 hash function ( Hashtbl.hash ) to distribute keys among buckets. As a
51 consequence, collisions between keys happen deterministically. In
52 Web-facing applications or other security-sensitive applications, the
53 deterministic collision patterns can be exploited by a malicious user
54 to create a denial-of-service attack: the attacker sends input crafted
55 to create many collisions in the table, slowing the application down.
56 A hash table that is created with ~random set to true uses the seeded
58 hash function Hashtbl.seeded_hash with a seed that is randomly chosen
59 at hash table creation time. In effect, the hash function used is ran‐
60 domly selected among 2^{30} different hash functions. All these hash
61 functions have different collision patterns, rendering ineffective the
62 denial-of-service attack described above. However, because of random‐
63 ization, enumerating all elements of the hash table using Hashtbl.fold
64 or Hashtbl.iter is no longer deterministic: elements are enumerated in
65 different orders at different runs of the program.
66 If no ~random parameter is given, hash tables are created in non-random
68 mode by default. This default can be changed either programmatically
69 by calling Hashtbl.randomize or by setting the R flag in the OCAMLRUN‐
70 PARAM 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 -> 'a -> '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 Hashtbl.remove tbl key , the previous binding for key
108 , if any, is restored. (Same behavior as with association lists.)
109 val find : ('a, 'b) t -> 'a -> 'b
113 Hashtbl.find tbl x returns the current binding of x in tbl , or raises
116 Not_found if no such binding exists.
117 val find_opt : ('a, 'b) t -> 'a -> 'b option
121 Hashtbl.find_opt tbl x returns the current binding of x in tbl , or
124 None if no such binding exists.
125 Since 4.05
128 val find_all : ('a, 'b) t -> 'a -> 'b list
132 Hashtbl.find_all tbl x returns the list of all data associated with x
135 in tbl . The current binding is returned first, then the previous
136 bindings, in reverse order of introduction in the table.
137 val mem : ('a, 'b) t -> 'a -> bool
141 Hashtbl.mem tbl x checks if x is bound in tbl .
144 val remove : ('a, 'b) t -> 'a -> unit
148 Hashtbl.remove tbl x removes the current binding of x in tbl , restor‐
151 ing the previous binding if it exists. It does nothing if x is not
152 bound in tbl .
153 val replace : ('a, 'b) t -> 'a -> 'b -> unit
157 Hashtbl.replace tbl key data replaces the current binding of key in tbl
160 by a binding of key to data . If key is unbound in tbl , a binding of
161 key to data is added to tbl . This is functionally equivalent to
162 Hashtbl.remove tbl key followed by Hashtbl.add tbl key data .
163 val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
167 Hashtbl.iter f tbl applies f to all bindings in table tbl . f receives
170 the key as first argument, and the associated value as second argument.
171 Each binding is presented exactly once to f .
172 The order in which the bindings are passed to f is unspecified. How‐
174 ever, if the table contains several bindings for the same key, they are
175 passed to f in reverse order of introduction, that is, the most recent
176 binding is passed first.
177 If the hash table was created in non-randomized mode, the order in
179 which the bindings are enumerated is reproducible between successive
180 runs of the program, and even between minor versions of OCaml. For
181 randomized hash tables, the order of enumeration is entirely random.
182 The behavior is not specified if the hash table is modified by f during
184 the iteration.
185 val filter_map_inplace : ('a -> 'b -> 'b option) -> ('a, 'b) t -> unit
189 Hashtbl.filter_map_inplace f tbl applies f to all bindings in table tbl
192 and update each binding depending on the result of f . If f returns
193 None , the binding is discarded. If it returns Some new_val , the
194 binding is update to associate the key to new_val .
195 Other comments for Hashtbl.iter apply as well.
197 Since 4.03.0
200 val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
204 Hashtbl.fold f tbl init computes (f kN dN ... (f k1 d1 init)...) ,
207 where k1 ... kN are the keys of all bindings in tbl , and d1 ... dN are
208 the associated values. Each binding is presented exactly once to f .
209 The order in which the bindings are passed to f is unspecified. How‐
211 ever, if the table contains several bindings for the same key, they are
212 passed to f in reverse order of introduction, that is, the most recent
213 binding is passed first.
214 If the hash table was created in non-randomized mode, the order in
216 which the bindings are enumerated is reproducible between successive
217 runs of the program, and even between minor versions of OCaml. For
218 randomized hash tables, the order of enumeration is entirely random.
219 The behavior is not specified if the hash table is modified by f during
221 the iteration.
222 val length : ('a, 'b) t -> int
226 Hashtbl.length tbl returns the number of bindings in tbl . It takes
229 constant time. Multiple bindings are counted once each, so
230 Hashtbl.length gives the number of times Hashtbl.iter calls its first
231 argument.
232 val randomize : unit -> unit
236 After a call to Hashtbl.randomize() , hash tables are created in ran‐
238 domized mode by default: Hashtbl.create returns randomized hash tables,
239 unless the ~random:false optional parameter is given. The same effect
240 can be achieved by setting the R parameter in the OCAMLRUNPARAM envi‐
241 ronment variable.
242 It is recommended that applications or Web frameworks that need to pro‐
244 tect themselves against the denial-of-service attack described in
245 Hashtbl.create call Hashtbl.randomize() at initialization time before
246 any domains are created.
247 Note that once Hashtbl.randomize() was called, there is no way to re‐
249 vert to the non-randomized default behavior of Hashtbl.create . This
250 is intentional. Non-randomized hash tables can still be created using
251 Hashtbl.create ~random:false .
252 Since 4.00.0
255 val is_randomized : unit -> bool
259 Return true if the tables are currently created in randomized mode by
261 default, false otherwise.
262 Since 4.03.0
265 val rebuild : ?random:bool -> ('a, 'b) t -> ('a, 'b) t
269 Return a copy of the given hashtable. Unlike Hashtbl.copy ,
271 Hashtbl.rebuild h re-hashes all the (key, value) entries of the origi‐
272 nal table h . The returned hash table is randomized if h was random‐
273 ized, or the optional random parameter is true, or if the default is to
274 create randomized hash tables; see Hashtbl.create for more information.
275 Hashtbl.rebuild can safely be used to import a hash table built by an
278 old version of the Hashtbl module, then marshaled to persistent stor‐
279 age. After unmarshaling, apply Hashtbl.rebuild to produce a hash table
280 for the current version of the Hashtbl module.
281 Since 4.12.0
284 type statistics = {
287 num_bindings : int ; (* Number of bindings present in the table.
288 Same value as returned by Hashtbl.length .
289 *)
290 num_buckets : int ; (* Number of buckets in the table.
291 *)
292 max_bucket_length : int ; (* Maximal number of bindings per bucket.
293 *)
294 bucket_histogram : int array ; (* Histogram of bucket sizes. This
295 array histo has length max_bucket_length + 1 . The value of histo.(i)
296 is the number of buckets whose size is i .
297 *)
298 }
299 Since 4.00.0
302 val stats : ('a, 'b) t -> statistics
306 Hashtbl.stats tbl returns statistics about the table tbl : number of
309 buckets, size of the biggest bucket, distribution of buckets by size.
310 Since 4.00.0
313 Hash tables and Sequences
318 val to_seq : ('a, 'b) t -> ('a * 'b) Seq.t
319 Iterate on the whole table. The order in which the bindings appear in
321 the sequence is unspecified. However, if the table contains several
322 bindings for the same key, they appear in reversed order of introduc‐
323 tion, that is, the most recent binding appears first.
324 The behavior is not specified if the hash table is modified during the
326 iteration.
327 Since 4.07
330 val to_seq_keys : ('a, 'b) t -> 'a Seq.t
334 Same as Seq.map fst (to_seq m)
336 Since 4.07
340 val to_seq_values : ('a, 'b) t -> 'b Seq.t
344 Same as Seq.map snd (to_seq m)
346 Since 4.07
350 val add_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
354 Add the given bindings to the table, using Hashtbl.add
356 Since 4.07
360 val replace_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
364 Add the given bindings to the table, using Hashtbl.replace
366 Since 4.07
370 val of_seq : ('a * 'b) Seq.t -> ('a, 'b) t
374 Build a table from the given bindings. The bindings are added in the
376 same order they appear in the sequence, using Hashtbl.replace_seq ,
377 which means that if two pairs have the same key, only the latest one
378 will appear in the table.
379 Since 4.07
382 Functorial interface
387 The functorial interface allows the use of specific comparison and hash
388 functions, either for performance/security concerns, or because keys
389 are not hashable/comparable with the polymorphic builtins.
390 For instance, one might want to specialize a table for integer keys:
392 module IntHash =
393 struct
394 type t = int
395 let equal i j = i=j
396 let hash i = i land max_int
397 end
398 module IntHashtbl = Hashtbl.Make(IntHash)
400 let h = IntHashtbl.create 17 in
402 IntHashtbl.add h 12 "hello"
403 This creates a new module IntHashtbl , with a new type 'a
406 IntHashtbl.t of tables from int to 'a . In this example, h contains
407 string values so its type is string IntHashtbl.t .
408 Note that the new type 'a IntHashtbl.t is not compatible with the type
410 ('a,'b) Hashtbl.t of the generic interface. For example, Hashtbl.length
411 h would not type-check, you must use IntHashtbl.length .
412 module type HashedType = sig end
414 The input signature of the functor Hashtbl.Make .
417 module type S = sig end
420 The output signature of the functor Hashtbl.Make .
423 module Make : functor (H : HashedType) -> sig end
426 Functor building an implementation of the hashtable structure. The
429 functor Hashtbl.Make returns a structure containing a type key of keys
430 and a type 'a t of hash tables associating data of type 'a to keys of
431 type key . The operations perform similarly to those of the generic
432 interface, but use the hashing and equality functions specified in the
433 functor argument H instead of generic equality and hashing. Since the
434 hash function is not seeded, the create operation of the result struc‐
435 ture always returns non-randomized hash tables.
436 module type SeededHashedType = sig end
439 The input signature of the functor Hashtbl.MakeSeeded .
442 Since 4.00.0
445 module type SeededS = sig end
448 The output signature of the functor Hashtbl.MakeSeeded .
451 Since 4.00.0
454 module MakeSeeded : functor (H : SeededHashedType) -> sig end
457 Functor building an implementation of the hashtable structure. The
460 functor Hashtbl.MakeSeeded returns a structure containing a type key of
461 keys and a type 'a t of hash tables associating data of type 'a to keys
462 of type key . The operations perform similarly to those of the generic
463 interface, but use the seeded hashing and equality functions specified
464 in the functor argument H instead of generic equality and hashing. The
465 create operation of the result structure supports the ~random optional
466 parameter and returns randomized hash tables if ~random:true is passed
467 or if randomization is globally on (see Hashtbl.randomize ).
468 Since 4.00.0
471 The polymorphic hash functions
476 val hash : 'a -> int
477 Hashtbl.hash x associates a nonnegative integer to any value of any
480 type. It is guaranteed that if x = y or Stdlib.compare x y = 0 , then
481 hash x = hash y . Moreover, hash always terminates, even on cyclic
482 structures.
483 val seeded_hash : int -> 'a -> int
487 A variant of Hashtbl.hash that is further parameterized by an integer
489 seed.
490 Since 4.00.0
493 val hash_param : int -> int -> 'a -> int
497 Hashtbl.hash_param meaningful total x computes a hash value for x ,
500 with the same properties as for hash . The two extra integer parameters
501 meaningful and total give more precise control over hashing. Hashing
502 performs a breadth-first, left-to-right traversal of the structure x ,
503 stopping after meaningful meaningful nodes were encountered, or total
504 nodes (meaningful or not) were encountered. If total as specified by
505 the user exceeds a certain value, currently 256, then it is capped to
506 that value. Meaningful nodes are: integers; floating-point numbers;
507 strings; characters; booleans; and constant constructors. Larger values
508 of meaningful and total means that more nodes are taken into account to
509 compute the final hash value, and therefore collisions are less likely
510 to happen. However, hashing takes longer. The parameters meaningful
511 and total govern the tradeoff between accuracy and speed. As default
512 choices, Hashtbl.hash and Hashtbl.seeded_hash take meaningful = 10 and
513 total = 100 .
514 val seeded_hash_param : int -> int -> int -> 'a -> int
518 A variant of Hashtbl.hash_param that is further parameterized by an in‐
520 teger seed. Usage: Hashtbl.seeded_hash_param meaningful total seed x .
521 Since 4.00.0
524OCamldoc 2023-07-20 Stdlib.Hashtbl(3)