<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>hash tables</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_copy.html">next</a> | <a href="___Basic__List.html">previous</a> | <a href="_operators.html">forward</a> | <a href="_lists_spand_spsequences.html">backward</a> | <a href="___The_sp__Macaulay2_splanguage.html">up</a> | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<div><a href="index.html" title="">Macaulay2Doc</a> > <a href="___The_sp__Macaulay2_splanguage.html" title="">The Macaulay2 language</a> > <a href="_hash_sptables.html" title="">hash tables</a></div>
<hr/>
<div><h1>hash tables</h1>
<div>A hash table is a data structure that can implement a function whose domain is a finite set. An element of the domain is called a key. The hash table stores the key-value pairs in such a way that when presented with a key, the corresponding value can be quickly recovered.<p/>
A dictionary could be implemented as a hash table: the keys would be the words in the language, and the values could be the definitions of the words.<p/>
A phone book could also be implemented as a hash table: the keys would be the names of the subscribers, and the values could be the corresponding phone numbers. (We exclude the possibility of two subscribers with the same name.)<p/>
As an example we implement a phone book.<table class="examples"><tr><td><pre>i1 : book = new HashTable from {
"Joe" => "344-5567",
"Sarah" => "567-4223",
"John" => "322-1456"}
o1 = HashTable{Joe => 344-5567 }
John => 322-1456
Sarah => 567-4223
o1 : HashTable</pre>
</td></tr>
</table>
We use the operator <a href="__sh.html" title="length, or access to elements">#</a> to obtain values from the phone book.<table class="examples"><tr><td><pre>i2 : book#"Sarah"
o2 = 567-4223</pre>
</td></tr>
</table>
The operator <a href="__sh_qu.html" title="check for presence of elements">#?</a> can be used to tell us whether a given key has an entry in the hash table.<table class="examples"><tr><td><pre>i3 : book#?"Mary"
o3 = false</pre>
</td></tr>
</table>
We have implemented the notion of set via hash tables in which every value is the number 1.<table class="examples"><tr><td><pre>i4 : x = set {a,b,c,r,t}
o4 = set {a, b, c, r, t}
o4 : Set</pre>
</td></tr>
<tr><td><pre>i5 : peek x
o5 = Set{a => 1}
b => 1
c => 1
r => 1
t => 1</pre>
</td></tr>
<tr><td><pre>i6 : x#?a
o6 = true</pre>
</td></tr>
<tr><td><pre>i7 : x#?4
o7 = false</pre>
</td></tr>
</table>
There is a type of hash table that is mutable, i.e., a hash table whose entries can be changed. They are changed with assignment statements of the form <tt>x#key=value</tt>.<table class="examples"><tr><td><pre>i8 : x = new MutableHashTable;</pre>
</td></tr>
<tr><td><pre>i9 : x#"Joe" = "344-5567";</pre>
</td></tr>
<tr><td><pre>i10 : x#3 = {a,b,c};</pre>
</td></tr>
<tr><td><pre>i11 : x#{1,2} = 44;</pre>
</td></tr>
<tr><td><pre>i12 : x#3
o12 = {a, b, c}
o12 : List</pre>
</td></tr>
<tr><td><pre>i13 : x#?4
o13 = false</pre>
</td></tr>
</table>
When a mutable hash table is printed, its contents are not displayed. This prevents infinite loops in printing routines.<table class="examples"><tr><td><pre>i14 : x
o14 = MutableHashTable{...3...}
o14 : MutableHashTable</pre>
</td></tr>
</table>
Use <a href="_peek.html" title="examine contents of an object">peek</a> to see the contents of a mutable hash table.<table class="examples"><tr><td><pre>i15 : peek x
o15 = MutableHashTable{{1, 2} => 44 }
3 => {a, b, c}
Joe => 344-5567</pre>
</td></tr>
</table>
A variant of <a href="__sh.html" title="length, or access to elements">#</a> is <a href="_..html" title="access to elements whose key is a symbol">.</a>. It takes only global symbols as keys, and ignores their values.<table class="examples"><tr><td><pre>i16 : p=4;</pre>
</td></tr>
<tr><td><pre>i17 : x.p = 444;</pre>
</td></tr>
<tr><td><pre>i18 : x.p
o18 = 444</pre>
</td></tr>
<tr><td><pre>i19 : x#?4
o19 = false</pre>
</td></tr>
</table>
</div>
<div><h3>Menu</h3>
<h4>functions for manipulating hash tables</h4>
<ul><li><span><a href="_copy.html" title="copy an object">copy</a> -- copy an object</span></li>
<li><span><a href="_hash__Table.html" title="make a hash table">hashTable</a> -- make a hash table</span></li>
<li><span><a href="_keys.html" title="keys used in a hash table">keys</a> -- keys used in a hash table</span></li>
<li><span><a href="_values.html" title="values in a hash table">values</a> -- values in a hash table</span></li>
<li><span><a href="_pairs.html" title="list the pairs in a hash table">pairs</a> -- list the pairs in a hash table</span></li>
<li><span><a href="_mutable.html" title="whether something may be modified">mutable</a> -- whether something may be modified</span></li>
<li><span><a href="_remove.html" title="remove an entry from a hash table">remove</a> -- remove an entry from a hash table</span></li>
<li><span><a href="_apply__Keys.html" title="apply a function to each key in a hash table">applyKeys</a> -- apply a function to each key in a hash table</span></li>
<li><span><a href="_apply__Values.html" title="apply a function to each value">applyValues</a> -- apply a function to each value</span></li>
<li><span><a href="_apply__Pairs.html" title="apply a function to each pair in a hash table">applyPairs</a> -- apply a function to each pair in a hash table</span></li>
<li><span>merge, see <span><a href="_merge_lp__Hash__Table_cm__Hash__Table_cm__Function_rp.html" title="merge hash tables">merge(HashTable,HashTable,Function)</a> -- merge hash tables</span></span></li>
<li><span><a href="_combine.html" title="combine hash tables">combine</a> -- combine hash tables</span></li>
</ul>
<h4>more information</h4>
<ul><li><span><a href="_hashing.html" title="">hashing</a></span></li>
<li><span><a href="___Hash__Table.html" title="the class of all hash tables">HashTable</a> -- the class of all hash tables</span></li>
<li><span><a href="___Mutable__Hash__Table.html" title="the class of all mutable hash tables">MutableHashTable</a> -- the class of all mutable hash tables</span></li>
</ul>
</div>
</div>
</body>
</html>
