html/suif1_97.html

   1 <HTML>
   2 <HEAD>
   3 <!-- This HTML file has been created by texi2html 1.54
   4      from suif1.texi on 28 April 1999 -->
   5
   6 <TITLE>The SUIF Version 1 Library - Hash Tables</TITLE>
   7 <link href="suif1_98.html" rel=Next>
   8 <link href="suif1_96.html" rel=Previous>
   9 <link href="suif1_toc.html" rel=ToC>
  10
  11 </HEAD>
  12 <BODY>
  13 <p>Go to the <A HREF="suif1_1.html">first</A>, <A HREF="suif1_96.html">previous</A>, <A HREF="suif1_98.html">next</A>, <A HREF="suif1_113.html">last</A> section, <A HREF="suif1_toc.html">table of contents</A>.
  14 <P><HR><P>
  15
  16
  17 <H2><A NAME="SEC97" HREF="suif1_toc.html#TOC97">Hash Tables</A></H2>
  18 <P>
  19 <A NAME="IDX683"></A>
  20
  21 </P>
  22 <P>
  23 <A NAME="IDX684"></A>
  24 <A NAME="IDX685"></A>
  25 <A NAME="IDX686"></A>
  26 SUIF hash tables are implemented by the <CODE>hash_table</CODE> class in the
  27 files <TT>`hash.h'</TT> and <TT>`hash.cc'</TT>.  Each hash table is a fixed-size
  28 array of <CODE>hash_chain</CODE> buckets.  A <CODE>hash_chain</CODE> is just a
  29 move-to-front list.  See section <A HREF="suif1_93.html#SEC93">Move-to-front Lists</A>.  The entries in a hash
  30 table are derived from the <CODE>hash_e</CODE> class, which contains a single
  31 unsigned value used as the signature.
  32
  33 </P>
  34 <P>
  35 If you wish to store pointers in a hash table, you can use the
  36 <CODE>hash_e</CODE> class directly (assuming that the pointers can fit into
  37 the unsigned signature fields).  Otherwise, you need to create a derived
  38 <CODE>hash_e</CODE> class.  The only other thing needed is a function to
  39 compare two <CODE>hash_e</CODE> entries to determine if they are equal.  You
  40 can then create a new <CODE>hash_table</CODE> object.  Even if you are using a
  41 derived <CODE>hash_e</CODE> class, it may be easier to just type cast the
  42 pointers than to derive a new <CODE>hash_table</CODE> class that includes the
  43 correct type casts.
  44
  45 </P>
  46 <P>
  47 <A NAME="IDX687"></A>
  48 <A NAME="IDX688"></A>
  49 The hash table <CODE>enter</CODE> method tries to add a new entry.  If the
  50 entry was already in the table it returns <CODE>TRUE</CODE> and does not enter
  51 a duplicate; otherwise, it adds the new entry and returns <CODE>FALSE</CODE>.
  52 The <CODE>lookup</CODE> method checks to see if a particular entry is in the
  53 table.  If so, it returns the pointer to the entry.
  54
  55 </P>
  56
  57 <P><HR><P>
  58 <p>Go to the <A HREF="suif1_1.html">first</A>, <A HREF="suif1_96.html">previous</A>, <A HREF="suif1_98.html">next</A>, <A HREF="suif1_113.html">last</A> section, <A HREF="suif1_toc.html">table of contents</A>.
  59 </BODY>
  60 </HTML>