This file is indexed.

/usr/share/gap/doc/ref/chap28.html is in gap-doc 4r6p5-3.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (ref) - Chapter 28: Dictionaries and General Hash Tables</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap28"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chap12.html">12</a>  <a href="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chap19.html">19</a>  <a href="chap20.html">20</a>  <a href="chap21.html">21</a>  <a href="chap22.html">22</a>  <a href="chap23.html">23</a>  <a href="chap24.html">24</a>  <a href="chap25.html">25</a>  <a href="chap26.html">26</a>  <a href="chap27.html">27</a>  <a href="chap28.html">28</a>  <a href="chap29.html">29</a>  <a href="chap30.html">30</a>  <a href="chap31.html">31</a>  <a href="chap32.html">32</a>  <a href="chap33.html">33</a>  <a href="chap34.html">34</a>  <a href="chap35.html">35</a>  <a href="chap36.html">36</a>  <a href="chap37.html">37</a>  <a href="chap38.html">38</a>  <a href="chap39.html">39</a>  <a href="chap40.html">40</a>  <a href="chap41.html">41</a>  <a href="chap42.html">42</a>  <a href="chap43.html">43</a>  <a href="chap44.html">44</a>  <a href="chap45.html">45</a>  <a href="chap46.html">46</a>  <a href="chap47.html">47</a>  <a href="chap48.html">48</a>  <a href="chap49.html">49</a>  <a href="chap50.html">50</a>  <a href="chap51.html">51</a>  <a href="chap52.html">52</a>  <a href="chap53.html">53</a>  <a href="chap54.html">54</a>  <a href="chap55.html">55</a>  <a href="chap56.html">56</a>  <a href="chap57.html">57</a>  <a href="chap58.html">58</a>  <a href="chap59.html">59</a>  <a href="chap60.html">60</a>  <a href="chap61.html">61</a>  <a href="chap62.html">62</a>  <a href="chap63.html">63</a>  <a href="chap64.html">64</a>  <a href="chap65.html">65</a>  <a href="chap66.html">66</a>  <a href="chap67.html">67</a>  <a href="chap68.html">68</a>  <a href="chap69.html">69</a>  <a href="chap70.html">70</a>  <a href="chap71.html">71</a>  <a href="chap72.html">72</a>  <a href="chap73.html">73</a>  <a href="chap74.html">74</a>  <a href="chap75.html">75</a>  <a href="chap76.html">76</a>  <a href="chap77.html">77</a>  <a href="chap78.html">78</a>  <a href="chap79.html">79</a>  <a href="chap80.html">80</a>  <a href="chap81.html">81</a>  <a href="chap82.html">82</a>  <a href="chap83.html">83</a>  <a href="chap84.html">84</a>  <a href="chap85.html">85</a>  <a href="chap86.html">86</a>  <a href="chap87.html">87</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap27.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap29.html">[Next Chapter]</a>&nbsp;  </div>

<p id="mathjaxlink" class="pcenter"><a href="chap28_mj.html">[MathJax on]</a></p>
<p><a id="X867203C5877489A2" name="X867203C5877489A2"></a></p>
<div class="ChapSects"><a href="chap28.html#X867203C5877489A2">28 <span class="Heading">Dictionaries and General Hash Tables</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap28.html#X81560C4083E27955">28.1 <span class="Heading">Using Dictionaries</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap28.html#X7B571EA282AF70D7">28.2 <span class="Heading">Dictionaries</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X7E78E3E983A5C895">28.2-1 NewDictionary</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap28.html#X86BD015B7B889329">28.3 <span class="Heading">Dictionaries via Binary Lists</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X865D5BE1830A448D">28.3-1 DictionaryByPosition</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X87F7247E784021C2">28.3-2 IsDictionary</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X7D776BC67ABDDCCE">28.3-3 IsLookupDictionary</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X86C4F0507AD98B8A">28.3-4 AddDictionary</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X808C885D7E267285">28.3-5 KnowsDictionary</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X863706BF847A47EB">28.3-6 LookupDictionary</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap28.html#X8444087381BBA88A">28.4 <span class="Heading">General Hash Tables</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap28.html#X85CD6C9B85DE7C54">28.5 <span class="Heading">Hash keys</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X79DEEB5783513838">28.5-1 DenseIntKey</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X87FC10AC81E5F6BA">28.5-2 SparseIntKey</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap28.html#X84D1A83C8247E7FB">28.6 <span class="Heading">Dense hash tables</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X874FAA447930C7DA">28.6-1 DenseHashTable</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap28.html#X7FDB74417A19E674">28.7 <span class="Heading">Sparse hash tables</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X8757D3A785290640">28.7-1 SparseHashTable</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap28.html#X80FDDF957887B4FC">28.7-2 DoubleHashArraySize</a></span>
</div></div>
</div>

