Quelle  chap7.html   Sprache: HTML

<?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 (datastructures) - Chapter 7: Hashmaps</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="chap7"  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="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="chap6.html">[Previous Chapter]</a>    <a href="chap8.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap7_mj.html">[MathJax on]</a></p>
<p><a id="X7D62ABFF8416C44C" name="X7D62ABFF8416C44C"></a></p>
<div class="ChapSects"><a href="chap7.html#X7D62ABFF8416C44C">7 <span class="Heading">Hashmaps</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X7C5F33687C53BEF0">7.1 <span class="Heading">API</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7C142C0B7AD53629">7.1-1 IsHashMap</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7FC1C1CD87229F1B">7.1-2 HashMap</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X827F974B7B5111CA">7.1-3 Keys</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7B774EB27F2B7148">7.1-4 Values</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X820C9185827968FA">7.1-5 KeyIterator</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7B4D76A47B09C173">7.1-6 ValueIterator</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7F75A43984B05E73">7.1-7 KeyValueIterator</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X818E60167B0B12F7"><code>7.1-8 <span>\</span>[<span>\</span>]</code></a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X8028C04B7895B9CD"><code>7.1-9 <span>\</span>[<span>\</span>]\:\=</code></a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X78DF0E377A70207E"><code>7.1-10 \in</code></a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X84CD9B0B82DC85F7"><code>7.1-11 IsBound<span>\</span>[<span>\</span>]</code></a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X85A876A479D7161D"><code>7.1-12 Unbind<span>\</span>[<span>\</span>]</code></a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X866A89F080CE944A">7.1-13 Size</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X857102527A38A649">7.1-14 IsEmpty</a></span>
</div></div>
</div>

<h3>7 <span class="Heading">Hashmaps</span></h3>

<p>A hash map stores key-value pairs and allows efficient lookup of keys by using a hash function.</p>

<p><strong class="pkg">datastructures</strong> currently provides a reference implementation of hashmaps using a hashtable stored in a plain <strong class="pkg">GAP</strong> list.</p>

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

<h4>7.1 <span class="Heading">API</span></h4>

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

<h5>7.1-1 IsHashMap</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsHashMap</code>( <var class="Arg">arg</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code></p>

<p>Category of hash maps</p>

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

<h5>7.1-2 HashMap</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; HashMap</code>( [<var class="Arg">values</var>][,] [<var class="Arg">hashfunc</var>[, <var class="Arg">eqfunc</var>]][,] [<var class="Arg">capacity</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Create a new hash map. The optional argument <var class="Arg">values</var> must be a list of key-value pairs which will be inserted into the new hashmap in order. The optional argument <var class="Arg">hashfunc</var> must be a hash-function, <var class="Arg">eqfunc</var> must be a binary equality testing function that returns <code class="keyw">true</code> if the two arguments are considered equal, and <code class="keyw">false</code> if they are not. Refer to Chapter <a href="chap6.html#X7AE36B967EB1382B"><span class="RefLink">6</span></a> about the requirements for hashfunctions and equality testers. The optional argument <var class="Arg">capacity</var> determines the initial size of the hashmap.</p>

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

<h5>7.1-3 Keys</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Keys</code>( <var class="Arg">h</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a list</p>

<p>Returns the list of keys of the hashmap <var class="Arg">h</var>.</p>

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

<h5>7.1-4 Values</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Values</code>( <var class="Arg">h</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a list</p>

<p>Returns the set of values stored in the hashmap <var class="Arg">h</var>.</p>

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

<h5>7.1-5 KeyIterator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; KeyIterator</code>( <var class="Arg">h</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: an iterator</p>

<p>Returns an iterator for the keys stored in the hashmap <var class="Arg">h</var>.</p>

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

<h5>7.1-6 ValueIterator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ValueIterator</code>( <var class="Arg">h</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: an iterator</p>

<p>Returns an iterator for the values stored in the hashmap <var class="Arg">h</var>.</p>

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

<h5>7.1-7 KeyValueIterator</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; KeyValueIterator</code>( <var class="Arg">h</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: an iterator</p>

<p>Returns an iterator for key-value-pairs stored in the hashmap <var class="Arg">h</var>.</p>

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

<h5><code>7.1-8 <span>\</span>[<span>\</span>]</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; <span>\</span>[<span>\</span>]</code>( <var class="Arg">hashmap</var>, <var class="Arg">object</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>List-style access for hashmaps.</p>

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

<h5><code>7.1-9 <span>\</span>[<span>\</span>]\:\=</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; <span>\</span>[<span>\</span>]\:\=</code>( <var class="Arg">hashmap</var>, <var class="Arg">object</var>, <var class="Arg">object</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>List-style assignment for hashmaps.</p>

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

<h5><code>7.1-10 \in</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; \in</code>( <var class="Arg">object</var>, <var class="Arg">hashmap</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Test whether a key is stored in the hashmap.</p>

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

<h5><code>7.1-11 IsBound<span>\</span>[<span>\</span>]</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsBound<span>\</span>[<span>\</span>]</code>( <var class="Arg">object</var>, <var class="Arg">hashmap</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Test whether a key is stored in the hashmap.</p>

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

<h5><code>7.1-12 Unbind<span>\</span>[<span>\</span>]</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Unbind<span>\</span>[<span>\</span>]</code>( <var class="Arg">object</var>, <var class="Arg">hashmap</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Delete a key from a hashmap.</p>

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

<h5>7.1-13 Size</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Size</code>( <var class="Arg">hashmap</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Determine the number of keys stored in a hashmap.</p>

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

<h5>7.1-14 IsEmpty</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsEmpty</code>( <var class="Arg">object</var>, <var class="Arg">hashmap</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Test whether a hashmap is empty.</p>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap6.html">[Previous Chapter]</a>    <a href="chap8.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="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

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