/usr/share/gap/doc/ref/chap28.html is in gap-doc 4r7p9-1.
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"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap27.html">[Previous Chapter]</a> <a href="chap29.html">[Next Chapter]</a> </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"> </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"> </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"> </span><a href="chap28.html#X7E78E3E983A5C895">28.2-1 NewDictionary</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap28.html#X865D5BE1830A448D">28.3-1 DictionaryByPosition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap28.html#X87F7247E784021C2">28.3-2 IsDictionary</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap28.html#X7D776BC67ABDDCCE">28.3-3 IsLookupDictionary</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap28.html#X86C4F0507AD98B8A">28.3-4 AddDictionary</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap28.html#X808C885D7E267285">28.3-5 KnowsDictionary</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap28.html#X863706BF847A47EB">28.3-6 LookupDictionary</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </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"> </span><a href="chap28.html#X79DEEB5783513838">28.5-1 DenseIntKey</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap28.html#X87FC10AC81E5F6BA">28.5-2 SparseIntKey</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap28.html#X874FAA447930C7DA">28.6-1 DenseHashTable</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap28.html#X8757D3A785290640">28.7-1 SparseHashTable</a></span>
<span class="ContSS"><br /><span class="nocss"> </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></span> <span class="GAPinput">d:=NewDictionary((1,2,3),true);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AddDictionary(d,(1,2),1);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AddDictionary(d,(5,6),9);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AddDictionary(d,(4,7),2);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">LookupDictionary(d,(5,6));</span>
9
<span class="GAPprompt">gap></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></span> <span class="GAPinput">RepresentationsOfObject(d);</span>
[ "IsComponentObjectRep", "IsDictionaryDefaultRep",
"IsListDictionary", "IsListLookupDictionary", "IsSortDictionary",
"IsSortLookupDictionary" ]
<span class="GAPprompt">gap></span> <span class="GAPinput">d:=NewDictionary((1,2,3),true,Elements(SymmetricGroup(5)));;</span>
<span class="GAPprompt">gap></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></span> <span class="GAPinput">v:=GF(2)^7;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">d:=NewDictionary(Zero(v),true);; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RepresentationsOfObject(d);</span>
[ "IsComponentObjectRep", "IsDictionaryDefaultRep",
"IsListDictionary", "IsListLookupDictionary", "IsSortDictionary",
"IsSortLookupDictionary" ]
<span class="GAPprompt">gap></span> <span class="GAPinput">d:=NewDictionary(Zero(v),true,v);;</span>
<span class="GAPprompt">gap></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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap27.html">[Previous Chapter]</a> <a href="chap29.html">[Next Chapter]</a> </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>
|