Module Core.Hashtbl_intf

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, but 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 this will result in 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:

There are three kinds of hash-table functions:

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.

Usage

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

  1. For a list of hashtable functions see Core.Hashtbl_intf.S.

  2. 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, e.g., Int63.Table or Host_and_port.Table.

  3. 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, e.g.:

      let equal (x, y) (x', y') = String.(=) x x' && Int63.(=) y y'
  let hash (x, y) = String.hash x + Int63.hash y * 65599
module Binable : sig ... end
module Hashtbl = Base.Hashtbl
module type Key_plain = Hashtbl.Key.S
module Hashable = Base.Hashable
module Merge_into_action = Base.Hashtbl.Merge_into_action
module type Hashable = Base.Hashable.Hashable
module type Key = sig ... end
module type Key_binable = sig ... end
module type Key_stable = sig ... end
module type Creators = sig ... end
module type Accessors = sig ... end
module type Multi = Hashtbl.Multi
type ('key, 'data, 'z) create_options_with_first_class_module = ('key, 'data, 'z) Hashtbl.create_options
type ('key, 'data, 'z) create_options_without_hashable = ?growth_allowed:bool -> ?size:int -> 'z
type ('key, 'data, 'z) create_options_with_hashable = ?growth_allowed:Base.Bool.t -> ?size:Base.Int.t -> hashable:'key Hashable.t -> 'z
module type M_quickcheck = sig ... end
module type For_deriving = sig ... end
module type S_plain = sig ... end
module type S = sig ... end
module type S_binable = sig ... end
module type S_stable = sig ... end
module type Hashtbl = sig ... end