1Hashtbl(3)                       OCaml library                      Hashtbl(3)
2
3
4

NAME

6       Hashtbl - Hash tables and hash functions.
7

Module

9       Module   Hashtbl
10

Documentation

12       Module Hashtbl
13        : sig end
14
15
16       Hash tables and hash functions.
17
18       Hash tables are hashed association tables, with in-place modification.
19
20
21
22
23
24
25
26
27       === Generic interface ===
28
29       type ('a, 'b) t
30
31
32       The type of hash tables from type 'a to type 'b .
33
34
35
36
37       val create : int -> ('a, 'b) t
38
39
40       Hashtbl.create n creates a new, empty hash table, with initial size n .
41       For best results, n should be on the order of the  expected  number  of
42       elements that will be in the table.  The table grows as needed, so n is
43       just an initial guess.
44
45
46
47
48       val clear : ('a, 'b) t -> unit
49
50       Empty a hash table.
51
52
53
54
55       val add : ('a, 'b) t -> 'a -> 'b -> unit
56
57
58       Hashtbl.add tbl x y adds a binding of x to y in table tbl  .   Previous
59       bindings  for x are not removed, but simply hidden. That is, after per‐
60       forming Hashtbl.remove tbl x , the previous binding for x , if any,  is
61       restored.  (Same behavior as with association lists.)
62
63
64
65
66       val copy : ('a, 'b) t -> ('a, 'b) t
67
68       Return a copy of the given hashtable.
69
70
71
72
73       val find : ('a, 'b) t -> 'a -> 'b
74
75
76       Hashtbl.find  tbl x returns the current binding of x in tbl , or raises
77       Not_found if no such binding exists.
78
79
80
81
82       val find_all : ('a, 'b) t -> 'a -> 'b list
83
84
85       Hashtbl.find_all tbl x returns the list of all data associated  with  x
86       in  tbl  .   The  current  binding is returned first, then the previous
87       bindings, in reverse order of introduction in the table.
88
89
90
91
92       val mem : ('a, 'b) t -> 'a -> bool
93
94
95       Hashtbl.mem tbl x checks if x is bound in tbl .
96
97
98
99
100       val remove : ('a, 'b) t -> 'a -> unit
101
102
103       Hashtbl.remove tbl x removes the current binding of x in tbl ,  restor‐
104       ing  the  previous  binding  if it exists.  It does nothing if x is not
105       bound in tbl .
106
107
108
109
110       val replace : ('a, 'b) t -> 'a -> 'b -> unit
111
112
113       Hashtbl.replace tbl x y replaces the current binding of x in tbl  by  a
114       binding  of  x  to y .  If x is unbound in tbl , a binding of x to y is
115       added to tbl .  This is functionally equivalent to Hashtbl.remove tbl x
116       followed by Hashtbl.add tbl x y .
117
118
119
120
121       val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
122
123
124       Hashtbl.iter f tbl applies f to all bindings in table tbl .  f receives
125       the key as first argument, and the associated value as second argument.
126       Each  binding  is presented exactly once to f .  The order in which the
127       bindings are passed to f is unspecified.  However, if  the  table  con‐
128       tains  several  bindings  for  the  same  key,  they are passed to f in
129       reverse order of introduction, that is,  the  most  recent  binding  is
130       passed first.
131
132
133
134
135       val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
136
137
138       Hashtbl.fold  f  tbl  init  computes (f kN dN ... (f k1 d1 init)...)  ,
139       where k1 ... kN are the keys of all bindings in tbl , and d1 ... dN are
140       the  associated  values.  Each binding is presented exactly once to f .
141       The order in which the bindings are passed to f is  unspecified.   How‐
142       ever, if the table contains several bindings for the same key, they are
143       passed to f in reverse order of introduction, that is, the most  recent
144       binding is passed first.
145
146
147
148
149       val length : ('a, 'b) t -> int
150
151
152       Hashtbl.length  tbl  returns  the number of bindings in tbl .  Multiple
153       bindings are counted multiply, so Hashtbl.length gives  the  number  of
154       times Hashtbl.iter calls its first argument.
155
156
157
158
159
160       === Functorial interface ===
161
162       module type HashedType = sig end
163
164
165       The input signature of the functor Hashtbl.Make .
166
167
168
169       module type S = sig end
170
171
172       The output signature of the functor Hashtbl.Make .
173
174
175
176       module Make : functor (H : HashedType) -> sig end
177
178
179       Functor  building  an  implementation  of the hashtable structure.  The
180       functor Hashtbl.Make returns a structure containing a type key of  keys
181       and  a  type 'a t of hash tables associating data of type 'a to keys of
182       type key .  The operations perform similarly to those  of  the  generic
183       interface,  but use the hashing and equality functions specified in the
184       functor argument H instead of generic equality and hashing.
185
186
187
188
189
190       === The polymorphic hash primitive ===
191
192
193       val hash : 'a -> int
194
195
196       Hashtbl.hash x associates a positive integer to any value of any  type.
197       It  is  guaranteed  that  if x = y or Pervasives.compare x y = 0 , then
198       hash x = hash y .  Moreover, hash always  terminates,  even  on  cyclic
199       structures.
200
201
202
203
204       val hash_param : int -> int -> 'a -> int
205
206
207       Hashtbl.hash_param  n  m  x computes a hash value for x , with the same
208       properties as for hash . The two extra parameters n  and  m  give  more
209       precise control over hashing. Hashing performs a depth-first, right-to-
210       left traversal of the structure x , stopping after n  meaningful  nodes
211       were  encountered,  or  m  nodes,  meaningful or not, were encountered.
212       Meaningful nodes are: integers; floating-point numbers; strings;  char‐
213       acters;  booleans;  and constant constructors. Larger values of m and n
214       means that more nodes are taken into account to compute the final  hash
215       value,  and  therefore  collisions are less likely to happen.  However,
216       hashing takes longer. The  parameters  m  and  n  govern  the  tradeoff
217       between accuracy and speed.
218
219
220
221
222
223
224OCamldoc                          2007-05-24                        Hashtbl(3)