<h3>28 <span class="Heading">Dictionaries and General Hash Tables</span></h3>

<p>People and computers spend a large amount of time with searching. Dictionaries are an abstract data structure which facilitates searching for objects. Depending on the kind of objects the implementation will use a variety of possible internal storage methods that will aim to provide the fastest possible access to objects. These internal methods include</p>


<dl>
<dt><strong class="Mark">Hash Tables</strong></dt>
<dd><p>for objects for which a hash function has been defined.</p>

</dd>
<dt><strong class="Mark">Direct Indexing</strong></dt>
<dd><p>if the domain is small and cheaply enumerable</p>

</dd>
<dt><strong class="Mark">Sorted Lists</strong></dt>
<dd><p>if a total order can be computed easily</p>

</dd>
<dt><strong class="Mark">Plain lists</strong></dt>
<dd><p>for objects for which nothing but an equality test is available.</p>

</dd>
</dl>
<p><a id="X81560C4083E27955" name="X81560C4083E27955"></a></p>

<h4>28.1 <span class="Heading">Using Dictionaries</span></h4>

<p>The standard way to use dictionaries is to first create a dictionary (using <code class="func">NewDictionary</code> (<a href="chap28.html#X7E78E3E983A5C895"><span class="RefLink">28.2-1</span></a>), and then to store objects (and associated information) in it and look them up.</p>

<p>For the creation of objects the user has to make a few choices: Is the dictionary only to be used to check whether objects are known already, or whether associated information is to be stored with the objects. This second case is called a <em>lookup dictionary</em> and is selected by the second parameter of <code class="func">NewDictionary</code> (<a href="chap28.html#X7E78E3E983A5C895"><span class="RefLink">28.2-1</span></a>).</p>

<p>The second choice is to indicate which kind of objects are to be stored. This choice will decide the internal storage used. This kind of objects is specified by the first parameter to <code class="func">NewDictionary</code> (<a href="chap28.html#X7E78E3E983A5C895"><span class="RefLink">28.2-1</span></a>), which is a "sample" object.</p>

<p>In some cases however such a sample object is not specific enough. For example when storing vectors over a finite field, it would not be clear whether all vectors will be over a prime field or over a field extension. Such an issue can be resolved by indicating in an (optional) third parameter to <code class="func">NewDictionary</code> (<a href="chap28.html#X7E78E3E983A5C895"><span class="RefLink">28.2-1</span></a>) a <em>domain</em> which has to be a collection that will contain all objects to be used with this dictionary. (Such a domain may also be used internally to decide that direct indexing can be used).</p>

<p>The reason for this choice of giving two parameters is that in some cases no suitable collection of objects has been defined in <strong class="pkg">GAP</strong> - for example for permutations there is no object representing the symmetric group on infinitely many points.</p>

<p>Once a dictionary has been created, it is possible to use <code class="func">RepresentationsOfObject</code> (<a href="chap13.html#X7BBE93BE7977750F"><span class="RefLink">13.4-1</span></a>) to check which representation is used by <strong class="pkg">GAP</strong>.</p>

<p>In the following example, we create a dictionary to store permutations with associated information.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">d:=NewDictionary((1,2,3),true);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AddDictionary(d,(1,2),1);</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AddDictionary(d,(5,6),9);</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AddDictionary(d,(4,7),2);</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">LookupDictionary(d,(5,6));</span>
9
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">LookupDictionary(d,(5,7));</span>
fail
</pre></div>

<p>A typical example of this use would be in an orbit algorithm. The dictionary would be used to store the elements known in the orbit together with their respective orbit positions.</p>

<p>We observe that this dictionary is stored internally by a sorted list. On the other hand, if we have an explicit, sorted element list, direct indexing is to be used.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RepresentationsOfObject(d);</span>
[ "IsComponentObjectRep", "IsDictionaryDefaultRep", 
  "IsListDictionary", "IsListLookupDictionary", "IsSortDictionary", 
  "IsSortLookupDictionary" ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">d:=NewDictionary((1,2,3),true,Elements(SymmetricGroup(5)));;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RepresentationsOfObject(d);</span>
[ "IsComponentObjectRep", "IsDictionaryDefaultRep", 
  "IsPositionDictionary", "IsPositionDictionary" ]
</pre></div>

<p>(Just indicating <code class="code">SymmetricGroup(5)</code> as a third parameter would still keep the first storage method, as indexing would be too expensive if no explicit element list is known.)</p>

<p>The same effect happens in the following example, in which we work with vectors: Indicating only a vector only enables sorted index, as it cannot be known whether all vectors will be defined over the prime field. On the other hand, providing the vector space (and thus limiting the domain) enables the use of hashing (which will be faster).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">v:=GF(2)^7;;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">d:=NewDictionary(Zero(v),true);;                            </span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RepresentationsOfObject(d);</span>
[ "IsComponentObjectRep", "IsDictionaryDefaultRep", 
  "IsListDictionary", "IsListLookupDictionary", "IsSortDictionary", 
  "IsSortLookupDictionary" ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">d:=NewDictionary(Zero(v),true,v);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RepresentationsOfObject(d);</span>
[ "IsComponentObjectRep", "IsDictionaryDefaultRep", 
  "IsPositionDictionary", "IsPositionDictionary" ]
</pre></div>

<p><a id="X7B571EA282AF70D7" name="X7B571EA282AF70D7"></a></p>

<h4>28.2 <span class="Heading">Dictionaries</span></h4>

<p>This section contains the formal declarations for dictionaries. For information on how to use them, please refer to the previous section <a href="chap28.html#X81560C4083E27955"><span class="RefLink">28.1</span></a>. There are several ways how dictionaries are implemented: As lists, as sorted lists, as hash tables or via binary lists. A user however will just have to call <code class="func">NewDictionary</code> (<a href="chap28.html#X7E78E3E983A5C895"><span class="RefLink">28.2-1</span></a>) and obtain a "suitable" dictionary for the kind of objects she wants to create. It is possible however to create hash tables (see <a href="chap28.html#X8444087381BBA88A"><span class="RefLink">28.4</span></a>) and dictionaries using binary lists (see <code class="func">DictionaryByPosition</code> (<a href="chap28.html#X865D5BE1830A448D"><span class="RefLink">28.3-1</span></a>)).</p>

<p>The use of two objects, <var class="Arg">obj</var> and <var class="Arg">objcoll</var> to parametrize the objects a dictionary is able to store might look confusing. However there are situations where either of them might be needed:</p>

<p>The first situation is that of objects, for which no formal "collection object" has been defined. A typical example here might be subspaces of a vector space. <strong class="pkg">GAP</strong> does not formally define a "Grassmannian" or anything else to represent the multitude of all subspaces. So it is only possible to give the dictionary a "sample object".</p>

<p>The other situation is that of an object which might represent quite varied domains. The permutation <span class="SimpleMath">(1,10^6)</span> might be the nontrivial element of a cyclic group of order 2, it might be a representative of <span class="SimpleMath">S_{10^6}</span>. In the first situation the best approach might be just to have two entries for the two possible objects, in the second situation a much more elaborate approach might be needed.</p>

<p>An algorithm that creates a dictionary will usually know a priori, from what domain all the objects will be, giving this domain permits to use a more efficient dictionary.</p>

<p>This is particularly true for vectors. From a single vector one cannot decide whether a calculation will take place over the smallest field containing all its entries or over a larger field.</p>

<p><a id="X7E78E3E983A5C895" name="X7E78E3E983A5C895"></a></p>

<h5>28.2-1 NewDictionary</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; NewDictionary</code>( <var class="Arg">obj</var>, <var class="Arg">look</var>[, <var class="Arg">objcoll</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>creates a new dictionary for objects such as <var class="Arg">obj</var>. If <var class="Arg">objcoll</var> is given the dictionary will be for objects only from this collection, knowing this can improve the performance. If <var class="Arg">objcoll</var> is given, <var class="Arg">obj</var> may be replaced by <code class="keyw">false</code>, i.e. no sample object is needed.</p>

<p>The function tries to find the right kind of dictionary for the basic dictionary functions to be quick. If <var class="Arg">look</var> is <code class="keyw">true</code>, the dictionary will be a lookup dictionary, otherwise it is an ordinary dictionary.</p>

<p><a id="X86BD015B7B889329" name="X86BD015B7B889329"></a></p>

<h4>28.3 <span class="Heading">Dictionaries via Binary Lists</span></h4>

<p>As there are situations where the approach via binary lists is explicitly desired, such dictionaries can be created deliberately.</p>

<p><a id="X865D5BE1830A448D" name="X865D5BE1830A448D"></a></p>

<h5>28.3-1 DictionaryByPosition</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DictionaryByPosition</code>( <var class="Arg">list</var>, <var class="Arg">lookup</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>creates a new (lookup) dictionary which uses <code class="func">PositionCanonical</code> (<a href="chap21.html#X7B4B10AE81602D4E"><span class="RefLink">21.16-3</span></a>) in <var class="Arg">list</var> for indexing. The dictionary will have an entry <var class="Arg">dict</var><code class="code">!.blist</code> which is a bit list corresponding to <var class="Arg">list</var> indicating the known values. If <var class="Arg">look</var> is <code class="keyw">true</code>, the dictionary will be a lookup dictionary, otherwise it is an ordinary dictionary.</p>

<p><a id="X87F7247E784021C2" name="X87F7247E784021C2"></a></p>

<h5>28.3-2 IsDictionary</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsDictionary</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>A dictionary is a growable collection of objects that permits to add objects (with associated values) and to check whether an object is already known.</p>

<p><a id="X7D776BC67ABDDCCE" name="X7D776BC67ABDDCCE"></a></p>

<h5>28.3-3 IsLookupDictionary</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsLookupDictionary</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>A <em>lookup dictionary</em> is a dictionary, which permits not only to check whether an object is contained, but also to retrieve associated values, using the operation <code class="func">LookupDictionary</code> (<a href="chap28.html#X863706BF847A47EB"><span class="RefLink">28.3-6</span></a>).</p>

<p><a id="X86C4F0507AD98B8A" name="X86C4F0507AD98B8A"></a></p>

<h5>28.3-4 AddDictionary</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; AddDictionary</code>( <var class="Arg">dict</var>, <var class="Arg">key</var>[, <var class="Arg">val</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>adds <var class="Arg">key</var> to the dictionary <var class="Arg">dict</var>, storing the associated value <var class="Arg">val</var> in case <var class="Arg">dict</var> is a lookup dictionary. If <var class="Arg">key</var> is not an object of the kind for which the dictionary was specified, or if <var class="Arg">key</var> is known already to <var class="Arg">dict</var>, the results are unpredictable.</p>

<p><a id="X808C885D7E267285" name="X808C885D7E267285"></a></p>

<h5>28.3-5 KnowsDictionary</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; KnowsDictionary</code>( <var class="Arg">dict</var>, <var class="Arg">key</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>checks, whether <var class="Arg">key</var> is known to the dictionary <var class="Arg">dict</var>, and returns <code class="keyw">true</code> or <code class="keyw">false</code> accordingly. <var class="Arg">key</var> <em>must</em> be an object of the kind for which the dictionary was specified, otherwise the results are unpredictable.</p>

<p><a id="X863706BF847A47EB" name="X863706BF847A47EB"></a></p>

<h5>28.3-6 LookupDictionary</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; LookupDictionary</code>( <var class="Arg">dict</var>, <var class="Arg">key</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>looks up <var class="Arg">key</var> in the lookup dictionary <var class="Arg">dict</var> and returns the associated value. If <var class="Arg">key</var> is not known to the dictionary, <code class="keyw">fail</code> is returned.</p>

<p><a id="X8444087381BBA88A" name="X8444087381BBA88A"></a></p>

<h4>28.4 <span class="Heading">General Hash Tables</span></h4>

<p>These sections describe some particularities for hash tables. These are intended mainly for extending the implementation - programs requiring hash functionality ought to use the dictionary interface described above.</p>

<p>We hash by keys and also store a value. Keys cannot be removed from the table, but the corresponding value can be changed. Fast access to last hash index allows you to efficiently store more than one array of values –this facility should be used with care.</p>

<p>This code works for any kind of object, provided you have a <code class="func">DenseIntKey</code> (<a href="chap28.html#X79DEEB5783513838"><span class="RefLink">28.5-1</span></a>) method to convert the key into a positive integer. This method should ideally be implemented efficiently in the core.</p>

<p>Note that, for efficiency, it is currently impossible to create a hash table with non-positive integers.</p>

<p><a id="X85CD6C9B85DE7C54" name="X85CD6C9B85DE7C54"></a></p>

<h4>28.5 <span class="Heading">Hash keys</span></h4>

<p>The crucial step of hashing is to transform key objects into integers such that equal objects produce the same integer.</p>

<p>The actual function used will vary very much on the type of objects. However <strong class="pkg">GAP</strong> provides already key functions for some commonly encountered objects.</p>

<p><a id="X79DEEB5783513838" name="X79DEEB5783513838"></a></p>

<h5>28.5-1 DenseIntKey</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DenseIntKey</code>( <var class="Arg">objcoll</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns a function that can be used as hash key function for objects such as <var class="Arg">obj</var> in the collection <var class="Arg">objcoll</var>. Typically, <var class="Arg">objcoll</var> will be a large domain. If the domain is not available, it can be given as <code class="keyw">false</code> in which case the hash key function will be determined only based on <var class="Arg">obj</var>. (For a further discussion of these two arguments see <code class="func">NewDictionary</code> (<a href="chap28.html#X7E78E3E983A5C895"><span class="RefLink">28.2-1</span></a>)).</p>

<p>The function returned by <code class="func">DenseIntKey</code> is guaranteed to give different values for different objects. If no suitable hash key function has been predefined, <code class="keyw">fail</code> is returned.</p>

<p><a id="X87FC10AC81E5F6BA" name="X87FC10AC81E5F6BA"></a></p>

<h5>28.5-2 SparseIntKey</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; SparseIntKey</code>( <var class="Arg">objcoll</var>, <var class="Arg">obj</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns a function that can be used as hash key function for objects such as <var class="Arg">obj</var> in the collection <var class="Arg">objcoll</var>. In contrast to <code class="func">DenseIntKey</code> (<a href="chap28.html#X79DEEB5783513838"><span class="RefLink">28.5-1</span></a>), the function returned may return the same key value for different objects. If no suitable hash key function has been predefined, <code class="keyw">fail</code> is returned.</p>

<p><a id="X84D1A83C8247E7FB" name="X84D1A83C8247E7FB"></a></p>

<h4>28.6 <span class="Heading">Dense hash tables</span></h4>

<p>Dense hash tables are used for hashing dense sets without collisions, in particular integers. Keys are stored as an unordered list and values as an array with holes. The position of a value is given by the function returned by <code class="func">DenseIntKey</code> (<a href="chap28.html#X79DEEB5783513838"><span class="RefLink">28.5-1</span></a>), and so <code class="code">KeyIntDense</code> must be one-to-one.</p>

<p><a id="X874FAA447930C7DA" name="X874FAA447930C7DA"></a></p>

<h5>28.6-1 DenseHashTable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DenseHashTable</code>(  )</td><td class="tdright">( function )</td></tr></table></div>
<p>Construct an empty dense hash table. This is the only correct way to construct such a table.</p>

<p><a id="X7FDB74417A19E674" name="X7FDB74417A19E674"></a></p>

<h4>28.7 <span class="Heading">Sparse hash tables</span></h4>

<p>Sparse hash tables are used for hashing sparse sets. Stores keys as an array with fail denoting an empty position, stores values as an array with holes. Uses the result of calling <code class="func">SparseIntKey</code> (<a href="chap28.html#X87FC10AC81E5F6BA"><span class="RefLink">28.5-2</span></a>)) of the key. <code class="code">DefaultHashLength</code> is the default starting hash table length; the table is doubled when it becomes half full.</p>

<p>In sparse hash tables, the integer obtained from the hash key is then transformed to an index position by taking it modulo the length of the hash array.</p>

<p><a id="X8757D3A785290640" name="X8757D3A785290640"></a></p>

<h5>28.7-1 SparseHashTable</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; SparseHashTable</code>( [<var class="Arg">intkeyfun</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Construct an empty sparse hash table. This is the only correct way to construct such a table. If the argument <var class="Arg">intkeyfun</var> is given, this function will be used to obtain numbers for the keys passed to it.</p>

<p><a id="X80FDDF957887B4FC" name="X80FDDF957887B4FC"></a></p>

<h5>28.7-2 DoubleHashArraySize</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DoubleHashArraySize</code>( <var class="Arg">hash</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Double the size of the hash array and rehash all the entries. This will also happen automatically when the hash array is half full.</p>


<div class="chlinkprevnextbot">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap27.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap29.html">[Next Chapter]</a>&nbsp;  </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chap12.html">12</a>  <a href="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chap19.html">19</a>  <a href="chap20.html">20</a>  <a href="chap21.html">21</a>  <a href="chap22.html">22</a>  <a href="chap23.html">23</a>  <a href="chap24.html">24</a>  <a href="chap25.html">25</a>  <a href="chap26.html">26</a>  <a href="chap27.html">27</a>  <a href="chap28.html">28</a>  <a href="chap29.html">29</a>  <a href="chap30.html">30</a>  <a href="chap31.html">31</a>  <a href="chap32.html">32</a>  <a href="chap33.html">33</a>  <a href="chap34.html">34</a>  <a href="chap35.html">35</a>  <a href="chap36.html">36</a>  <a href="chap37.html">37</a>  <a href="chap38.html">38</a>  <a href="chap39.html">39</a>  <a href="chap40.html">40</a>  <a href="chap41.html">41</a>  <a href="chap42.html">42</a>  <a href="chap43.html">43</a>  <a href="chap44.html">44</a>  <a href="chap45.html">45</a>  <a href="chap46.html">46</a>  <a href="chap47.html">47</a>  <a href="chap48.html">48</a>  <a href="chap49.html">49</a>  <a href="chap50.html">50</a>  <a href="chap51.html">51</a>  <a href="chap52.html">52</a>  <a href="chap53.html">53</a>  <a href="chap54.html">54</a>  <a href="chap55.html">55</a>  <a href="chap56.html">56</a>  <a href="chap57.html">57</a>  <a href="chap58.html">58</a>  <a href="chap59.html">59</a>  <a href="chap60.html">60</a>  <a href="chap61.html">61</a>  <a href="chap62.html">62</a>  <a href="chap63.html">63</a>  <a href="chap64.html">64</a>  <a href="chap65.html">65</a>  <a href="chap66.html">66</a>  <a href="chap67.html">67</a>  <a href="chap68.html">68</a>  <a href="chap69.html">69</a>  <a href="chap70.html">70</a>  <a href="chap71.html">71</a>  <a href="chap72.html">72</a>  <a href="chap73.html">73</a>  <a href="chap74.html">74</a>  <a href="chap75.html">75</a>  <a href="chap76.html">76</a>  <a href="chap77.html">77</a>  <a href="chap78.html">78</a>  <a href="chap79.html">79</a>  <a href="chap80.html">80</a>  <a href="chap81.html">81</a>  <a href="chap82.html">82</a>  <a href="chap83.html">83</a>  <a href="chap84.html">84</a>  <a href="chap85.html">85</a>  <a href="chap86.html">86</a>  <a href="chap87.html">87</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>