1Hashtbl(3) OCaml library Hashtbl(3)
2
6 Hashtbl - Hash tables and hash functions.
7
9 Module Hashtbl
10
12 Module Hashtbl
13 : sig end
14 Hash tables and hash functions.
17 Hash tables are hashed association tables, with in-place modification.
19 === Generic interface ===
27 type ('a, 'b) t
30 The type of hash tables from type 'a to type 'b .
33 val create : ?random:bool -> int -> ('a, 'b) t
37 Hashtbl.create n creates a new, empty hash table, with initial size n .
40 For best results, n should be on the order of the expected number of
41 elements that will be in the table. The table grows as needed, so n is
42 just an initial guess.
43 The optional random parameter (a boolean) controls whether the internal
45 organization of the hash table is randomized at each execution of
46 Hashtbl.create or deterministic over all executions.
47 A hash table that is created with ~random:false uses a fixed hash func‐
49 tion ( Hashtbl.hash ) to distribute keys among buckets. As a conse‐
50 quence, collisions between keys happen deterministically. In Web-fac‐
51 ing applications or other security-sensitive applications, the deter‐
52 ministic collision patterns can be exploited by a malicious user to
53 create a denial-of-service attack: the attacker sends input crafted to
54 create many collisions in the table, slowing the application down.
55 A hash table that is created with ~random:true uses the seeded hash
57 function Hashtbl.seeded_hash with a seed that is randomly chosen at
58 hash table creation time. In effect, the hash function used is ran‐
59 domly selected among 2^{30} different hash functions. All these hash
60 functions have different collision patterns, rendering ineffective the
61 denial-of-service attack described above. However, because of random‐
62 ization, enumerating all elements of the hash table using Hashtbl.fold
63 or Hashtbl.iter is no longer deterministic: elements are enumerated in
64 different orders at different runs of the program.
65 If no ~random parameter is given, hash tables are created in non-random
67 mode by default. This default can be changed either programmatically
68 by calling Hashtbl.randomize or by setting the R flag in the OCAMLRUN‐
69 PARAM environment variable.
70 Before4.00.0 the random parameter was not present and all hash tables
73 were created in non-randomized mode.
74 val clear : ('a, 'b) t -> unit
79 Empty a hash table. Use reset instead of clear to shrink the size of
81 the bucket table to its initial size.
82 val reset : ('a, 'b) t -> unit
86 Empty a hash table and shrink the size of the bucket table to its ini‐
88 tial size.
89 Since 4.00.0
92 val copy : ('a, 'b) t -> ('a, 'b) t
96 Return a copy of the given hashtable.
98 val add : ('a, 'b) t -> 'a -> 'b -> unit
102 Hashtbl.add tbl x y adds a binding of x to y in table tbl . Previous
105 bindings for x are not removed, but simply hidden. That is, after per‐
106 forming Hashtbl.remove tbl x , the previous binding for x , if any, is
107 restored. (Same behavior as with association lists.)
108 val find : ('a, 'b) t -> 'a -> 'b
112 Hashtbl.find tbl x returns the current binding of x in tbl , or raises
115 Not_found if no such binding exists.
116 val find_opt : ('a, 'b) t -> 'a -> 'b option
120 Hashtbl.find_opt tbl x returns the current binding of x in tbl , or
123 None if no such binding exists.
124 Since 4.05
127 val find_all : ('a, 'b) t -> 'a -> 'b list
131 Hashtbl.find_all tbl x returns the list of all data associated with x
134 in tbl . The current binding is returned first, then the previous
135 bindings, in reverse order of introduction in the table.
136 val mem : ('a, 'b) t -> 'a -> bool
140 Hashtbl.mem tbl x checks if x is bound in tbl .
143 val remove : ('a, 'b) t -> 'a -> unit
147 Hashtbl.remove tbl x removes the current binding of x in tbl , restor‐
150 ing the previous binding if it exists. It does nothing if x is not
151 bound in tbl .
152 val replace : ('a, 'b) t -> 'a -> 'b -> unit
156 Hashtbl.replace tbl x y replaces the current binding of x in tbl by a
159 binding of x to y . If x is unbound in tbl , a binding of x to y is
160 added to tbl . This is functionally equivalent to Hashtbl.remove tbl x
161 followed by Hashtbl.add tbl x y .
162 val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
166 Hashtbl.iter f tbl applies f to all bindings in table tbl . f receives
169 the key as first argument, and the associated value as second argument.
170 Each binding is presented exactly once to f .
171 The order in which the bindings are passed to f is unspecified. How‐
173 ever, if the table contains several bindings for the same key, they are
174 passed to f in reverse order of introduction, that is, the most recent
175 binding is passed first.
176 If the hash table was created in non-randomized mode, the order in
178 which the bindings are enumerated is reproducible between successive
179 runs of the program, and even between minor versions of OCaml. For
180 randomized hash tables, the order of enumeration is entirely random.
181 The behavior is not defined if the hash table is modified by f during
183 the iteration.
184 val filter_map_inplace : ('a -> 'b -> 'b option) -> ('a, 'b) t -> unit
188 Hashtbl.filter_map_inplace f tbl applies f to all bindings in table tbl
191 and update each binding depending on the result of f . If f returns
192 None , the binding is discarded. If it returns Some new_val , the
193 binding is update to associate the key to new_val .
194 Other comments for Hashtbl.iter apply as well.
196 Since 4.03.0
199 val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
203 Hashtbl.fold f tbl init computes (f kN dN ... (f k1 d1 init)...) ,
206 where k1 ... kN are the keys of all bindings in tbl , and d1 ... dN are
207 the associated values. Each binding is presented exactly once to f .
208 The order in which the bindings are passed to f is unspecified. How‐
210 ever, if the table contains several bindings for the same key, they are
211 passed to f in reverse order of introduction, that is, the most recent
212 binding is passed first.
213 If the hash table was created in non-randomized mode, the order in
215 which the bindings are enumerated is reproducible between successive
216 runs of the program, and even between minor versions of OCaml. For
217 randomized hash tables, the order of enumeration is entirely random.
218 The behavior is not defined if the hash table is modified by f during
220 the iteration.
221 val length : ('a, 'b) t -> int
225 Hashtbl.length tbl returns the number of bindings in tbl . It takes
228 constant time. Multiple bindings are counted once each, so
229 Hashtbl.length gives the number of times Hashtbl.iter calls its first
230 argument.
231 val randomize : unit -> unit
235 After a call to Hashtbl.randomize() , hash tables are created in ran‐
237 domized mode by default: Hashtbl.create returns randomized hash tables,
238 unless the ~random:false optional parameter is given. The same effect
239 can be achieved by setting the R parameter in the OCAMLRUNPARAM envi‐
240 ronment variable.
241 It is recommended that applications or Web frameworks that need to pro‐
243 tect themselves against the denial-of-service attack described in
244 Hashtbl.create call Hashtbl.randomize() at initialization time.
245 Note that once Hashtbl.randomize() was called, there is no way to
247 revert to the non-randomized default behavior of Hashtbl.create . This
248 is intentional. Non-randomized hash tables can still be created using
249 Hashtbl.create ~random:false .
250 Since 4.00.0
253 val is_randomized : unit -> bool
257 return if the tables are currently created in randomized mode by
259 default
260 Since 4.03.0
263 type statistics = {
266 num_bindings : int ; (* Number of bindings present in the table.
267 Same value as returned by Hashtbl.length .
268 *)
269 num_buckets : int ; (* Number of buckets in the table.
270 *)
271 max_bucket_length : int ; (* Maximal number of bindings per bucket.
272 *)
273 bucket_histogram : int array ; (* Histogram of bucket sizes. This
274 array histo has length max_bucket_length + 1 . The value of histo.(i)
275 is the number of buckets whose size is i .
276 *)
277 }
278 Since 4.00.0
281 val stats : ('a, 'b) t -> statistics
285 Hashtbl.stats tbl returns statistics about the table tbl : number of
288 buckets, size of the biggest bucket, distribution of buckets by size.
289 Since 4.00.0
292 === Iterators ===
297 val to_seq : ('a, 'b) t -> ('a * 'b) Seq.t
300 Iterate on the whole table, in unspecified order.
302 The behavior is not defined if the hash table is modified during the
304 iteration.
305 Since 4.07
308 val to_seq_keys : ('a, 'b) t -> 'a Seq.t
312 Iterate on 'as, in ascending order
314 Since 4.07
317 val to_seq_values : ('a, 'b) t -> 'b Seq.t
321 Iterate on values, in ascending order of their corresponding 'a
323 Since 4.07
326 val add_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
330 Add the given bindings to the table, using Hashtbl.add
332 Since 4.07
336 val replace_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit
340 Add the given bindings to the table, using Hashtbl.replace
342 Since 4.07
346 val of_seq : ('a * 'b) Seq.t -> ('a, 'b) t
350 Build a table from the given bindings. The bindings are added in the
352 same order they appear in the sequence, using Hashtbl.replace_seq ,
353 which means that if two pairs have the same key, only the latest one
354 will appear in the table.
355 Since 4.07
358 === Functorial interface ===
363 === The functorial interface allows the use of specific comparison and
366 hash functions, either for performance/security concerns, or because
367 keys are not hashable/comparable with the polymorphic builtins. For
368 instance, one might want to specialize a table for integer keys: module
369 IntHash = struct type t = int let equal i j = i=j let hash i = i land
370 max_int end module IntHashtbl = Hashtbl.Make(IntHash) let h =
371 IntHashtbl.create 17 in IntHashtbl.add h 12 hello This creates a new
372 module IntHashtbl, with a new type 'a IntHashtbl.t of tables from int
373 to 'a. In this example, h contains string values so its type is string
374 IntHashtbl.t. Note that the new type 'a IntHashtbl.t is not compatible
375 with the type ('a,'b) Hashtbl.t of the generic interface. For example,
376 Hashtbl.length h would not type-check, you must use IntHashtbl.length.
377 ===
378 module type HashedType = sig end
381 The input signature of the functor Hashtbl.Make .
384 module type S = sig end
387 The output signature of the functor Hashtbl.Make .
390 module Make : functor (H : HashedType) -> sig end
393 Functor building an implementation of the hashtable structure. The
396 functor Hashtbl.Make returns a structure containing a type key of keys
397 and a type 'a t of hash tables associating data of type 'a to keys of
398 type key . The operations perform similarly to those of the generic
399 interface, but use the hashing and equality functions specified in the
400 functor argument H instead of generic equality and hashing. Since the
401 hash function is not seeded, the create operation of the result struc‐
402 ture always returns non-randomized hash tables.
403 module type SeededHashedType = sig end
406 The input signature of the functor Hashtbl.MakeSeeded .
409 Since 4.00.0
412 module type SeededS = sig end
415 The output signature of the functor Hashtbl.MakeSeeded .
418 Since 4.00.0
421 module MakeSeeded : functor (H : SeededHashedType) -> sig end
424 Functor building an implementation of the hashtable structure. The
427 functor Hashtbl.MakeSeeded returns a structure containing a type key of
428 keys and a type 'a t of hash tables associating data of type 'a to keys
429 of type key . The operations perform similarly to those of the generic
430 interface, but use the seeded hashing and equality functions specified
431 in the functor argument H instead of generic equality and hashing. The
432 create operation of the result structure supports the ~random optional
433 parameter and returns randomized hash tables if ~random:true is passed
434 or if randomization is globally on (see Hashtbl.randomize ).
435 Since 4.00.0
438 === The polymorphic hash functions ===
443 val hash : 'a -> int
446 Hashtbl.hash x associates a nonnegative integer to any value of any
449 type. It is guaranteed that if x = y or Pervasives.compare x y = 0 ,
450 then hash x = hash y . Moreover, hash always terminates, even on
451 cyclic structures.
452 val seeded_hash : int -> 'a -> int
456 A variant of Hashtbl.hash that is further parameterized by an integer
458 seed.
459 Since 4.00.0
462 val hash_param : int -> int -> 'a -> int
466 Hashtbl.hash_param meaningful total x computes a hash value for x ,
469 with the same properties as for hash . The two extra integer parameters
470 meaningful and total give more precise control over hashing. Hashing
471 performs a breadth-first, left-to-right traversal of the structure x ,
472 stopping after meaningful meaningful nodes were encountered, or total
473 nodes (meaningful or not) were encountered. If total as specified by
474 the user exceeds a certain value, currently 256, then it is capped to
475 that value. Meaningful nodes are: integers; floating-point numbers;
476 strings; characters; booleans; and constant constructors. Larger values
477 of meaningful and total means that more nodes are taken into account to
478 compute the final hash value, and therefore collisions are less likely
479 to happen. However, hashing takes longer. The parameters meaningful
480 and total govern the tradeoff between accuracy and speed. As default
481 choices, Hashtbl.hash and Hashtbl.seeded_hash take meaningful = 10 and
482 total = 100 .
483 val seeded_hash_param : int -> int -> int -> 'a -> int
487 A variant of Hashtbl.hash_param that is further parameterized by an
489 integer seed. Usage: Hashtbl.seeded_hash_param meaningful total seed x
490 .
491 Since 4.00.0
494OCamldoc 2019-02-02 Hashtbl(3)