Module Hashtree


module Hashtree: sig .. end
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.

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).



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.

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
The functorized version
module Make: 
functor (Key : Key) -> S with module Key = Key