All Packages  This Package  Class Hierarchy  Class Search  Index

Class calypso.util.HashtableBase

java.lang.Object
   |
   +----calypso.util.HashtableBase

Object subclass that implements a hash table.

abstract class  HashtableBase
     extends java.lang.Object
     implements java.lang.Cloneable
{
          // Fields 12
     static final int A;
     static final int DEFAULT;
     static final int EMPTY;
     static final int REMOVED;
     int capacity;
     int count;
     Object[] elements;
     int[] hashCodes;
     int indexMask;
     Object[] keys;
     int shift;
     int totalCount;

          // Constructors 2
     HashtableBase();
     HashtableBase(int);

          // Methods 19
     public void clear();
     public Object clone();
     boolean containsElement(Object);
     public int count();
     public Enumeration elements();
     public Vector elementsVector();
     int getElementsArray(Object[]);
     int getKeysArray(Object[]);
     protected void grow();
     private void grow(int);
     int hash(Object);
     public boolean isEmpty();
     public Enumeration keys();
     public Vector keysVector();
     Object put(Object, Object);
     Object removeKey(Object);
     public int size();
     int tableIndexFor(Object, int);
     public String toString();
}

• A

   static final int A

For the multiplicative hash, choose the golden ratio:

     A = ((sqrt(5) - 1) / 2) * (1 << 32)
 

ala Knuth...

• EMPTY

   static final int EMPTY

We use EMPTY and REMOVED as special markers in the table. If some poor object returns one of these two values as their hashCode, it is wacked to DEFAULT.

• REMOVED

   static final int REMOVED

• DEFAULT

   static final int DEFAULT

• count

   int count

• totalCount

   int totalCount

• shift

   int shift

• capacity

   int capacity

• indexMask

   int indexMask

• hashCodes

   int[] hashCodes

• keys

   Object[] keys

• elements

   Object[] elements

• HashtableBase

   HashtableBase() 

Constructs an empty Hashtable. The Hashtable will grow on demand as more elements are added.

• HashtableBase

   HashtableBase(int aInitialCapacity) 

Constructs a Hashtable capable of holding at least initialCapacity elements before needing to grow.

• clone

   public Object clone() 

Creates a shallow copy of the Hashtable. The table itself is cloned, but none of the keys or elements are copied.

Overrides:

clone in class Object

• count

   public int count() 

Returns the number of elements in the Hashtable.

• size

   public int size() 

Returns the number of elements in the Hashtable.

• isEmpty

   public boolean isEmpty() 

Returns true if there are no elements in the Hashtable.

• keys

   public Enumeration keys() 

Returns an Enumeration of the Hashtable's keys.

See Also: elements

• elements

   public Enumeration elements() 

Returns an Enumeration of the Hashtable's elements.

See Also: keys

• keysVector

   public Vector keysVector() 

Returns a Vector containing the Hashtable's keys.

• elementsVector

   public Vector elementsVector() 

Returns a Vector containing the Hashtable's elements.

• getKeysArray

   int getKeysArray(Object[] aArray) 

Returns an Object array containing the Hashtable's keys.

• getElementsArray

   int getElementsArray(Object[] aArray) 

Returns an Object array containing the Hashtable's elements.

• containsElement

   boolean containsElement(Object aElement) 

Returns true if the Hashtable contains the element. This method is slow -- O(n) -- because it must scan the table searching for the element.

• removeKey

   Object removeKey(Object aKey) 

Removes key and the element associated with it from the Hashtable. Returns the element associated with key, or null if key was not present.

• put

   Object put(Object aKey, 
              Object aElement) 

Places the key/element pair in the Hashtable. Neither key nor element may be null. Returns the old element associated with key, or null if the key was not present.

• hash

   int hash(Object aKey) 

We preclude the hashCodes EMPTY and REMOVED because we use them to indicate empty and previously filled slots in the table. All the Hashtable code should go through here and not call hashCode() directly on the key.

• tableIndexFor

   int tableIndexFor(Object aKey, 
                     int aHash) 

Primitive method used internally to find slots in the table. If the key is present in the table, this method will return the index under which it is stored. If the key is not present, then this method will return the index under which it can be put. The caller must look at the hashCode at that index to differentiate between the two possibilities.

• grow

   private void grow(int aCapacity) 

Grows the table to accommodate at least capacity number of elements.

• grow

   protected void grow() 

Grows the table by a factor of 2 (or creates it if necessary). All the REMOVED markers go away and the elements are rehashed into the bigger table.

• clear

   public void clear() 

Removes all keys and elements from the Hashtable.

• toString

   public String toString() 

Returns a string serialization of the Hashtable using the Serializer.

Overrides:

toString in class Object

See Also: Serializer

All Packages  This Package  Class Hierarchy  Class Search  Index