home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / Moscow ML 1.31 / source code / mosml / src / compiler / Hasht.sig < prev    next >
Encoding:
Text File  |  1996-07-03  |  2.6 KB  |  61 lines  |  [TEXT/R*ch]
  1. (* Hasht.sig *)
  2.  
  3. (* Hash tables and hash functions *)
  4.  
  5. (* Hash tables are hashed association tables, with in-place modification. *)
  6.  
  7. type ('a, 'b) t;
  8.         (* The type of hash tables from type ['a] to type ['b]. *)
  9.  
  10. val new : int -> ('_a, '_b) t;
  11.         (* [new n] creates a new, empty hash table, with initial size [n].
  12.            The table grows as needed, so [n] is just an initial guess.
  13.            Better results are said to be achieved when [n] is a prime
  14.            number. *)
  15.  
  16. val clear : ('a, 'b) t -> unit;
  17.         (* Empty a hash table. *)
  18.  
  19. val insert : (''_a, '_b) t -> ''_a -> '_b -> unit;
  20.         (* [insert tbl x y] adds a binding of [x] to [y] in table [tbl].
  21.            The previous binding for [x] is removed (if any). *)
  22.  
  23. val find : (''a, 'b) t -> ''a -> 'b;
  24.         (* [find tbl x] returns the current binding of [x] in [tbl],
  25.            or raises [Subscript] if no such binding exists. *)
  26.  
  27. val remove : (''a, 'b) t -> ''a -> unit;
  28.         (* [remove tbl x] removes the current binding of [x] in [tbl].
  29.            It does nothing if [x] is not bound in [tbl]. *)
  30.  
  31. val apply : ('a -> 'b -> unit) -> ('a, 'b) t -> unit;
  32.         (* [apply f tbl] applies [f] to all bindings in table [tbl].
  33.            [f] receives the key as first argument, and the associated
  34.            value as second argument. The order in which the bindings
  35.            are passed to [f] is unpredictable. *)
  36.  
  37. (*** The polymorphic hash primitive *)
  38.  
  39. val hash : 'a -> int;
  40.         (* [hash x] associates a positive integer to any value of
  41.            any type. It is guaranteed that
  42.                 if [x = y], then [hash x = hash y].
  43.            Moreover, [hash] always terminates, even on cyclic
  44.            structures. *)
  45.  
  46. prim_val hash_param : int -> int -> 'a -> int = 3 "hash_univ_param";
  47.         (* [hash_param n m x] computes a hash value for [x], with the
  48.            same properties as for [hash]. The two extra parameters
  49.            [n] and [m] give more precise control over hashing.
  50.            Hashing performs a depth-first, right-to-left traversal of
  51.            the structure [x], stopping after [n] meaningful nodes
  52.            were encountered, or [m] nodes, meaningful or not, were
  53.            encountered. Meaningful nodes are: integers;
  54.            floating-point numbers; strings; characters; booleans; and
  55.            constant constructors. Larger values of [m] and [n] means
  56.            that more nodes are taken into account to compute the
  57.            final hash value, and therefore collisions are less likely
  58.            to happen.  However, hashing takes longer. The parameters
  59.            [m] and [n] govern the tradeoff between accuracy and
  60.            speed. *)
  61.