package core_kernel

  1. Overview
  2. Docs
package core_kernel
Legend:
Library
Module
Module type
Parameter
Class
Class type

Core_hashtbl is a reimplementation of the standard MoreLabels.Hashtbl. Its worst case time complexity is O(log(N)) for lookups and additions, unlike the standard MoreLabels.Hashtbl, which is O(N).

A hash table is implemented as an array of AVL trees (see Avltree). If growth_allowed (default true) is false then size is the final size of the array, the table can always hold more elements than size, however they will all go into tree nodes. If it is true (default) then the array will double in size when the number of elements in the table reaches twice the size of the array. When this happens all existing elements will be reinserted, which can take a long time. If you care about latency set size and growth_allowed=false if possible.

In most cases, functions passed as arguments to hash table accessors must not mutate the hash table while it is being accessed, as it will result an an exception. For example, iter and change take a function f which must not modify t. In a few cases, mutation is allowed, such as in Hashtbl.find_and_call, where all access to t is finished before the ~if_found and ~if_not_found arguments are invoked.

We have three kinds of hash table modules:

Hashtbl Hashtbl.Poly Key.Table (a class of similar modules)

There are three kinds of hash-table functions:

creation from nothing (create, of_alist) sexp converters (t_of_sexp, sexp_of_t, and bin_io too) accessors and mappers (fold, mem, find, map, filter_map, ...)

Here is a table showing what classes of functions are available in each kind of hash-table module:

creation sexp-conv accessors Hashtbl X Hashtbl.Poly X X Key.Table X X X'

The entry marked with X' is there for historical reasons, and may be eliminated at some point. The upshot is that one should use Hashtbl for accessors, Hashtbl.Poly for hash-table creation and sexp conversion using polymorphic compare/hash, and Key.Table for hash-table creation and sexp conversion using Key.compare and Key.hash.

For many students of ocaml, using hashtables is complicated by the functors. Here are a few tips:

For a list of hashtable functions see Hashtbl_intf.S.

To create a hashtable with string keys use String.Table.

let table = String.Table.create () ~size:4 in
List.iter ~f:(fun (key, data) -> Hashtbl.set table ~key ~data)
  [ ("A", 1); ("B", 2); ("C", 3); ];
Hashtbl.find table "C"

Here 4 need only be a guess at the hashtable's future size. There are other similar pre-made hashtables, eg Int63.Table or Host_and_port.Table.

To create a hashtable with a custom key type use Hashable.

module Key = struct
  module T = struct
    type t = String.t * Int63.t [@@deriving compare, hash, sexp]
  end
  include T
  include Hashable.Make (T)
end
let table = Key.Table.create () ~size:4 in
List.iter ~f:(fun (key, data) -> Hashtbl.set table ~key ~data)
  [ (("pi", Int63.zero), 3.14159);
    (("e", Int63.minus_one), 2.71828);
    (("Euler", Int63.one), 0.577215);
  ];
Hashtbl.find table ("pi", Int63.zero)

Performance may improve if you define equal and hash explicitly, eg:

let equal (x, y) (x', y') = String.(=) x x' && Int63.(=) y y'
let hash (x, y) = String.hash x + Int63.hash y * 65599
include Core_hashtbl_intf.Hashtbl with type ('a, 'b) t = ('a, 'b) Base.Hashtbl.t
include Base.Hashtbl_intf.S_without_submodules with type ('a, 'b) t = ('a, 'b) Base.Hashtbl.t
module Hashable : sig ... end
val hash : 'a -> int
val hash_param : int -> int -> 'a -> int
type ('a, 'b) t = ('a, 'b) Base.Hashtbl.t

We use [@@deriving_inline sexp_of][@@@end] but not [@@deriving sexp] because we want people to be explicit about the hash and comparison functions used when creating hashtables. One can use Hashtbl.Poly.t, which does have [@@deriving_inline sexp][@@@end], to use polymorphic comparison and hashing.

