All Packages  Class Hierarchy  This Package  Previous  Next  Index

Interface rpi.goldsd.container.Hashable

public interface Hashable

extends Comparable

Version:

1.0, 3/17/98

Author:

David Goldschmidt

See Also:

Comparable, Table, AssociativeContainer

hash()

Returns an integer representation of the object implementing the Hashable interface.

hash(int)

Generates a valid hash value and will typically call the no-argument hash() method described above.

 public abstract int hash()

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.

Returns:

the hash value representing the corresponding object.

 public abstract int hash(int tableSize)

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:

4. 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 );
   }
 

Returns:

the hash value representing the corresponding object in the inclusive range 0..(tableSize-1).

All Packages  Class Hierarchy  This Package  Previous  Next  Index