Back to index

moin  1.9.0~rc2
IntHashtable.java
Go to the documentation of this file.
00001 // IntHashtable - a Hashtable that uses ints as the keys
00002 // http://www.acme.com/java/software/Acme.IntHashtable.html
00003 //
00004 // This is 90% based on JavaSoft's java.util.Hashtable.
00005 //
00006 // Visit the ACME Labs Java page for up-to-date versions of this and other
00007 // fine Java utilities: http://www.acme.com/java/
00008 
00009 package Acme;
00010 
00011 import java.util.*;
00012 
00014 // <P>
00015 // Use just like java.util.Hashtable, except that the keys must be ints.
00016 // This is much faster than creating a new Integer for each access.
00017 // <P>
00018 // <A HREF="/resources/classes/Acme/IntHashtable.java">Fetch the software.</A><BR>
00019 // <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>
00020 // <P>
00021 // @see java.util.Hashtable
00022 
00023 public class IntHashtable extends Dictionary implements Cloneable
00024     {
00026     private IntHashtableEntry table[];
00027 
00029     private int count;
00030 
00032     private int threshold;
00033 
00035     private float loadFactor;
00036 
00038     // capacity and the specified load factor.
00039     // @param initialCapacity the initial number of buckets
00040     // @param loadFactor a number between 0.0 and 1.0, it defines
00041     //        the threshold for rehashing the hashtable into
00042     //        a bigger one.
00043     // @exception IllegalArgumentException If the initial capacity
00044     // is less than or equal to zero.
00045     // @exception IllegalArgumentException If the load factor is
00046     // less than or equal to zero.
00047     public IntHashtable( int initialCapacity, float loadFactor )
00048        {
00049        if ( initialCapacity <= 0 || loadFactor <= 0.0 )
00050            throw new IllegalArgumentException();
00051        this.loadFactor = loadFactor;
00052        table = new IntHashtableEntry[initialCapacity];
00053        threshold = (int) ( initialCapacity * loadFactor );
00054        }
00055 
00057     // capacity.
00058     // @param initialCapacity the initial number of buckets
00059     public IntHashtable( int initialCapacity )
00060        {
00061        this( initialCapacity, 0.75f );
00062        }
00063 
00065     // is used. Note that the hashtable will automatically grow when it gets
00066     // full.
00067     public IntHashtable()
00068        {
00069        this( 101, 0.75f );
00070        }
00071 
00073     public int size()
00074        {
00075        return count;
00076        }
00077 
00079     public boolean isEmpty()
00080        {
00081        return count == 0;
00082        }
00083 
00085     // @see IntHashtable#elements
00086     public synchronized Enumeration keys()
00087        {
00088        return new IntHashtableEnumerator( table, true );
00089        }
00090 
00092     // on the returned object to fetch the elements sequentially.
00093     // @see IntHashtable#keys
00094     public synchronized Enumeration elements()
00095        {
00096        return new IntHashtableEnumerator( table, false );
00097        }
00098 
00100     // This operation is more expensive than the containsKey() method.
00101     // @param value the value that we are looking for
00102     // @exception NullPointerException If the value being searched 
00103     // for is equal to null.
00104     // @see IntHashtable#containsKey
00105     public synchronized boolean contains( Object value )
00106        {
00107        if ( value == null )
00108            throw new NullPointerException();
00109        IntHashtableEntry tab[] = table;
00110        for ( int i = tab.length ; i-- > 0 ; )
00111            {
00112            for ( IntHashtableEntry e = tab[i] ; e != null ; e = e.next )
00113               {
00114               if ( e.value.equals( value ) )
00115                   return true;
00116               }
00117            }
00118        return false;
00119        }
00120 
00122     // @param key the key that we are looking for
00123     // @see IntHashtable#contains
00124     public synchronized boolean containsKey( int key )
00125        {
00126        IntHashtableEntry tab[] = table;
00127        int hash = key;
00128        int index = ( hash & 0x7FFFFFFF ) % tab.length;
00129        for ( IntHashtableEntry e = tab[index] ; e != null ; e = e.next )
00130            {
00131            if ( e.hash == hash && e.key == key )
00132               return true;
00133            }
00134        return false;
00135        }
00136 
00138     // hashtable.
00139     // @param key the specified key
00140     // @returns the element for the key or null if the key
00141     //               is not defined in the hash table.
00142     // @see IntHashtable#put
00143     public synchronized Object get( int key )
00144        {
00145        IntHashtableEntry tab[] = table;
00146        int hash = key;
00147        int index = ( hash & 0x7FFFFFFF ) % tab.length;
00148        for ( IntHashtableEntry e = tab[index] ; e != null ; e = e.next )
00149            {
00150            if ( e.hash == hash && e.key == key )
00151               return e.value;
00152            }
00153        return null;
00154        }
00155 
00157     // java.util.Dictionary.  The Object must be an Integer.
00158     public Object get( Object okey )
00159        {
00160        if ( ! ( okey instanceof Integer ) )
00161            throw new InternalError( "key is not an Integer" );
00162        Integer ikey = (Integer) okey;
00163        int key = ikey.intValue();
00164        return get( key );
00165        }
00166 
00168     // This method is called automatically when the hashtable's
00169     // size exceeds the threshold.
00170     protected void rehash()
00171        {
00172        int oldCapacity = table.length;
00173        IntHashtableEntry oldTable[] = table;
00174 
00175        int newCapacity = oldCapacity * 2 + 1;
00176        IntHashtableEntry newTable[] = new IntHashtableEntry[newCapacity];
00177 
00178        threshold = (int) ( newCapacity * loadFactor );
00179        table = newTable;
00180 
00181        for ( int i = oldCapacity ; i-- > 0 ; )
00182            {
00183            for ( IntHashtableEntry old = oldTable[i] ; old != null ; )
00184               {
00185               IntHashtableEntry e = old;
00186               old = old.next;
00187 
00188               int index = ( e.hash & 0x7FFFFFFF ) % newCapacity;
00189               e.next = newTable[index];
00190               newTable[index] = e;
00191               }
00192            }
00193        }
00194 
00196     // key.  The element may be retrieved by doing a get() with the same key.
00197     // The key and the element cannot be null. 
00198     // @param key the specified key in the hashtable
00199     // @param value the specified element
00200     // @exception NullPointerException If the value of the element 
00201     // is equal to null.
00202     // @see IntHashtable#get
00203     // @return the old value of the key, or null if it did not have one.
00204     public synchronized Object put( int key, Object value )
00205        {
00206        // Make sure the value is not null.
00207        if ( value == null )
00208            throw new NullPointerException();
00209 
00210        // Makes sure the key is not already in the hashtable.
00211        IntHashtableEntry tab[] = table;
00212        int hash = key;
00213        int index = ( hash & 0x7FFFFFFF ) % tab.length;
00214        for ( IntHashtableEntry e = tab[index] ; e != null ; e = e.next )
00215            {
00216            if ( e.hash == hash && e.key == key )
00217               {
00218               Object old = e.value;
00219               e.value = value;
00220               return old;
00221               }
00222            }
00223 
00224        if ( count >= threshold )
00225            {
00226            // Rehash the table if the threshold is exceeded.
00227            rehash();
00228            return put( key, value );
00229            } 
00230 
00231        // Creates the new entry.
00232        IntHashtableEntry e = new IntHashtableEntry();
00233        e.hash = hash;
00234        e.key = key;
00235        e.value = value;
00236        e.next = tab[index];
00237        tab[index] = e;
00238        ++count;
00239        return null;
00240        }
00241 
00243     // java.util.Dictionary.  The Object must be an Integer.
00244     public Object put( Object okey, Object value )
00245        {
00246        if ( ! ( okey instanceof Integer ) )
00247            throw new InternalError( "key is not an Integer" );
00248        Integer ikey = (Integer) okey;
00249        int key = ikey.intValue();
00250        return put( key, value );
00251        }
00252 
00254     // key is not present.
00255     // @param key the key that needs to be removed
00256     // @return the value of key, or null if the key was not found.
00257     public synchronized Object remove( int key )
00258        {
00259        IntHashtableEntry tab[] = table;
00260        int hash = key;
00261        int index = ( hash & 0x7FFFFFFF ) % tab.length;
00262        for ( IntHashtableEntry e = tab[index], prev = null ; e != null ; prev = e, e = e.next )
00263            {
00264            if ( e.hash == hash && e.key == key )
00265               {
00266               if ( prev != null )
00267                   prev.next = e.next;
00268               else
00269                   tab[index] = e.next;
00270               --count;
00271               return e.value;
00272               }
00273            }
00274        return null;
00275        }
00276 
00278     // java.util.Dictionary.  The Object must be an Integer.
00279     public Object remove( Object okey )
00280        {
00281        if ( ! ( okey instanceof Integer ) )
00282            throw new InternalError( "key is not an Integer" );
00283        Integer ikey = (Integer) okey;
00284        int key = ikey.intValue();
00285        return remove( key );
00286        }
00287 
00289     public synchronized void clear()
00290        {
00291        IntHashtableEntry tab[] = table;
00292        for ( int index = tab.length; --index >= 0; )
00293            tab[index] = null;
00294        count = 0;
00295        }
00296 
00298     // the keys and elements themselves are NOT cloned. This is a
00299     // relatively expensive operation.
00300     public synchronized Object clone()
00301        {
00302        try
00303            {
00304            IntHashtable t = (IntHashtable) super.clone();
00305            t.table = new IntHashtableEntry[table.length];
00306            for ( int i = table.length ; i-- > 0 ; )
00307               t.table[i] = ( table[i] != null ) ?
00308                   (IntHashtableEntry) table[i].clone() : null;
00309            return t;
00310            }
00311        catch ( CloneNotSupportedException e)
00312            {
00313            // This shouldn't happen, since we are Cloneable.
00314            throw new InternalError();
00315            }
00316        }
00317 
00319     public synchronized String toString()
00320        {
00321        int max = size() - 1;
00322        StringBuffer buf = new StringBuffer();
00323        Enumeration k = keys();
00324        Enumeration e = elements();
00325        buf.append( "{" );
00326 
00327        for ( int i = 0; i <= max; ++i )
00328            {
00329            String s1 = k.nextElement().toString();
00330            String s2 = e.nextElement().toString();
00331            buf.append( s1 + "=" + s2 );
00332            if ( i < max )
00333               buf.append( ", " );
00334            }
00335        buf.append( "}" );
00336        return buf.toString();
00337        }
00338     }
00339 
00340 
00341 class IntHashtableEntry
00342     {
00343     int hash;
00344     int key;
00345     Object value;
00346     IntHashtableEntry next;
00347 
00348     protected Object clone()
00349        {
00350        IntHashtableEntry entry = new IntHashtableEntry();
00351        entry.hash = hash;
00352        entry.key = key;
00353        entry.value = value;
00354        entry.next = ( next != null ) ? (IntHashtableEntry) next.clone() : null;
00355        return entry;
00356        }
00357     }
00358 
00359 
00360 class IntHashtableEnumerator implements Enumeration
00361     {
00362     boolean keys;
00363     int index;
00364     IntHashtableEntry table[];
00365     IntHashtableEntry entry;
00366 
00367     IntHashtableEnumerator( IntHashtableEntry table[], boolean keys )
00368        {
00369        this.table = table;
00370        this.keys = keys;
00371        this.index = table.length;
00372        }
00373        
00374     public boolean hasMoreElements()
00375        {
00376        if ( entry != null )
00377            return true;
00378        while ( index-- > 0 )
00379            if ( ( entry = table[index] ) != null )
00380               return true;
00381        return false;
00382        }
00383 
00384     public Object nextElement()
00385        {
00386        if ( entry == null )
00387            while ( ( index-- > 0 ) && ( ( entry = table[index] ) == null ) )
00388               ;
00389        if ( entry != null )
00390            {
00391            IntHashtableEntry e = entry;
00392            entry = e.next;
00393            return keys ? new Integer( e.key ) : e.value;
00394            }
00395        throw new NoSuchElementException( "IntHashtableEnumerator" );
00396        }
00397     }