include sig ... end
include Base.Invariant.S2 with type ('a, 'b) t := ('a, 'b) t
val invariant : ('a -> unit) -> ('b -> unit) -> ('a, 'b) t -> unit
include Base.Hashtbl_intf.Creators with type ('a, 'b) t := ('a, 'b) t with type 'a key = 'a with type ('a, 'b, 'z) create_options := ('a, 'b, 'z) Base.Hashtbl_intf.create_options_with_first_class_module
type 'a key = 'a
include Base.Hashtbl_intf.Accessors with type ('a, 'b) t := ('a, 'b) t with type 'a key := 'a key
type 'a merge_into_action =
  1. | Remove
  2. | Set_to of 'a

Every key in src will be removed or set in dst according to the return value of f.

val hashable : ('key, _) t -> 'key Hashable.t

Shadowing the previous accessors with ones that take Hashable.t

include Base.Hashtbl_intf.S_using_hashable with type ('a, 'b) t := ('a, 'b) t with type 'a key := 'a key with type 'a merge_into_action := 'a merge_into_action
include sig ... end
val sexp_of_t : ('a -> Base.Sexp.t) -> ('b -> Base.Sexp.t) -> ('a, 'b) t -> Base.Sexp.t
include Base.Hashtbl_intf.Creators with type ('a, 'b) t := ('a, 'b) t with type 'a key := 'a key with type ('a, 'b, 'z) create_options := ('a, 'b, 'z) Base.Hashtbl_intf.create_options_with_hashable
val create : ('a key, 'b, unit -> ('a, 'b) t) Base.Hashtbl_intf.create_options_with_hashable
val of_alist : ('a key, 'b, ('a key * 'b) list -> [ `Ok of ('a, 'b) t | `Duplicate_key of 'a key ]) Base.Hashtbl_intf.create_options_with_hashable
val of_alist_report_all_dups : ('a key, 'b, ('a key * 'b) list -> [ `Ok of ('a, 'b) t | `Duplicate_keys of 'a key list ]) Base.Hashtbl_intf.create_options_with_hashable
val of_alist_or_error : ('a key, 'b, ('a key * 'b) list -> ('a, 'b) t Base.Or_error.t) Base.Hashtbl_intf.create_options_with_hashable
val of_alist_exn : ('a key, 'b, ('a key * 'b) list -> ('a, 'b) t) Base.Hashtbl_intf.create_options_with_hashable
val of_alist_multi : ('a key, 'b list, ('a key * 'b) list -> ('a, 'b list) t) Base.Hashtbl_intf.create_options_with_hashable
val create_mapped : ('a key, 'b, get_key:('r -> 'a key) -> get_data:('r -> 'b) -> 'r list -> [ `Ok of ('a, 'b) t | `Duplicate_keys of 'a key list ]) Base.Hashtbl_intf.create_options_with_hashable
create_mapped get_key get_data [x1,...,xn]
= of_alist [get_key x1, get_data x1; ...; get_key xn, get_data xn]
val create_with_key : ('a key, 'r, get_key:('r -> 'a key) -> 'r list -> [ `Ok of ('a, 'r) t | `Duplicate_keys of 'a key list ]) Base.Hashtbl_intf.create_options_with_hashable
create_with_key ~get_key [x1,...,xn]
= of_alist [get_key x1, x1; ...; get_key xn, xn]
val create_with_key_or_error : ('a key, 'r, get_key:('r -> 'a key) -> 'r list -> ('a, 'r) t Base.Or_error.t) Base.Hashtbl_intf.create_options_with_hashable
val create_with_key_exn : ('a key, 'r, get_key:('r -> 'a key) -> 'r list -> ('a, 'r) t) Base.Hashtbl_intf.create_options_with_hashable
val group : ('a key, 'b, get_key:('r -> 'a key) -> get_data:('r -> 'b) -> combine:('b -> 'b -> 'b) -> 'r list -> ('a, 'b) t) Base.Hashtbl_intf.create_options_with_hashable
include Base.Hashtbl_intf.Accessors with type ('a, 'b) t := ('a, 'b) t with type 'a key := 'a key with type 'a merge_into_action := 'a merge_into_action
val sexp_of_key : ('a, _) t -> 'a key -> Base.Sexp.t
val clear : (_, _) t -> unit
val copy : ('a, 'b) t -> ('a, 'b) t
val fold : ('a, 'b) t -> init:'c -> f:(key:'a key -> data:'b -> 'c -> 'c) -> 'c
val iter_keys : ('a, _) t -> f:('a key -> unit) -> unit
val iter : (_, 'b) t -> f:('b -> unit) -> unit
val iteri : ('a, 'b) t -> f:(key:'a key -> data:'b -> unit) -> unit
val iter_vals : (_, 'b) t -> f:('b -> unit) -> unit
  • deprecated [since 2016-04] Use iter instead
val existsi : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> bool
val exists : (_, 'b) t -> f:('b -> bool) -> bool
val for_alli : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> bool
val for_all : (_, 'b) t -> f:('b -> bool) -> bool
val counti : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> int
val count : (_, 'b) t -> f:('b -> bool) -> int
val length : (_, _) t -> int
val is_empty : (_, _) t -> bool
val mem : ('a, _) t -> 'a key -> bool
val remove : ('a, _) t -> 'a key -> unit
val replace : ('a, 'b) t -> key:'a key -> data:'b -> unit
  • deprecated [since 2015-10] Use set instead
val set : ('a, 'b) t -> key:'a key -> data:'b -> unit
val add : ('a, 'b) t -> key:'a key -> data:'b -> [ `Ok | `Duplicate ]
val add_or_error : ('a, 'b) t -> key:'a key -> data:'b -> unit Base.Or_error.t
val add_exn : ('a, 'b) t -> key:'a key -> data:'b -> unit
val change : ('a, 'b) t -> 'a key -> f:('b option -> 'b option) -> unit

change t key ~f changes t's value for key to be f (find t key).

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

update t key ~f is change t key ~f:(fun o -> Some (f o)).

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

add_multi t ~key ~data if key is present in the table then cons data on the list, otherwise add key with a single element list.

val remove_multi : ('a, _ list) t -> 'a key -> unit

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.

val map : ('a, 'b) t -> f:('b -> 'c) -> ('a, 'c) t

map t f returns new table with bound values replaced by f applied to the bound values

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

like map, but function takes both key and data as arguments

val filter_map : ('a, 'b) t -> f:('b -> 'c option) -> ('a, 'c) t

returns new map with bound values filtered by f applied to the bound values

val filter_mapi : ('a, 'b) t -> f:(key:'a key -> data:'b -> 'c option) -> ('a, 'c) t

like filter_map, but function takes both key and data as arguments

val filter_keys : ('a, 'b) t -> f:('a key -> bool) -> ('a, 'b) t
val filter : ('a, 'b) t -> f:('b -> bool) -> ('a, 'b) t
val filteri : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> ('a, 'b) t
val partition_map : ('a, 'b) t -> f:('b -> [ `Fst of 'c | `Snd of 'd ]) -> ('a, 'c) t * ('a, 'd) t

returns new maps with bound values partitioned by f applied to the bound values

val partition_mapi : ('a, 'b) t -> f:(key:'a key -> data:'b -> [ `Fst of 'c | `Snd of 'd ]) -> ('a, 'c) t * ('a, 'd) t

like partition_map, but function takes both key and data as arguments

val partition_tf : ('a, 'b) t -> f:('b -> bool) -> ('a, 'b) t * ('a, 'b) t
val partitioni_tf : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> ('a, 'b) t * ('a, 'b) t
val find_or_add : ('a, 'b) t -> 'a key -> default:(unit -> 'b) -> 'b

find_or_add t k ~default returns the data associated with key k if it is in the table t, otherwise it lets d = default() and adds it to the table.

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

find t k returns Some (the current binding) of k in t, or None if no such binding exists

val find_exn : ('a, 'b) t -> 'a key -> 'b

find_exn t k returns the current binding of k in t, or raises Not_found if no such binding exists.

val find_and_call : ('a, 'b) t -> 'a key -> if_found:('b -> 'c) -> if_not_found:('a key -> '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_remove : ('a, 'b) t -> 'a key -> 'b option

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:'k key -> [ `Left of 'a | `Right of 'b | `Both of 'a * 'b ] -> 'c option) -> ('k, 'c) t

Merge 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 (Some d1) None if k in h1 is to d1, and h2 does not map k;
  • f ~key:k None (Some d2) if k in h2 is to d2, and h1 does not map k;
  • f ~key:k (Some d1) (Some d2) otherwise, where k in h1 is to d1 and k in h2 is to d2.

Each key k is mapped to a single piece of data x, where d(k) = Some x.

val merge_into : src:('k, 'a) t -> dst:('k, 'b) t -> f:(key:'k key -> 'a -> 'b option -> 'b merge_into_action) -> unit
val keys : ('a, _) t -> 'a key list

Returns the list of all keys for given hashtable.

val data : (_, 'b) t -> 'b list

Returns the list of all data for given hashtable.

val filter_keys_inplace : ('a, _) t -> f:('a key -> bool) -> unit

filter_inplace t ~f removes all the elements from t that don't satisfy f.

val filter_inplace : (_, 'b) t -> f:('b -> bool) -> unit
val filteri_inplace : ('a, 'b) t -> f:(key:'a key -> data:'b -> bool) -> unit
val map_inplace : (_, 'b) t -> f:('b -> 'b) -> unit

map_inplace t ~f applies f to all elements in t, transforming them in place

val mapi_inplace : ('a, 'b) t -> f:(key:'a key -> 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:'a key -> data:'b -> 'b option) -> unit
val replace_all : (_, 'b) t -> f:('b -> 'b) -> unit
  • deprecated [since 2016-02] Use map_inplace instead
val replace_alli : ('a, 'b) t -> f:(key:'a key -> data:'b -> 'b) -> unit
  • deprecated [since 2016-02] Use mapi_inplace instead
val filter_replace_all : (_, 'b) t -> f:('b -> 'b option) -> unit
  • deprecated [since 2016-02] Use filter_map_inplace instead
val filter_replace_alli : ('a, 'b) t -> f:(key:'a key -> data:'b -> 'b option) -> unit
  • deprecated [since 2016-02] Use filter_mapi_inplace instead
val equal : ('a, 'b) t -> ('a, 'b) t -> ('b -> 'b -> bool) -> bool

equal t1 t2 f and similar t1 t2 f 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 : ('a, 'b1) t -> ('a, 'b2) t -> ('b1 -> 'b2 -> bool) -> bool
val to_alist : ('a, 'b) t -> ('a key * 'b) list

Returns the list of all (key,data) pairs for given hashtable.

val validate : name:('a key -> string) -> 'b Base.Validate.check -> ('a, 'b) t Base.Validate.check
val incr : ?by:int -> ?remove_if_zero:bool -> ('a, int) t -> 'a key -> unit

remove_if_zero's default is false.

val decr : ?by:int -> ?remove_if_zero:bool -> ('a, int) t -> 'a key -> unit
module Poly : sig ... end
module type Key_plain = Hashable.Hashtbl.Key_plain
module type Key = Hashable.Hashtbl.Key
module type Key_binable = Hashable.Hashtbl.Key_binable
module type S = Hashable.Hashtbl.S
module Make_plain (Key : Core_hashtbl_intf.Key_plain) : sig ... end
module Make (Key : Core_hashtbl_intf.Key) : sig ... end
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct