module Core_hashtbl:sig
..end
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.
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
.
Hashtbl_intf.S
. 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. module Key = struct
module T = struct
type t = String.t * Int63.t with sexp
let compare = compare
let hash = Hashtbl.hash
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