Provided by: ocaml-man_4.14.1-1ubuntu1_all bug

NAME

       MoreLabels.Hashtbl - no description

Module

       Module   MoreLabels.Hashtbl

Documentation

       Module Hashtbl
        : sig end

       Hash tables and hash functions.

       Hash tables are hashed association tables, with in-place modification.

   Generic interface
       type ('a, 'b) t = ('a, 'b) Hashtbl.t

       The type of hash tables from type 'a to type 'b .

       val create : ?random:bool -> int -> ('a, 'b) t

       Hashtbl.create n creates a new, empty hash table, with initial size n .  For best results,
       n should be on the order of the expected number of elements that will  be  in  the  table.
       The table grows as needed, so n is just an initial guess.

       The  optional ~ random parameter (a boolean) controls whether the internal organization of
       the hash table is randomized at each execution of Hashtbl.create or deterministic over all
       executions.

       A  hash  table  that  is  created  with ~ random set to false uses a fixed hash function (
       MoreLabels.Hashtbl.hash ) to distribute keys among buckets.  As a consequence,  collisions
       between   keys   happen   deterministically.    In   Web-facing   applications   or  other
       security-sensitive applications, the deterministic collision patterns can be exploited  by
       a malicious user to create a denial-of-service attack: the attacker sends input crafted to
       create many collisions in the table, slowing the application down.

       A hash table that is created with ~ random set to  true  uses  the  seeded  hash  function
       MoreLabels.Hashtbl.seeded_hash  with a seed that is randomly chosen at hash table creation
       time.  In effect, the hash function used is randomly selected among 2^{30} different  hash
       functions.   All  these  hash  functions  have  different  collision  patterns,  rendering
       ineffective  the  denial-of-service  attack  described   above.    However,   because   of
       randomization, enumerating all elements of the hash table using MoreLabels.Hashtbl.fold or
       MoreLabels.Hashtbl.iter is no longer deterministic: elements are enumerated  in  different
       orders at different runs of the program.

       If  no ~ random parameter is given, hash tables are created in non-random mode by default.
       This    default    can    be    changed     either     programmatically     by     calling
       MoreLabels.Hashtbl.randomize  or  by  setting  the R flag in the OCAMLRUNPARAM environment
       variable.

       Before4.00.0 the ~ random parameter was not present and all hash tables  were  created  in
       non-randomized mode.

       val clear : ('a, 'b) t -> unit

       Empty  a  hash table. Use reset instead of clear to shrink the size of the bucket table to
       its initial size.

       val reset : ('a, 'b) t -> unit

       Empty a hash table and shrink the size of the bucket table to its initial size.

       Since 4.00.0

       val copy : ('a, 'b) t -> ('a, 'b) t

       Return a copy of the given hashtable.

       val add : ('a, 'b) t -> key:'a -> data:'b -> unit

       Hashtbl.add tbl ~key ~data adds a binding of key to data in table tbl .  Previous bindings
       for   key   are   not   removed,   but   simply   hidden.   That   is,   after  performing
       MoreLabels.Hashtbl.remove tbl key , the previous binding for key , if  any,  is  restored.
       (Same behavior as with association lists.)

       val find : ('a, 'b) t -> 'a -> 'b

       Hashtbl.find  tbl  x  returns  the current binding of x in tbl , or raises Not_found if no
       such binding exists.

       val find_opt : ('a, 'b) t -> 'a -> 'b option

       Hashtbl.find_opt tbl x returns the current binding of x in  tbl  ,  or  None  if  no  such
       binding exists.

       Since 4.05

       val find_all : ('a, 'b) t -> 'a -> 'b list

       Hashtbl.find_all  tbl  x  returns  the  list  of  all data associated with x in tbl .  The
       current binding is returned first,  then  the  previous  bindings,  in  reverse  order  of
       introduction in the table.

       val mem : ('a, 'b) t -> 'a -> bool

       Hashtbl.mem tbl x checks if x is bound in tbl .

       val remove : ('a, 'b) t -> 'a -> unit

       Hashtbl.remove  tbl  x  removes  the  current binding of x in tbl , restoring the previous
       binding if it exists.  It does nothing if x is not bound in tbl .

       val replace : ('a, 'b) t -> key:'a -> data:'b -> unit

       Hashtbl.replace tbl ~key ~data replaces the current binding of key in tbl by a binding  of
       key to data .  If key is unbound in tbl , a binding of key to data is added to tbl .  This
       is  functionally   equivalent   to   MoreLabels.Hashtbl.remove   tbl   key   followed   by
       MoreLabels.Hashtbl.add tbl key data .

       val iter : f:(key:'a -> data:'b -> unit) -> ('a, 'b) t -> unit

       Hashtbl.iter  ~f tbl applies f to all bindings in table tbl .  f receives the key as first
       argument, and the associated value as second argument. Each binding is  presented  exactly
       once to f .

       The  order  in  which  the bindings are passed to f is unspecified.  However, if the table
       contains several bindings for the same key, they are passed  to  f  in  reverse  order  of
       introduction, that is, the most recent binding is passed first.

       If  the hash table was created in non-randomized mode, the order in which the bindings are
       enumerated is reproducible between successive runs of the program, and even between  minor
       versions  of  OCaml.   For  randomized  hash  tables, the order of enumeration is entirely
       random.

       The behavior is not specified if the hash table is modified by f during the iteration.

       val filter_map_inplace : f:(key:'a -> data:'b -> 'b option) -> ('a, 'b) t -> unit

       Hashtbl.filter_map_inplace ~f tbl applies f to all bindings in table tbl and  update  each
       binding  depending on the result of f .  If f returns None , the binding is discarded.  If
       it returns Some new_val , the binding is update to associate the key to new_val .

       Other comments for MoreLabels.Hashtbl.iter apply as well.

       Since 4.03.0

       val fold : f:(key:'a -> data:'b -> 'c -> 'c) -> ('a, 'b) t -> init:'c -> 'c

       Hashtbl.fold ~f tbl ~init computes (f kN dN ... (f k1 d1 init)...)  , where k1 ... kN  are
       the  keys  of all bindings in tbl , and d1 ... dN are the associated values.  Each binding
       is presented exactly once to f .

       The order in which the bindings are passed to f is unspecified.   However,  if  the  table
       contains  several  bindings  for  the  same  key, they are passed to f in reverse order of
       introduction, that is, the most recent binding is passed first.

       If the hash table was created in non-randomized mode, the order in which the bindings  are
       enumerated  is reproducible between successive runs of the program, and even between minor
       versions of OCaml.  For randomized hash tables,  the  order  of  enumeration  is  entirely
       random.

       The behavior is not specified if the hash table is modified by f during the iteration.

       val length : ('a, 'b) t -> int

       Hashtbl.length  tbl  returns  the  number  of  bindings  in tbl .  It takes constant time.
       Multiple bindings are counted once each, so  Hashtbl.length  gives  the  number  of  times
       Hashtbl.iter calls its first argument.

       val randomize : unit -> unit

       After  a  call  to  Hashtbl.randomize()  ,  hash  tables are created in randomized mode by
       default:  MoreLabels.Hashtbl.create   returns   randomized   hash   tables,   unless   the
       ~random:false optional parameter is given.  The same effect can be achieved by setting the
       R parameter in the OCAMLRUNPARAM environment variable.

       It is recommended that applications or Web frameworks  that  need  to  protect  themselves
       against   the   denial-of-service   attack  described  in  MoreLabels.Hashtbl.create  call
       Hashtbl.randomize() at initialization time.

       Note that once  Hashtbl.randomize()  was  called,  there  is  no  way  to  revert  to  the
       non-randomized  default  behavior  of  MoreLabels.Hashtbl.create  .   This is intentional.
       Non-randomized hash tables can still be created using Hashtbl.create ~random:false .

       Since 4.00.0

       val is_randomized : unit -> bool

       Return true if the tables are currently created  in  randomized  mode  by  default,  false
       otherwise.

       Since 4.03.0

       val rebuild : ?random:bool -> ('a, 'b) t -> ('a, 'b) t

       Return    a   copy   of   the   given   hashtable.    Unlike   MoreLabels.Hashtbl.copy   ,
       MoreLabels.Hashtbl.rebuild h re-hashes all the (key, value) entries of the original  table
       h  .   The  returned  hash table is randomized if h was randomized, or the optional random
       parameter  is  true,  or  if  the  default  is  to  create  randomized  hash  tables;  see
       MoreLabels.Hashtbl.create for more information.

       MoreLabels.Hashtbl.rebuild  can  safely  be  used  to  import a hash table built by an old
       version of the MoreLabels.Hashtbl module, then marshaled  to  persistent  storage.   After
       unmarshaling,  apply  MoreLabels.Hashtbl.rebuild  to  produce a hash table for the current
       version of the MoreLabels.Hashtbl module.

       Since 4.12.0

       type statistics = Hashtbl.statistics = {
        num_bindings : int ;  (* Number of bindings present in the table.  Same value as returned
       by MoreLabels.Hashtbl.length .
        *)
        num_buckets : int ;  (* Number of buckets in the table.
        *)
        max_bucket_length : int ;  (* Maximal number of bindings per bucket.
        *)
        bucket_histogram  :  int  array  ;   (*  Histogram of bucket sizes.  This array histo has
       length max_bucket_length + 1 .  The value of histo.(i) is the number of buckets whose size
       is i .
        *)
        }

       Since 4.00.0

       val stats : ('a, 'b) t -> statistics

       Hashtbl.stats  tbl returns statistics about the table tbl : number of buckets, size of the
       biggest bucket, distribution of buckets by size.

       Since 4.00.0

   Hash tables and Sequences
       val to_seq : ('a, 'b) t -> ('a * 'b) Seq.t

       Iterate on the whole table.  The order in which the bindings appear  in  the  sequence  is
       unspecified. However, if the table contains several bindings for the same key, they appear
       in reversed order of introduction, that is, the most recent binding appears first.

       The behavior is not specified if the hash table is modified during the iteration.

       Since 4.07

       val to_seq_keys : ('a, 'b) t -> 'a Seq.t

       Same as Seq.map fst (to_seq m)

       Since 4.07

       val to_seq_values : ('a, 'b) t -> 'b Seq.t

       Same as Seq.map snd (to_seq m)

       Since 4.07

       val add_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit

       Add the given bindings to the table, using MoreLabels.Hashtbl.add

       Since 4.07

       val replace_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit

       Add the given bindings to the table, using MoreLabels.Hashtbl.replace

       Since 4.07

       val of_seq : ('a * 'b) Seq.t -> ('a, 'b) t

       Build a table from the given bindings. The bindings are  added  in  the  same  order  they
       appear  in  the  sequence,  using MoreLabels.Hashtbl.replace_seq , which means that if two
       pairs have the same key, only the latest one will appear in the table.

       Since 4.07

   Functorial interface
       The functorial interface allows the use of specific comparison and hash functions,  either
       for  performance/security  concerns,  or because keys are not hashable/comparable with the
       polymorphic builtins.

       For instance, one might want to specialize a table for integer keys:
               module IntHash =
                 struct
                   type t = int
                   let equal i j = i=j
                   let hash i = i land max_int
                 end

               module IntHashtbl = Hashtbl.Make(IntHash)

               let h = IntHashtbl.create 17 in
               IntHashtbl.add h 12 "hello"

       This creates a new module IntHashtbl , with a new type 'a
             IntHashtbl.t of tables from int to 'a . In this example, h contains string values so
       its type is string IntHashtbl.t .

       Note  that  the new type 'a IntHashtbl.t is not compatible with the type ('a,'b) Hashtbl.t
       of the generic interface. For example, Hashtbl.length h would not type-check, you must use
       IntHashtbl.length .

       module type HashedType = sig end

       The input signature of the functor MoreLabels.Hashtbl.Make .

       module type S = sig end

       The output signature of the functor MoreLabels.Hashtbl.Make .

       module Make : functor (H : HashedType) -> sig end

       Functor  building  an implementation of the hashtable structure.  The functor Hashtbl.Make
       returns a structure containing a type key  of  keys  and  a  type  'a  t  of  hash  tables
       associating  data  of  type  'a to keys of type key .  The operations perform similarly to
       those of the generic interface, but use the hashing and equality  functions  specified  in
       the  functor  argument H instead of generic equality and hashing.  Since the hash function
       is not seeded, the create operation of the result structure always returns  non-randomized
       hash tables.

       module type SeededHashedType = sig end

       The input signature of the functor MoreLabels.Hashtbl.MakeSeeded .

       Since 4.00.0

       module type SeededS = sig end

       The output signature of the functor MoreLabels.Hashtbl.MakeSeeded .

       Since 4.00.0

       module MakeSeeded : functor (H : SeededHashedType) -> sig end

       Functor   building   an   implementation   of   the   hashtable  structure.   The  functor
       Hashtbl.MakeSeeded returns a structure containing a type key of keys and a type  'a  t  of
       hash  tables  associating  data  of  type 'a to keys of type key .  The operations perform
       similarly to those of the generic interface, but  use  the  seeded  hashing  and  equality
       functions  specified  in  the  functor argument H instead of generic equality and hashing.
       The create operation of the result structure supports the ~ random optional parameter  and
       returns  randomized  hash tables if ~random:true is passed or if randomization is globally
       on (see MoreLabels.Hashtbl.randomize ).

       Since 4.00.0

   The polymorphic hash functions
       val hash : 'a -> int

       Hashtbl.hash x associates a nonnegative integer to any value of any type. It is guaranteed
       that  if  x  = y or Stdlib.compare x y = 0 , then hash x = hash y .  Moreover, hash always
       terminates, even on cyclic structures.

       val seeded_hash : int -> 'a -> int

       A variant of MoreLabels.Hashtbl.hash that is further parameterized by an integer seed.

       Since 4.00.0

       val hash_param : int -> int -> 'a -> int

       Hashtbl.hash_param meaningful total x computes  a  hash  value  for  x  ,  with  the  same
       properties  as  for hash . The two extra integer parameters meaningful and total give more
       precise control over hashing. Hashing performs a breadth-first, left-to-right traversal of
       the  structure  x  , stopping after meaningful meaningful nodes were encountered, or total
       nodes (meaningful or not) were encountered.  If total as specified by the user  exceeds  a
       certain  value,  currently  256,  then  it is capped to that value.  Meaningful nodes are:
       integers;  floating-point   numbers;   strings;   characters;   booleans;   and   constant
       constructors.  Larger  values of meaningful and total means that more nodes are taken into
       account to compute the final hash value, and  therefore  collisions  are  less  likely  to
       happen.   However,  hashing  takes  longer. The parameters meaningful and total govern the
       tradeoff between accuracy and speed.   As  default  choices,  MoreLabels.Hashtbl.hash  and
       MoreLabels.Hashtbl.seeded_hash take meaningful = 10 and total = 100 .

       val seeded_hash_param : int -> int -> int -> 'a -> int

       A  variant  of  MoreLabels.Hashtbl.hash_param  that is further parameterized by an integer
       seed.  Usage: Hashtbl.seeded_hash_param meaningful total seed x .

       Since 4.00.0