Legend:
Library
Module
Module type
Parameter
Class
Class type
A polymorphic hashtbl that uses Pool to avoid allocation.
This uses the standard linked-chain hashtable algorithm, albeit with links performed through a pool and hence avoiding caml_modify (for table manipulation), even when hashing object keys/values.
This implementation is worth exploring for your application if profiling demonstrates that garbage collection and the caml_modify write barrier are a significant part of your execution time.
We provide a sexp_of_t but not a t_of_sexp for this type because one needs to be explicit about the hash and comparison functions used when creating a hashtable. Note that Hashtbl.Poly.t does have [@@deriving sexp], and uses OCaml's built-in polymorphic comparison and and polymorphic hashing.
Creators
val create :
?growth_allowed:bool ->?size:int ->(moduleBase__.Hashtbl_intf.Key.Swithtypet = 'a)->('a, 'b)t
The module you pass to create must have a type that is hashable, sexpable, and comparable.
val of_alist :
?growth_allowed:bool ->?size:int ->(moduleBase__.Hashtbl_intf.Key.Swithtypet = 'a)->('a * 'b) list->[ `Ok of ('a, 'b)t| `Duplicate_key of 'a ]
Example:
Hashtbl.of_alist (module Int) [(3, "something"); (2, "whatever")]
- : [ `Duplicate_key of int | `Ok of (int, string) Hashtbl.t ] = `Ok <abstr>
val of_alist_report_all_dups :
?growth_allowed:bool ->?size:int ->(moduleBase__.Hashtbl_intf.Key.Swithtypet = 'a)->('a * 'b) list->[ `Ok of ('a, 'b)t| `Duplicate_keys of 'a list ]
Whereas of_alist will report Duplicate_key no matter how many dups there are in your list, of_alist_report_all_dups will report each and every duplicate entry.
For example:
Hashtbl.of_alist (module Int) [(1, "foo"); (1, "bar"); (2, "foo"); (2, "bar")];;
- : [ `Duplicate_key of int | `Ok of (int, string) Hashtbl.t ] = `Duplicate_key 1
Hashtbl.of_alist_report_all_dups (module Int) [(1, "foo"); (1, "bar"); (2, "foo"); (2, "bar")];;
- : [ `Duplicate_keys of int list | `Ok of (int, string) Hashtbl.t ] = `Duplicate_keys [1; 2]
Creates a "multi" hashtable, i.e., a hashtable where each key points to a list potentially containing multiple values. So instead of short-circuiting with a `Duplicate_key variant on duplicates, as in of_alist, of_alist_multi folds those values into a list for the given key:
let h = Hashtbl.of_alist_multi (module Int) [(1, "a"); (1, "b"); (2, "c"); (2, "d")];;
val h : (int, string list) Hashtbl.t = <abstr>
Hashtbl.find_exn h 1;;
- : string list = ["b"; "a"]
val create_mapped :
?growth_allowed:bool ->?size:int ->(moduleBase__.Hashtbl_intf.Key.Swithtypet = 'a)->get_key:('r->'a)->get_data:('r->'b)->'r list->[ `Ok of ('a, 'b)t| `Duplicate_keys of 'a list ]
Applies the get_key and get_data functions to the 'r list to create the initial keys and values, respectively, for the new hashtable.
let h =
Hashtbl.create_mapped (module Int)
~get_key:(fun x -> x)
~get_data:(fun x -> x + 1)
[1; 2; 3];;
val h : [ `Duplicate_keys of int list | `Ok of (int, int) Hashtbl.t ] = `Ok <abstr>
let h =
match h with
| `Ok x -> x
| `Duplicate_keys _ -> failwith ""
in
Hashtbl.find_exn h 1;;
- : int = 2
val create_with_key :
?growth_allowed:bool ->?size:int ->(moduleBase__.Hashtbl_intf.Key.Swithtypet = 'a)->get_key:('r->'a)->'r list->[ `Ok of ('a, 'r)t| `Duplicate_keys of 'a list ]
val create_with_key_or_error :
?growth_allowed:bool ->?size:int ->(moduleBase__.Hashtbl_intf.Key.Swithtypet = 'a)->get_key:('r->'a)->'r list->('a, 'r)tBase.Or_error.t
val create_with_key_exn :
?growth_allowed:bool ->?size:int ->(moduleBase__.Hashtbl_intf.Key.Swithtypet = 'a)->get_key:('r->'a)->'r list->('a, 'r)t
val group :
?growth_allowed:bool ->?size:int ->(moduleBase__.Hashtbl_intf.Key.Swithtypet = 'a)->get_key:('r->'a)->get_data:('r->'b)->combine:('b->'b->'b)->'r list->('a, 'b)t
Like create_mapped, applies the get_key and get_data functions to the 'r
list to create the initial keys and values, respectively, for the new hashtable -- and then, like add_multi, folds together values belonging to the same keys. Here, though, the function used for the folding is given by combine (instead of just being a cons).
Example:
Hashtbl.group (module Int)
~get_key:(fun x -> x / 2)
~get_data:(fun x -> x)
~combine:(fun x y -> x * y)
[ 1; 2; 3; 4]
|> Hashtbl.to_alist;;
- : (int * int) list = [(2, 4); (1, 6); (0, 1)]
map t f returns a new table with values replaced by the result of applying f to the current values.
Example:
let h = Hashtbl.of_alist_exn (module Int) [(1, 4); (5, 6)] in
let h' = Hashtbl.map h ~f:(fun x -> x * 2) in
Hashtbl.to_alist h';;
- : (int * int) list = [(5, 12); (1, 8)]
val mapi : ('a, 'b)t->f:(key:'akey->data:'b->'c)->('a, 'c)t
Like map, but the function f takes both key and data as arguments.
val filter_map : ('a, 'b)t->f:('b->'c option)->('a, 'c)t
Returns a new table by filtering the given table's values by f: the keys for which f applied to the current value returns Some are kept, and those for which it returns None are discarded.
Example:
let h = Hashtbl.of_alist_exn (module Int) [(1, 4); (5, 6)] in
Hashtbl.filter_map h ~f:(fun x -> if x > 5 then Some x else None)
|> Hashtbl.to_alist;;
- : (int * int) list = [(5, 6)]
val filter_mapi :
('a, 'b)t->f:(key:'akey->data:'b->'c option)->('a, 'c)t
Like filter_map, but the function f takes both key and data as arguments.
val filter_keys : ('a, 'b)t->f:('akey-> bool)->('a, 'b)t
find_exn t k returns the current binding of k in t, or raises Caml.Not_found or Not_found_s if no such binding exists.
val find_and_call :
('a, 'b)t->'akey->if_found:('b->'c)->if_not_found:('akey->'c)->'c
find_and_call t k ~if_found ~if_not_found
is equivalent to:
match find t k with Some v -> if_found v | None -> if_not_found k
except that it doesn't allocate the option.
val find_and_call1 :
('a, 'b)t->'akey->a:'d->if_found:('b->'d->'c)->if_not_found:('akey->'d->'c)->'c
Just like find_and_call, but takes an extra argument which is passed to if_found and if_not_found, so that the client code can avoid allocating closures or using refs to pass this additional information. This function is only useful in code which tries to minimize heap allocation.
val find_and_call2 :
('a, 'b)t->'akey->a:'d->b:'e->if_found:('b->'d->'e->'c)->if_not_found:('akey->'d->'e->'c)->'c
val findi_and_call :
('a, 'b)t->'akey->if_found:(key:'akey->data:'b->'c)->if_not_found:('akey->'c)->'c
val findi_and_call1 :
('a, 'b)t->'akey->a:'d->if_found:(key:'akey->data:'b->'d->'c)->if_not_found:('akey->'d->'c)->'c
val findi_and_call2 :
('a, 'b)t->'akey->a:'d->b:'e->if_found:(key:'akey->data:'b->'d->'e->'c)->if_not_found:('akey->'d->'e->'c)->'c
find_and_remove t k returns Some (the current binding) of k in t and removes it, or None is no such binding exists.
val merge :
('k, 'a)t->('k, 'b)t->f:
(key:'kkey->[ `Left of 'a| `Right of 'b| `Both of 'a * 'b ]->'c option)->('k, 'c)t
Merges two hashtables.
The result of merge f h1 h2 has as keys the set of all k in the union of the sets of keys of h1 and h2 for which d(k) is not None, where:
d(k) =
f ~key:k (`Left d1) if k in h1 maps to d1, and h2 does not have data for k;
f ~key:k (`Right d2) if k in h2 maps to d2, and h1 does not have data for k;
f ~key:k (`Both (d1, d2)) otherwise, where k in h1 maps to d1 and k in h2 maps to d2.
Each key k is mapped to a single piece of data x, where d(k) = Some x.
Example:
let h1 = Hashtbl.of_alist_exn (module Int) [(1, 5); (2, 3232)] in
let h2 = Hashtbl.of_alist_exn (module Int) [(1, 3)] in
Hashtbl.merge h1 h2 ~f:(fun ~key:_ -> function
| `Left x -> Some (`Left x)
| `Right x -> Some (`Right x)
| `Both (x, y) -> if x=y then None else Some (`Both (x,y))
) |> Hashtbl.to_alist;;
- : (int * [> `Both of int * int | `Left of int | `Right of int ]) list =
[(2, `Left 3232); (1, `Both (5, 3))]
val merge_into :
src:('k, 'a)t->dst:('k, 'b)t->f:
(key:'kkey->'a->'b option->'bBase__.Hashtbl_intf.Merge_into_action.t)->
unit
Every key in src will be removed or set in dst according to the return value of f.
map_inplace t ~f applies f to all elements in t, transforming them in place.
val mapi_inplace : ('a, 'b)t->f:(key:'akey->data:'b->'b)-> unit
val filter_map_inplace : (_, 'b)t->f:('b->'b option)-> unit
filter_map_inplace combines the effects of map_inplace and filter_inplace.
val filter_mapi_inplace :
('a, 'b)t->f:(key:'akey->data:'b->'b option)->
unit
val equal : ('b->'b-> bool)->('a, 'b)t->('a, 'b)t-> bool
equal f t1 t2 and similar f t1 t2 both return true iff t1 and t2 have the same keys and for all keys k, f (find_exn t1 k) (find_exn t2 k). equal and similar only differ in their types.
val similar : ('b1->'b2-> bool)->('a, 'b1)t->('a, 'b2)t-> bool
remove_multi t key updates the table, removing the head of the list bound to key. If the list has only one element (or is empty) then the binding is removed.
resize t size ensures that t can hold at least size entries without resizing (again), provided that t has growth enabled. This is useful for sizing global tables during application initialization, to avoid subsequent, expensive growth online. See Immediate.String.resize, for example.
val on_grow :
before:(unit ->'a)->after:('a->old_capacity:int ->new_capacity:int -> unit)->
unit
on_grow ~before ~after allows you to connect higher level loggers to the point where these hashtbls grow. before is called before the table grows, and after after it. This permits you to e.g. measure the time elapsed between the two.
This is only meant for debugging and profiling, e.g. note that once a callback is installed, there is no way to remove it.