NAME¶

Hashtbl - Hash tables and hash functions.

Module¶

Module Hashtbl

Documentation¶

Module Hashtbl
: sig end Hash tables and hash functions. Hash tables are hashed association tables, with in-place modification. === Generic interface === type ('a, 'b) t The type of hash tables from type 'a to type 'b . val create : int -> ('a, 'b) t Hashtbl.create n creates a new, empty hash table, with initial size n . For best results, n should be on the order of the expected number of elements that will be in the table. The table grows as needed, so n is just an initial guess. val clear : ('a, 'b) t -> unit Empty a hash table. val add : ('a, 'b) t -> 'a -> 'b -> unit Hashtbl.add tbl x y adds a binding of x to y in table tbl . Previous bindings for x are not removed, but simply hidden. That is, after performing Hashtbl.remove tbl x , the previous binding for x , if any, is restored. (Same behavior as with association lists.) val copy : ('a, 'b) t -> ('a, 'b) t Return a copy of the given hashtable. val find : ('a, 'b) t -> 'a -> 'b Hashtbl.find tbl x returns the current binding of x in tbl , or raises Not_found if no such binding exists. val find_all : ('a, 'b) t -> 'a -> 'b list Hashtbl.find_all tbl x returns the list of all data associated with x in tbl . The current binding is returned first, then the previous bindings, in reverse order of introduction in the table. val mem : ('a, 'b) t -> 'a -> bool Hashtbl.mem tbl x checks if x is bound in tbl . val remove : ('a, 'b) t -> 'a -> unit Hashtbl.remove tbl x removes the current binding of x in tbl , restoring the previous binding if it exists. It does nothing if x is not bound in tbl . val replace : ('a, 'b) t -> 'a -> 'b -> unit Hashtbl.replace tbl x y replaces the current binding of x in tbl by a binding of x to y . If x is unbound in tbl , a binding of x to y is added to tbl . This is functionally equivalent to Hashtbl.remove tbl x followed by Hashtbl.add tbl x y . val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit Hashtbl.iter f tbl applies f to all bindings in table tbl . f receives the key as first argument, and the associated value as second argument. Each binding is presented exactly once to f . The order in which the bindings are passed to f is unspecified. However, if the table contains several bindings for the same key, they are passed to f in reverse order of introduction, that is, the most recent binding is passed first. val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c Hashtbl.fold f tbl init computes (f kN dN ... (f k1 d1 init)...) , where k1 ... kN are the keys of all bindings in tbl , and d1 ... dN are the associated values. Each binding is presented exactly once to f . The order in which the bindings are passed to f is unspecified. However, if the table contains several bindings for the same key, they are passed to f in reverse order of introduction, that is, the most recent binding is passed first. val length : ('a, 'b) t -> int Hashtbl.length tbl returns the number of bindings in tbl . Multiple bindings are counted multiply, so Hashtbl.length gives the number of times Hashtbl.iter calls its first argument. === Functorial interface === module type HashedType = sig end The input signature of the functor Hashtbl.Make . module type S = sig end The output signature of the functor Hashtbl.Make . module Make : functor (H : HashedType) -> sig end Functor building an implementation of the hashtable structure. The functor Hashtbl.Make returns a structure containing a type key of keys and a type 'a t of hash tables associating data of type 'a to keys of type key . The operations perform similarly to those of the generic interface, but use the hashing and equality functions specified in the functor argument H instead of generic equality and hashing. === The polymorphic hash primitive === val hash : 'a -> int Hashtbl.hash x associates a positive integer to any value of any type. It is guaranteed that if x = y or Pervasives.compare x y = 0 , then hash x = hash y . Moreover, hash always terminates, even on cyclic structures. val hash_param : int -> int -> 'a -> int Hashtbl.hash_param n m x computes a hash value for x , with the same properties as for hash . The two extra parameters n and m give more precise control over hashing. Hashing performs a depth-first, right-to-left traversal of the structure x , stopping after n meaningful nodes were encountered, or m nodes, meaningful or not, were encountered. Meaningful nodes are: integers; floating-point numbers; strings; characters; booleans; and constant constructors. Larger values of m and n means that more nodes are taken into account to compute the final hash value, and therefore collisions are less likely to happen. However, hashing takes longer. The parameters m and n govern the tradeoff between accuracy and speed.