package rpi.goldsd.container; /** * The Hashable interface defines two versions of the * hash() method for those objects that are to be stored * in a hashtable or other associative container. Note that this * interface extends the Comparable interface in order to * ensure that the isEqualTo() method is defined for * elements implementing this interface. * * @see Comparable * @see Table * @see AssociativeContainer * @version 1.0, 3/17/98 * @author David Goldschmidt */ public interface Hashable extends Comparable { /** * Returns an integer representation of the object implementing * the Hashable interface. The hash value must be a valid Java * integer, and its generation must adhere to the following rules: *

*

    *
  1. The hash() method must perform in constant time * O(1). *
  2. For a given object, the hash value must not change during * the lifetime of the object. In other words, each call to * the hash() method for a given object must always return * the same integer value. *
  3. Two objects that are deemed equal according to the * isEqualTo() method of the Comparable interface * must have identical hash values. In other words, calls * to the hash() method of the equal objects must produce * the same integer value. *
*

* Ideally, the hash() method should generate hash values that * are fairly random. To take advantage of the performance gains * of associative hashtable structures, the hash values should * be evenly distributed over the size of the hashtable. When * the size of the hashtable is known, the second hash() method * defined next should be used. * @return the hash value representing the corresponding object. */ public int hash(); /** * Generates a valid hash value and will typically call the * no-argument hash() method described above. The single * argument to this version of the hash() method is an integer * value representing the size of the associative hashtable that will * make use of the generated hash value. This value should be * used in the generation of the hash value for the given object. *

* The generation of the hash value must adhere to the same * three requirements detailed in the previous description; * however, requirements (2) and (3) should be adhered to only * for calls to the hash() method in which the tableSize * argument is the same. For example, if this hash() method is * repeatedly called with a tableSize of 101, the resulting hash * values must all be the same. If a tableSize of 203 is then * used, the resulting hash value may be different from that obtained * with a tableSize of 101. *

* A fourth requirement is also expected when using this version * of the hash() method: *

*

    *
  1. The resulting hash value must be in the inclusive range * 0..(tableSize-1). *
*

* If nothing else, this method should be implemented as follows: * 

   *   public int hash( int tableSize )
   *   {
   *     // restrict hash value to 0..(tableSize-1)
   *     return ( Math.abs( hash() ) % tableSize );
   *   }
   *
* @return the hash value representing the corresponding object * in the inclusive range 0..(tableSize-1). */ public int hash( int tableSize ); }