1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
<html>
<head>
<link rel="stylesheet" href="style.css" type="text/css">
<link rel="Start" href="index.html">
<link rel="previous" href="GraphicsX11.html">
<link rel="next" href="Int32.html">
<link rel="Up" href="index.html">
<link title="Index of types" rel=Appendix href="index_types.html">
<link title="Index of exceptions" rel=Appendix href="index_exceptions.html">
<link title="Index of values" rel=Appendix href="index_values.html">
<link title="Index of modules" rel=Appendix href="index_modules.html">
<link title="Index of module types" rel=Appendix href="index_module_types.html">
<link title="Arg" rel="Chapter" href="Arg.html">
<link title="Arith_status" rel="Chapter" href="Arith_status.html">
<link title="Array" rel="Chapter" href="Array.html">
<link title="ArrayLabels" rel="Chapter" href="ArrayLabels.html">
<link title="Big_int" rel="Chapter" href="Big_int.html">
<link title="Bigarray" rel="Chapter" href="Bigarray.html">
<link title="Buffer" rel="Chapter" href="Buffer.html">
<link title="Callback" rel="Chapter" href="Callback.html">
<link title="CamlinternalMod" rel="Chapter" href="CamlinternalMod.html">
<link title="CamlinternalOO" rel="Chapter" href="CamlinternalOO.html">
<link title="Char" rel="Chapter" href="Char.html">
<link title="Complex" rel="Chapter" href="Complex.html">
<link title="Condition" rel="Chapter" href="Condition.html">
<link title="Dbm" rel="Chapter" href="Dbm.html">
<link title="Digest" rel="Chapter" href="Digest.html">
<link title="Dynlink" rel="Chapter" href="Dynlink.html">
<link title="Event" rel="Chapter" href="Event.html">
<link title="Filename" rel="Chapter" href="Filename.html">
<link title="Format" rel="Chapter" href="Format.html">
<link title="Gc" rel="Chapter" href="Gc.html">
<link title="Genlex" rel="Chapter" href="Genlex.html">
<link title="Graphics" rel="Chapter" href="Graphics.html">
<link title="GraphicsX11" rel="Chapter" href="GraphicsX11.html">
<link title="Hashtbl" rel="Chapter" href="Hashtbl.html">
<link title="Int32" rel="Chapter" href="Int32.html">
<link title="Int64" rel="Chapter" href="Int64.html">
<link title="Lazy" rel="Chapter" href="Lazy.html">
<link title="Lexing" rel="Chapter" href="Lexing.html">
<link title="List" rel="Chapter" href="List.html">
<link title="ListLabels" rel="Chapter" href="ListLabels.html">
<link title="Map" rel="Chapter" href="Map.html">
<link title="Marshal" rel="Chapter" href="Marshal.html">
<link title="MoreLabels" rel="Chapter" href="MoreLabels.html">
<link title="Mutex" rel="Chapter" href="Mutex.html">
<link title="Nativeint" rel="Chapter" href="Nativeint.html">
<link title="Num" rel="Chapter" href="Num.html">
<link title="Obj" rel="Chapter" href="Obj.html">
<link title="Oo" rel="Chapter" href="Oo.html">
<link title="Parsing" rel="Chapter" href="Parsing.html">
<link title="Pervasives" rel="Chapter" href="Pervasives.html">
<link title="Printexc" rel="Chapter" href="Printexc.html">
<link title="Printf" rel="Chapter" href="Printf.html">
<link title="Queue" rel="Chapter" href="Queue.html">
<link title="Random" rel="Chapter" href="Random.html">
<link title="Scanf" rel="Chapter" href="Scanf.html">
<link title="Set" rel="Chapter" href="Set.html">
<link title="Sort" rel="Chapter" href="Sort.html">
<link title="Stack" rel="Chapter" href="Stack.html">
<link title="StdLabels" rel="Chapter" href="StdLabels.html">
<link title="Str" rel="Chapter" href="Str.html">
<link title="Stream" rel="Chapter" href="Stream.html">
<link title="String" rel="Chapter" href="String.html">
<link title="StringLabels" rel="Chapter" href="StringLabels.html">
<link title="Sys" rel="Chapter" href="Sys.html">
<link title="Thread" rel="Chapter" href="Thread.html">
<link title="ThreadUnix" rel="Chapter" href="ThreadUnix.html">
<link title="Unix" rel="Chapter" href="Unix.html">
<link title="UnixLabels" rel="Chapter" href="UnixLabels.html">
<link title="Weak" rel="Chapter" href="Weak.html"><link title="Generic interface" rel="Section" href="#6_Genericinterface">
<link title="Functorial interface" rel="Section" href="#6_Functorialinterface">
<link title="The polymorphic hash primitive" rel="Section" href="#6_Thepolymorphichashprimitive">
<title>Hashtbl</title>
</head>
<body>
<div class="navbar"><a href="GraphicsX11.html">Previous</a>
<a href="index.html">Up</a>
<a href="Int32.html">Next</a>
</div>
<center><h1>Module <a href="type_Hashtbl.html">Hashtbl</a></h1></center>
<br>
<pre><span class="keyword">module</span> Hashtbl: <code class="code"><span class="keyword">sig</span></code> <a href="Hashtbl.html">..</a> <code class="code"><span class="keyword">end</span></code></pre>Hash tables and hash functions.
<p>
Hash tables are hashed association tables, with in-place modification.<br>
<hr width="100%">
<br>
<a name="6_Genericinterface"></a>
<h6>Generic interface</h6><br>
<pre><span class="keyword">type</span> <a name="TYPEt"></a><code class="type">('a, 'b)</code> t </pre>
<div class="info">
The type of hash tables from type <code class="code"><span class="keywordsign">'</span>a</code> to type <code class="code"><span class="keywordsign">'</span>b</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALcreate"></a>create : <code class="type">int -> ('a, 'b) <a href="Hashtbl.html#TYPEt">t</a></code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.create n</code> creates a new, empty hash table, with
initial size <code class="code">n</code>. For best results, <code class="code">n</code> should be on the
order of the expected number of elements that will be in
the table. The table grows as needed, so <code class="code">n</code> is just an
initial guess.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALclear"></a>clear : <code class="type">('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> unit</code></pre><div class="info">
Empty a hash table.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALadd"></a>add : <code class="type">('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> 'a -> 'b -> unit</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.add tbl x y</code> adds a binding of <code class="code">x</code> to <code class="code">y</code> in table <code class="code">tbl</code>.
Previous bindings for <code class="code">x</code> are not removed, but simply
hidden. That is, after performing <a href="Hashtbl.html#VALremove"><code class="code"><span class="constructor">Hashtbl</span>.remove</code></a><code class="code"> tbl x</code>,
the previous binding for <code class="code">x</code>, if any, is restored.
(Same behavior as with association lists.)<br>
</div>
<pre><span class="keyword">val</span> <a name="VALcopy"></a>copy : <code class="type">('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> ('a, 'b) <a href="Hashtbl.html#TYPEt">t</a></code></pre><div class="info">
Return a copy of the given hashtable.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALfind"></a>find : <code class="type">('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> 'a -> 'b</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.find tbl x</code> returns the current binding of <code class="code">x</code> in <code class="code">tbl</code>,
or raises <code class="code"><span class="constructor">Not_found</span></code> if no such binding exists.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALfind_all"></a>find_all : <code class="type">('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> 'a -> 'b list</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.find_all tbl x</code> returns the list of all data
associated with <code class="code">x</code> in <code class="code">tbl</code>.
The current binding is returned first, then the previous
bindings, in reverse order of introduction in the table.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALmem"></a>mem : <code class="type">('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> 'a -> bool</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.mem tbl x</code> checks if <code class="code">x</code> is bound in <code class="code">tbl</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALremove"></a>remove : <code class="type">('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> 'a -> unit</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.remove tbl x</code> removes the current binding of <code class="code">x</code> in <code class="code">tbl</code>,
restoring the previous binding if it exists.
It does nothing if <code class="code">x</code> is not bound in <code class="code">tbl</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALreplace"></a>replace : <code class="type">('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> 'a -> 'b -> unit</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.replace tbl x y</code> replaces the current binding of <code class="code">x</code>
in <code class="code">tbl</code> by a binding of <code class="code">x</code> to <code class="code">y</code>. If <code class="code">x</code> is unbound in <code class="code">tbl</code>,
a binding of <code class="code">x</code> to <code class="code">y</code> is added to <code class="code">tbl</code>.
This is functionally equivalent to <a href="Hashtbl.html#VALremove"><code class="code"><span class="constructor">Hashtbl</span>.remove</code></a><code class="code"> tbl x</code>
followed by <a href="Hashtbl.html#VALadd"><code class="code"><span class="constructor">Hashtbl</span>.add</code></a><code class="code"> tbl x y</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALiter"></a>iter : <code class="type">('a -> 'b -> unit) -> ('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> unit</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.iter f tbl</code> applies <code class="code">f</code> to all bindings in table <code class="code">tbl</code>.
<code class="code">f</code> receives the key as first argument, and the associated value
as second argument. Each binding is presented exactly once to <code class="code">f</code>.
The order in which the bindings are passed to <code class="code">f</code> is unspecified.
However, if the table contains several bindings for the same key,
they are passed to <code class="code">f</code> in reverse order of introduction, that is,
the most recent binding is passed first.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALfold"></a>fold : <code class="type">('a -> 'b -> 'c -> 'c) -> ('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> 'c -> 'c</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.fold f tbl init</code> computes
<code class="code">(f kN dN ... (f k1 d1 init)...)</code>,
where <code class="code">k1 ... kN</code> are the keys of all bindings in <code class="code">tbl</code>,
and <code class="code">d1 ... dN</code> are the associated values.
Each binding is presented exactly once to <code class="code">f</code>.
The order in which the bindings are passed to <code class="code">f</code> is unspecified.
However, if the table contains several bindings for the same key,
they are passed to <code class="code">f</code> in reverse order of introduction, that is,
the most recent binding is passed first.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALlength"></a>length : <code class="type">('a, 'b) <a href="Hashtbl.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.length tbl</code> returns the number of bindings in <code class="code">tbl</code>.
Multiple bindings are counted multiply, so <code class="code"><span class="constructor">Hashtbl</span>.length</code>
gives the number of times <code class="code"><span class="constructor">Hashtbl</span>.iter</code> calls its first argument.<br>
</div>
<br>
<a name="6_Functorialinterface"></a>
<h6>Functorial interface</h6><br>
<pre><span class="keyword">module type</span> <a href="Hashtbl.HashedType.html">HashedType</a> = <code class="code"><span class="keyword">sig</span></code> <a href="Hashtbl.HashedType.html">..</a> <code class="code"><span class="keyword">end</span></code></pre><div class="info">
The input signature of the functor <a href="Hashtbl.Make.html"><code class="code"><span class="constructor">Hashtbl</span>.<span class="constructor">Make</span></code></a>.
</div>
<pre><span class="keyword">module type</span> <a href="Hashtbl.S.html">S</a> = <code class="code"><span class="keyword">sig</span></code> <a href="Hashtbl.S.html">..</a> <code class="code"><span class="keyword">end</span></code></pre><div class="info">
The output signature of the functor <a href="Hashtbl.Make.html"><code class="code"><span class="constructor">Hashtbl</span>.<span class="constructor">Make</span></code></a>.
</div>
<pre><span class="keyword">module</span> <a href="Hashtbl.Make.html">Make</a>: <div class="sig_block"><code class="code"><span class="keyword">functor</span> (</code><code class="code"><span class="constructor">H</span></code><code class="code"> : </code><code class="type"><a href="Hashtbl.HashedType.html">HashedType</a></code><code class="code">) <span class="keywordsign">-></span> </code><code class="type"><a href="Hashtbl.S.html">S</a></code><code class="type"> with type key = H.t</code></div></pre><div class="info">
Functor building an implementation of the hashtable structure.
</div>
<br>
<a name="6_Thepolymorphichashprimitive"></a>
<h6>The polymorphic hash primitive</h6><br>
<pre><span class="keyword">val</span> <a name="VALhash"></a>hash : <code class="type">'a -> int</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.hash x</code> associates a positive integer to any value of
any type. It is guaranteed that
if <code class="code">x = y</code> or <code class="code"><span class="constructor">Pervasives</span>.compare x y = 0</code>, then <code class="code">hash x = hash y</code>.
Moreover, <code class="code">hash</code> always terminates, even on cyclic
structures.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALhash_param"></a>hash_param : <code class="type">int -> int -> 'a -> int</code></pre><div class="info">
<code class="code"><span class="constructor">Hashtbl</span>.hash_param n m x</code> computes a hash value for <code class="code">x</code>, with the
same properties as for <code class="code">hash</code>. The two extra parameters <code class="code">n</code> and
<code class="code">m</code> give more precise control over hashing. Hashing performs a
depth-first, right-to-left traversal of the structure <code class="code">x</code>, stopping
after <code class="code">n</code> meaningful nodes were encountered, or <code class="code">m</code> nodes,
meaningful or not, were encountered. Meaningful nodes are: integers;
floating-point numbers; strings; characters; booleans; and constant
constructors. Larger values of <code class="code">m</code> and <code class="code">n</code> 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 <code class="code">m</code> and <code class="code">n</code>
govern the tradeoff between accuracy and speed.<br>
</div>
</body></html>
|
