一、前言
关于tomcat源码中org.apache.tomcat.util.collections.SimpleHashtable简单hash表实现类,实现java.util.Enumeration遍历接口,详情源码说明部分。
二、源码说明
package org.apache.tomcat.util.collections;@b@@b@import java.util.Enumeration;@b@@b@ @b@public final class SimpleHashtable implements Enumeration{@b@ @b@ private static org.apache.juli.logging.Log log=@b@ org.apache.juli.logging.LogFactory.getLog( SimpleHashtable.class );@b@ @b@ // entries ...@b@ private Entry table[];@b@@b@ // currently enumerated key@b@ private Entry current = null;@b@ private int currentBucket = 0;@b@@b@ // number of elements in hashtable@b@ private int count;@b@ private int threshold;@b@@b@ private static final float loadFactor = 0.75f;@b@@b@@b@ /**@b@ * Constructs a new, empty hashtable with the specified initial @b@ * capacity.@b@ *@b@ * @param initialCapacity the initial capacity of the hashtable.@b@ */@b@ public SimpleHashtable(int initialCapacity) {@b@ if (initialCapacity < 0)@b@ throw new IllegalArgumentException("Illegal Capacity: "+@b@ initialCapacity);@b@ if (initialCapacity==0)@b@ initialCapacity = 1;@b@ table = new Entry[initialCapacity];@b@ threshold = (int)(initialCapacity * loadFactor);@b@ }@b@@b@ /**@b@ * Constructs a new, empty hashtable with a default capacity.@b@ */@b@ public SimpleHashtable() {@b@ this(11);@b@ }@b@@b@ /**@b@ */@b@ public void clear ()@b@ {@b@ count = 0;@b@ currentBucket = 0;@b@ current = null;@b@ for (int i = 0; i < table.length; i++)@b@ table [i] = null;@b@ }@b@@b@ /**@b@ * Returns the number of keys in this hashtable.@b@ *@b@ * @return the number of keys in this hashtable.@b@ */@b@ public int size() {@b@ return count;@b@ }@b@@b@ /**@b@ * Returns an enumeration of the keys in this hashtable.@b@ *@b@ * @return an enumeration of the keys in this hashtable.@b@ * @see Enumeration@b@ */@b@ public Enumeration keys() {@b@ currentBucket = 0;@b@ current = null;@b@ hasMoreElements();@b@ return this;@b@ }@b@@b@ /**@b@ * Used to view this as an enumeration; returns true if there@b@ * are more keys to be enumerated.@b@ */@b@ public boolean hasMoreElements ()@b@ {@b@ if (current != null)@b@ return true;@b@ while (currentBucket < table.length) {@b@ current = table [currentBucket++];@b@ if (current != null)@b@ return true;@b@ }@b@ return false;@b@ }@b@@b@ /**@b@ * Used to view this as an enumeration; returns the next key@b@ * in the enumeration.@b@ */@b@ public Object nextElement ()@b@ {@b@ Object retval;@b@@b@ if (current == null)@b@ throw new IllegalStateException ();@b@ retval = current.key;@b@ current = current.next;@b@ // Advance to the next position ( we may call next after next,@b@ // without hasMore )@b@ hasMoreElements();@b@ return retval;@b@ }@b@@b@@b@ /**@b@ * Returns the value to which the specified key is mapped in this hashtable.@b@ */@b@ public Object getInterned (String key) {@b@ Entry tab[] = table;@b@ int hash = key.hashCode();@b@ int index = (hash & 0x7FFFFFFF) % tab.length;@b@ for (Entry e = tab[index] ; e != null ; e = e.next) {@b@ if ((e.hash == hash) && (e.key == key))@b@ return e.value;@b@ }@b@ return null;@b@ }@b@@b@ /**@b@ * Returns the value to which the specified key is mapped in this@b@ * hashtable ... the key isn't necessarily interned, though.@b@ */@b@ public Object get(String key) {@b@ Entry tab[] = table;@b@ int hash = key.hashCode();@b@ int index = (hash & 0x7FFFFFFF) % tab.length;@b@ for (Entry e = tab[index] ; e != null ; e = e.next) {@b@ if ((e.hash == hash) && e.key.equals(key))@b@ return e.value;@b@ }@b@ return null;@b@ }@b@@b@ /**@b@ * Increases the capacity of and internally reorganizes this @b@ * hashtable, in order to accommodate and access its entries more @b@ * efficiently. This method is called automatically when the @b@ * number of keys in the hashtable exceeds this hashtable's capacity @b@ * and load factor. @b@ */@b@ private void rehash() {@b@ int oldCapacity = table.length;@b@ Entry oldMap[] = table;@b@@b@ int newCapacity = oldCapacity * 2 + 1;@b@ Entry newMap[] = new Entry[newCapacity];@b@@b@ threshold = (int)(newCapacity * loadFactor);@b@ table = newMap;@b@@b@ /*@b@ System.out.pr intln("rehash old=" + oldCapacity@b@ + ", new=" + newCapacity@b@ + ", thresh=" + threshold@b@ + ", count=" + count);@b@ */@b@@b@ for (int i = oldCapacity ; i-- > 0 ;) {@b@ for (Entry old = oldMap[i] ; old != null ; ) {@b@ Entry e = old;@b@ old = old.next;@b@@b@ int index = (e.hash & 0x7FFFFFFF) % newCapacity;@b@ e.next = newMap[index];@b@ newMap[index] = e;@b@ }@b@ }@b@ }@b@@b@ /**@b@ * Maps the specified <code>key</code> to the specified @b@ * <code>value</code> in this hashtable. Neither the key nor the @b@ * value can be <code>null</code>. @b@ *@b@ * <P>The value can be retrieved by calling the <code>get</code> method @b@ * with a key that is equal to the original key. @b@ */@b@ public Object put(Object key, Object value) {@b@ // Make sure the value is not null@b@ if (value == null) {@b@ throw new NullPointerException();@b@ }@b@@b@ // Makes sure the key is not already in the hashtable.@b@ Entry tab[] = table;@b@ int hash = key.hashCode();@b@ int index = (hash & 0x7FFFFFFF) % tab.length;@b@ for (Entry e = tab[index] ; e != null ; e = e.next) {@b@ // if ((e.hash == hash) && e.key.equals(key)) {@b@ if ((e.hash == hash) && (e.key == key)) {@b@ Object old = e.value;@b@ e.value = value;@b@ return old;@b@ }@b@ }@b@@b@ if (count >= threshold) {@b@ // Rehash the table if the threshold is exceeded@b@ rehash();@b@@b@ tab = table;@b@ index = (hash & 0x7FFFFFFF) % tab.length;@b@ } @b@@b@ // Creates the new entry.@b@ Entry e = new Entry(hash, key, value, tab[index]);@b@ tab[index] = e;@b@ count++;@b@ return null;@b@ }@b@@b@ public Object remove(Object key) {@b@ Entry tab[] = table;@b@ Entry prev=null;@b@ int hash = key.hashCode();@b@ int index = (hash & 0x7FFFFFFF) % tab.length;@b@ if( dL > 0 ) d("Idx " + index + " " + tab[index] );@b@ for (Entry e = tab[index] ; e != null ; prev=e, e = e.next) {@b@ if( dL > 0 ) d("> " + prev + " " + e.next + " " + e + " " + e.key);@b@ if ((e.hash == hash) && e.key.equals(key)) {@b@ if( prev!=null ) {@b@ prev.next=e.next;@b@ } else {@b@ tab[index]=e.next;@b@ }@b@ if( dL > 0 ) d("Removing from list " + tab[index] + " " + prev +@b@ " " + e.value);@b@ count--;@b@ Object res=e.value;@b@ e.value=null;@b@ return res;@b@ }@b@ }@b@ return null;@b@ }@b@@b@ /**@b@ * Hashtable collision list.@b@ */@b@ private static class Entry {@b@ int hash;@b@ Object key;@b@ Object value;@b@ Entry next;@b@@b@ protected Entry(int hash, Object key, Object value, Entry next) {@b@ this.hash = hash;@b@ this.key = key;@b@ this.value = value;@b@ this.next = next;@b@ }@b@ }@b@@b@ private static final int dL=0;@b@ private void d(String s ) {@b@ if (log.isDebugEnabled())@b@ log.debug( "SimpleHashtable: " + s );@b@ }@b@}