home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / jgl_1_1.exe / src / Hashing.java < prev    next >
Encoding:
Java Source  |  1996-09-10  |  2.6 KB  |  85 lines
  1. // Copyright(c) 1996 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package jgl;
  5.  
  6. /**
  7.  * The Hashing class contains generic hashing algorithms.
  8.  * <p>
  9.  * @version 1.1
  10.  * @author ObjectSpace, Inc.
  11.  */
  12.  
  13. public final class Hashing
  14.   {
  15.   /**
  16.    * Compute an hash value for an ordered container.  
  17.    */
  18.   public static int orderedHash( Container c )
  19.     {
  20.     return orderedHash( c.start(), c.finish() );
  21.     }
  22.  
  23.   /**
  24.    * Compute a hash value for a range of elements in an ordered container
  25.    * Hashing on an ordered container requires that all
  26.    * elements in the container that are used in the hash
  27.    * have the position taken into account.
  28.    * The hashing scheme uses all contained elements if the size 
  29.    * of the range is less than 16.  If the size of the range 
  30.    * is > 16, only representative samples are used to increase
  31.    * performance.  Position is taken into account for each element
  32.    * used in the hash by taking the position modulo 16 plus one
  33.    * and using this result as a divisor on the actual hash code
  34.    * of the element.
  35.    * @param first An iterator positioned at the first element of the sequence.
  36.    * @param last An iterator positioned immediately after the last element of the sequence.
  37.    */
  38.   public static int orderedHash( ForwardIterator first, ForwardIterator last )
  39.     {
  40.     int h = 0;
  41.     int length = first.distance( last );
  42.     int skip = length < 16 ? 1 : length / 16;
  43.     int position = 0;
  44.     while( ( !first.equals( last ) ) && ( first.distance( last ) > 0 ) )
  45.       {
  46.       if( first.get() != null )
  47.         h ^= ( first.get().hashCode() / ((position % 16) + 1) );
  48.       position++;
  49.       first.advance( skip );
  50.       }
  51.     return h;
  52.     }
  53.  
  54.   /**
  55.    * Compute an hash value for an unordered container.  
  56.    */
  57.   public static int unorderedHash( Container c )
  58.     {
  59.     return unorderedHash( c.start(), c.finish() );
  60.     }
  61.  
  62.   /**
  63.    * Compute a hash value for a range of elements in an 
  64.    * uordered container.
  65.    * Hashing on an unordered container requires that all
  66.    * elements in the container are used in the hash.
  67.    * A simple XOR scheme is used over all elements to
  68.    * ensure that equality is maintained over like ranges.
  69.    * @param first An iterator positioned at the first element of the sequence.
  70.    * @param last An iterator positioned immediately after the last element of the sequence.
  71.    */
  72.   public static int unorderedHash( ForwardIterator first, ForwardIterator last )
  73.     {
  74.     int h = 0;
  75.     while( !first.equals( last ) ) 
  76.       {
  77.       if( first.get() != null )
  78.         h ^= first.get().hashCode();
  79.       first.advance();
  80.       }
  81.     return h;
  82.     }
  83.  }
  84.  
  85.