Quelle  chap6.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 6: Hash Functions</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="chap6"  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="chap5.html">[Previous Chapter]</a>    <a href="chap7.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap6_mj.html">[MathJax on]</a></p>
<p><a id="X7AE36B967EB1382B" name="X7AE36B967EB1382B"></a></p>
<div class="ChapSects"><a href="chap6.html#X7AE36B967EB1382B">6 <span class="Heading">Hash Functions</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7DFB63A97E67C0A1">6.1 <span class="Heading">Introduction</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7A441DD97E6C78A6">6.2 <span class="Heading">Hash Functions for Basic Types</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X85E86FF080A3A37A">6.2-1 HashBasic</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X78424208807F992D">6.3 <span class="Heading">Hash Functions for Permutation Groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X848AD86F8089106F">6.3-1 Hash_PermGroup_Fast</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X86FFE7A07E784C24">6.3-2 Hash_PermGroup_Complete</a></span>
</div></div>
</div>

<h3>6 <span class="Heading">Hash Functions</span></h3>

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

<h4>6.1 <span class="Heading">Introduction</span></h4>

<p>A hash function in <strong class="pkg">datastructures</strong> is a function <span class="SimpleMath">H</span> which maps a value <span class="SimpleMath">X</span> to a small integer (where a small integer is an integer in the range <code class="code">[-2^28..2^28-1]</code> on a 32-bit system, and <code class="code">[-2^60..2^60-1]</code> on a 64-bit system), under the requirement that if <span class="SimpleMath">X=Y</span>, then <span class="SimpleMath">H(X)=H(Y)</span>.</p>

<p>A variety of hash functions is provided by <strong class="pkg">datastructures</strong>, with different behaviours. A bad choice of hash function can lead to serious performance problems.</p>

<p><strong class="pkg">datastructures</strong> does not guarantee consistency of hash values across release or <strong class="pkg">GAP</strong> sessions.</p>

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

<h4>6.2 <span class="Heading">Hash Functions for Basic Types</span></h4>

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

<h5>6.2-1 HashBasic</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; HashBasic</code>( <var class="Arg">obj...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a small integer</p>

<p>Hashes any values built inductively from</p>


<ul>
<li><p>built-in types, namely integers, booleans, permutations, transformations, partial permutations, and</p>

</li>
<li><p>constructors for lists and records.</p>

</li>
</ul>
<p>This function is variadic, treating more than one argument as equivalent to a list containing the arguments, that is <code class="code">HashBasic(x,y,z) = HashBasic([x,y,z])</code>.</p>

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

<h4>6.3 <span class="Heading">Hash Functions for Permutation Groups</span></h4>

<p><strong class="pkg">datastructures</strong> provides two hash functions for permutation groups; <code class="func">Hash_PermGroup_Fast</code> (<a href="chap6.html#X848AD86F8089106F"><span class="RefLink">6.3-1</span></a>) is the faster one, with higher likelihood of collisions and <code class="func">Hash_PermGroup_Complete</code> (<a href="chap6.html#X86FFE7A07E784C24"><span class="RefLink">6.3-2</span></a>) is slower but provides a lower likelihood of collisions.</p>

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

<h5>6.3-1 Hash_PermGroup_Fast</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Hash_PermGroup_Fast</code>( <var class="Arg">group</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a small integer</p>

<p><code class="func">Hash_PermGroup_Fast</code> is faster than <code class="func">Hash_PermGroup_Complete</code> (<a href="chap6.html#X86FFE7A07E784C24"><span class="RefLink">6.3-2</span></a>), but will return the same value for groups with the same size, orbits and degree of transitivity.</p>

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

<h5>6.3-2 Hash_PermGroup_Complete</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Hash_PermGroup_Complete</code>( <var class="Arg">group</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a small integer</p>

<p><code class="func">Hash_PermGroup_Complete</code> is slower than <code class="func">Hash_PermGroup_Fast</code> (<a href="chap6.html#X848AD86F8089106F"><span class="RefLink">6.3-1</span></a>), but is extremely unlikely to return the same hash for two different groups.</p>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap5.html">[Previous Chapter]</a>    <a href="chap7.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>