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