module Hashtree:This module implements a normal hashtbl, with one tweak. Instead of using linked lists for buckets it uses (mutable) AVL trees. This property means that the worst case time complexity of find, add, and remove is O(log(N)), instead of O(N) as with the list version. As with the standard Hashtbl, the average case time complexity is O(1) with a good hash function, and the constants appear to be comparable.sig
..end
You must pay for this guarentee by specifying a comparison
function instead of an equality function (the polymorphic version
uses Pervasives.compare). This means that this version of hashtbl
does not work with certian classes of keys (E.G. keys where
physical equality is the only method of comparison).
You must pay for this guarentee by specifying a comparison
function instead of an equality function (the polymorphic version
uses Pervasives.compare). This means that this version of hashtbl
does not work with certian classes of keys (E.G. keys where
physical equality is the only method of comparison).
type ('a, 'b)
t
include Sexpable.S2
include Binable.S2
val create : int -> ('a, 'b) t
val add : ('a, 'b) t -> key:'a -> data:'b -> unit
val remove : ('a, 'b) t -> 'a -> unit
val find : ('a, 'b) t -> 'a -> 'b option
val length : ('a, 'b) t -> int
val fold : ('a, 'b) t -> init:'c -> f:(key:'a -> data:'b -> 'c -> 'c) -> 'c
module type Key =sig
..end
module type S =sig
..end
module Make: