+ * + * To sucessfully store and retrieve objects from a hash table the + * object used as the key must implement the hashCode() and equals() + * methods.
+ * + * This example creates a Cache of numbers. It uses the names of + * the numbers as keys: + *
+ * Cache numbers = new Cache();
+ * numbers.put("one", new Integer(1));
+ * numbers.put("two", new Integer(1));
+ * numbers.put("three", new Integer(1));
+ *
+ * To retrieve a number use:
+ *
+ * Integer n = (Integer)numbers.get("two");
+ * if (n != null) {
+ * System.out.println("two = " + n);
+ * }
+ *
+ *
+ * @see java.lang.Object#hashCode
+ * @see java.lang.Object#equals
+ * @see sun.misc.Ref
+ */
+public
+class Cache extends Dictionary {
+ /**
+ * The hash table data.
+ */
+ private CacheEntry table[];
+
+ /**
+ * The total number of entries in the hash table.
+ */
+ private int count;
+
+ /**
+ * Rehashes the table when count exceeds this threshold.
+ */
+ private int threshold;
+
+ /**
+ * The load factor for the hashtable.
+ */
+ private float loadFactor;
+
+ private void init(int initialCapacity, float loadFactor) {
+ if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
+ throw new IllegalArgumentException();
+ }
+ this.loadFactor = loadFactor;
+ table = new CacheEntry[initialCapacity];
+ threshold = (int) (initialCapacity * loadFactor);
+ }
+
+ /**
+ * Constructs a new, empty Cache with the specified initial
+ * capacity and the specified load factor.
+ * @param initialCapacity the initial number of buckets
+ * @param loadFactor a number between 0.0 and 1.0, it defines
+ * the threshold for rehashing the Cache into
+ * a bigger one.
+ * @exception IllegalArgumentException If the initial capacity
+ * is less than or equal to zero.
+ * @exception IllegalArgumentException If the load factor is
+ * less than or equal to zero.
+ */
+ public Cache (int initialCapacity, float loadFactor) {
+ init(initialCapacity, loadFactor);
+ }
+
+ /**
+ * Constructs a new, empty Cache with the specified initial
+ * capacity.
+ * @param initialCapacity the initial number of buckets
+ */
+ public Cache (int initialCapacity) {
+ init(initialCapacity, 0.75f);
+ }
+
+ /**
+ * Constructs a new, empty Cache. A default capacity and load factor
+ * is used. Note that the Cache will automatically grow when it gets
+ * full.
+ */
+ public Cache () {
+ try {
+ init(101, 0.75f);
+ } catch (IllegalArgumentException ex) {
+ // This should never happen
+ throw new Error("panic");
+ }
+ }
+
+ /**
+ * Returns the number of elements contained within the Cache.
+ */
+ public int size() {
+ return count;
+ }
+
+ /**
+ * Returns true if the Cache contains no elements.
+ */
+ public boolean isEmpty() {
+ return count == 0;
+ }
+
+ /**
+ * Returns an enumeration of the Cache's keys.
+ * @see Cache#elements
+ * @see Enumeration
+ */
+ public synchronized Enumeration keys() {
+ return new CacheEnumerator(table, true);
+ }
+
+ /**
+ * Returns an enumeration of the elements. Use the Enumeration methods
+ * on the returned object to fetch the elements sequentially.
+ * @see Cache#keys
+ * @see Enumeration
+ */
+ public synchronized Enumeration elements() {
+ return new CacheEnumerator(table, false);
+ }
+
+ /**
+ * Gets the object associated with the specified key in the Cache.
+ * @param key the key in the hash table
+ * @returns the element for the key or null if the key
+ * is not defined in the hash table.
+ * @see Cache#put
+ */
+ public synchronized Object get(Object key) {
+ CacheEntry tab[] = table;
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % tab.length;
+ for (CacheEntry e = tab[index]; e != null; e = e.next) {
+ if ((e.hash == hash) && e.key.equals(key)) {
+ return e.check();
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Rehashes the contents of the table into a bigger table.
+ * This is method is called automatically when the Cache's
+ * size exceeds the threshold.
+ */
+ protected void rehash() {
+ int oldCapacity = table.length;
+ CacheEntry oldTable[] = table;
+
+ int newCapacity = oldCapacity * 2 + 1;
+ CacheEntry newTable[] = new CacheEntry[newCapacity];
+
+ threshold = (int) (newCapacity * loadFactor);
+ table = newTable;
+
+ // System.out.println("rehash old=" + oldCapacity + ", new=" +
+ // newCapacity + ", thresh=" + threshold + ", count=" + count);
+
+ for (int i = oldCapacity; i-- > 0;) {
+ for (CacheEntry old = oldTable[i]; old != null;) {
+ CacheEntry e = old;
+ old = old.next;
+ if (e.check() != null) {
+ int index = (e.hash & 0x7FFFFFFF) % newCapacity;
+ e.next = newTable[index];
+ newTable[index] = e;
+ } else
+ count--; /* remove entries that have disappeared */
+ }
+ }
+ }
+
+ /**
+ * Puts the specified element into the Cache, using the specified
+ * key. The element may be retrieved by doing a get() with the same
+ * key. The key and the element cannot be null.
+ * @param key the specified hashtable key
+ * @param value the specified element
+ * @return the old value of the key, or null if it did not have one.
+ * @exception NullPointerException If the value of the specified
+ * element is null.
+ * @see Cache#get
+ */
+ public synchronized Object put(Object key, Object value) {
+ // Make sure the value is not null
+ if (value == null) {
+ throw new NullPointerException();
+ }
+ // Makes sure the key is not already in the cache.
+ CacheEntry tab[] = table;
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % tab.length;
+ CacheEntry ne = null;
+ for (CacheEntry e = tab[index]; e != null; e = e.next) {
+ if ((e.hash == hash) && e.key.equals(key)) {
+ Object old = e.check();
+ e.setThing(value);
+ return old;
+ } else if (e.check() == null)
+ ne = e; /* reuse old flushed value */
+ }
+
+ if (count >= threshold) {
+ // Rehash the table if the threshold is exceeded
+ rehash();
+ return put(key, value);
+ }
+ // Creates the new entry.
+ if (ne == null) {
+ ne = new CacheEntry ();
+ ne.next = tab[index];
+ tab[index] = ne;
+ count++;
+ }
+ ne.hash = hash;
+ ne.key = key;
+ ne.setThing(value);
+ return null;
+ }
+
+ /**
+ * Removes the element corresponding to the key. Does nothing if the
+ * key is not present.
+ * @param key the key that needs to be removed
+ * @return the value of key, or null if the key was not found.
+ */
+ public synchronized Object remove(Object key) {
+ CacheEntry tab[] = table;
+ int hash = key.hashCode();
+ int index = (hash & 0x7FFFFFFF) % tab.length;
+ for (CacheEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
+ if ((e.hash == hash) && e.key.equals(key)) {
+ if (prev != null) {
+ prev.next = e.next;
+ } else {
+ tab[index] = e.next;
+ }
+ count--;
+ return e.check();
+ }
+ }
+ return null;
+ }
+}
+
+/**
+ * A Cache enumerator class. This class should remain opaque
+ * to the client. It will use the Enumeration interface.
+ */
+class CacheEnumerator implements Enumeration {
+ boolean keys;
+ int index;
+ CacheEntry table[];
+ CacheEntry entry;
+
+ CacheEnumerator (CacheEntry table[], boolean keys) {
+ this.table = table;
+ this.keys = keys;
+ this.index = table.length;
+ }
+
+ public boolean hasMoreElements() {
+ while (index >= 0) {
+ while (entry != null)
+ if (entry.check() != null)
+ return true;
+ else
+ entry = entry.next;
+ while (--index >= 0 && (entry = table[index]) == null) ;
+ }
+ return false;
+ }
+
+ public Object nextElement() {
+ while (index >= 0) {
+ if (entry == null)
+ while (--index >= 0 && (entry = table[index]) == null) ;
+ if (entry != null) {
+ CacheEntry e = entry;
+ entry = e.next;
+ if (e.check() != null)
+ return keys ? e.key : e.check();
+ }
+ }
+ throw new NoSuchElementException("CacheEnumerator");
+ }
+
+}