simplehashtable.java

发布/订阅系统路由重配算法,可应用于ad hoc环境

/*
 * project: RebecaSim
 * package: util
 * file:    SimpleHashtable.java
 * version: 0.1
 * date:    03.04.2005
 * 
 * This software is part of the diploma thesis "Ein adaptives Brokernetz 
 * für Publish/Subscribe Systeme".
 */
package util;

import java.util.*;

/**
 * This class provides a simple, open and unsynchronized hashtable, which 
 * implements the most important methods known from the 
 * <code>java.util.Hashtable</code> class. <p>
 * 
 * Despite the more comprehensive functionality of the 
 * <code>java.util.Hashtable</code> the <code>SimpleHashtable</code>
 * has also its advantages. 
 * It permits <cod>null</code> objects both as keys and values and
 * provides more control of the dynamic memory allocation when increasing 
 * or decreasing its capacity of the internal <i>bucket</i> array.
 * (See the description of the object constructors for more information.)
 * The two default <code>ResetableIterator</code>s can be used to access
 * the keys or values sequentially, without the instantiation of any
 * new object, which is especially useful in <code>finalize</code> methods,
 * where memory is short. 
 *
 * @version 0.1 03.04.2005
 * @author  Helge Parzyjegle
 * @see     java.util.Hashtable
 */
public class SimpleHashtable {
	
	/**
	 * An entry of the hashtable collision list encapsulating a key and its
	 * belonging value. 
	 */
	private static class Entry implements Map.Entry{

		/** The <code>key</code>'s cached hash value. */
		int hash;
		
		/** The key. */
		Object key;
		
		/** The belonging value. */
		Object value;
		
		/** 
		 * The next entry in the collision list or <code>null</code>, 
		 * if this is the last one.
		 */
		Entry next;
		
		/**
		 * Creates a new collision list entry and sets its fields to the
		 * values specified by the provided params.
		 * 
		 * @param hash  the <code>key</code>'s hash value.
		 * @param key   the key itself.
		 * @param value the value belonging to the key.
		 * @param next  the next entry in the collision list or 
		 *              <code>null</code>, if this is the last one.
		 */
		protected Entry(int hash, Object key, Object value, Entry next) {
		    this.hash = hash;
		    this.key = key;
		    this.value = value;
		    this.next = next;
		}
		
		public Object getKey() {
			return key;
		}
		
		public Object getValue() {
			return value;
		}
		
		public Object setValue(Object value) {
			Object oldValue;
			oldValue = this.value;
			this.value = value;
			return oldValue;
		}
		
	}

	/**
	 * A hashtable iterator class implementing the 
	 * <code>ResetableIterator</code> interface. 
	 * Note that this iterator is <i>not</i> fail-fast.
	 */
	private class TableIterator implements ResetableIterator {

		/**
		 * The iterator's type: <code>KEYS</code> or <code>VALUES</code>.
		 * So the iterator's <code>next</code> method will return
		 * the hashtable's keys or values, respectively.
		 */
		int type;

		/** The hashtable's index of the iterator's current object. */ 
		int index;
		
		/** The hashtable's entry of the iterator's current object. */
		Entry entry;
		
		/**
		 * Constructs a new reseted iterator for this 
		 * <code>SimpleHashtable</code>, which returns either its keys
		 * or its values.
		 * 
		 * @param type the iterator's type. (<code>KEYS</code> lets the
		 *             iterator return the hashtable's keys, 
		 *             <code>VALUES</code> its values instead.)
		 */
		TableIterator(int type) {
			this.type = type;
			this.index = 0;
			this.entry = null;
		}
		
		/**
		 * Returns <code>true</code> if the iterator has more elements.
		 * 
		 * @return <code>true</code> if the iterator has more elements.
		 */
		public boolean hasNext() {
			while (entry == null && index < table.length) {
				entry = table[index++];
			}
			return entry != null;
		}
		
		/**
		 * Returns the next element in the iteration.
		 * 
		 * @return the next element in the iteration.
		 * @throws NoSuchElementException if the iteration has no more elements.
		 */
		public Object next() {
			Object ret; // the next element in the iteration.
			while (entry == null && index < table.length) {
				entry = table[index++];
			}
			if (entry != null) {
				if (type == KEYS) {
					ret = entry.key;
				}
				else if (type == VALUES) {
					ret = entry.value;
				}
				else {
					ret = entry;
				}
				entry = entry.next;
				return ret;
			}
			throw new NoSuchElementException();
		}
		
		/**
		 * Method is unsupported by this iterator.
		 * 
		 * @throws UnsupportedOperationException when method is called.
		 */
		public void remove() {
			throw new UnsupportedOperationException();
		}
		
		/**
		 * Resets the iterator to its first element.
		 */
		public void reset() {
			this.entry = null;
			this.index = 0;
		}
	}
	
	/** 
	 * Constant specifying the iterator's type. A <code>TableIterator</code>
	 * constructed with the <code>KEYS</code> constant will return the
	 * hashtable's keys.
	 */
	private static final int KEYS = 0;
	
	/** 
	 * Constant specifying the iterator's type. A <code>TableIterator</code>
	 * constructed with the <code>VALUES</code> constant will return the
	 * hashtable's values.
	 */
	private static final int VALUES = 1;
	
	
	private static final int ENTRIES = 2;
	
	
	/** Constant used to store <code>null</code> objects in the hashtable. */
	private static final Object NULL = new Object();

	/** The hashtable's default iterator returning the key objects. */	
	public final ResetableIterator keyIterator;
	
	/** The hashtable's default iterator returning the value objects. */	
	public final ResetableIterator valueIterator;
	
	public final ResetableIterator entryIterator;
	
	/** The bucket array's minimum size. */
	private int minCapacity;
	
	/** The bucket array's maximum size. */
	private int maxCapacity;
	
	/** The hashtable's load factor indicating when the table is underloaded. */
	private float minLoadFactor;
	
	/** The hashtable's load factor indicating when the table is overloaded. */
	private float maxLoadFactor;
	
	/** 
	 * The rate by which the bucket array growths when the table is rehashed
	 * caused by overload. In the underload case the bucket array shrinks
	 * by this rate. 
	 */
	private float capacityRate;

	/** The hashtable's bucket array containing its data entries. */
	private Entry[] table;

	/** The total number of entries in the hashtable. */
	private int count;
	
	/** 
	 * The table's bucket array is reduced when the table's count drops 
	 * below this threshold. This includes a rehash operation.
	 * The field's value is computed by (int)(table.length * minLoadFactor).
	 */
	private int minThreshold;

	/** 
	 * The table's bucket array is extended when the table's count exceeds 
	 * this threshold. This includes a rehash operation.
	 * The field's value is computed by (int)(table.length * maxLoadFactor).
	 */
	private int maxThreshold;
	
	/**
	 * Constructs a new <code>SimpleHashtable</code> object with the
	 * following default parameters:
	 * <code>minCapacity = 10</code>,
	 * <code>maxCapacity = Integer.MAX_VALUE</code>,
	 * <code>minLoadFactor = 0.0f</code>,
	 * <code>maxLoadFactor = 0.75f</code> and
	 * <code>capacityRate = 2.0f</code>.
	 */
	public SimpleHashtable() {
		this(10,Integer.MAX_VALUE,0.0f,0.75f,2.0f);
	}
	
	/**
	 * Constructs a new <code>SimpleHashtable</code> object with the
	 * specified and following default parameters:
	 * <code>maxCapacity = Integer.MAX_VALUE</code>,
	 * <code>minLoadFactor = 0.0f</code> and
	 * <code>capacityRate = 2.0f</code>.
	 * 
	 * @param  minCapacity   the minimum capacity of the internal bucket array.
	 * @param  maxLoadFactor the maximum tolarated load factor. 
	 * @throws IllegalArgumentException if <code>minCapacity</code> is
	 *         less than <code>1</code> or if <code>maxLoadFactor</code>
	 *         is equal or less than <code>0.0f</code>.
	 */
	public SimpleHashtable(int minCapacity, float maxLoadFactor) {
		this(minCapacity,Integer.MAX_VALUE,0.0f,maxLoadFactor,2.0f);
	}
	
	/**
	 * Constructs a new empty <code>SimpleHashtable</code> object with
	 * the specified parameters. <p>
	 * 
	 * <code>minCapacity</code> and <code>maxCapacity</code> limit the
	 * size of the used internal bucket array.
	 * Note that a too high <code>minCapacity</code> wastes space, while
	 * a too low <code>maxCapacity</code> leads to hash collisions and
	 * decreases the performance. <p>
	 * 
	 * <code>minLoadFactor</code> and <code>maxLoadFactor</code> control
	 * when the internal bucket array's capacity is adapted and the table 
	 * is rehashed.
	 * When the total number of stored entries in the hashtable drops
	 * below the product of the <code>minLoadFactor</code> and the current
	 * capacity, the capacity is reduced by <code>capacityRate</code>.
	 * When the total number of stored entries in the hashtable exceeds
	 * the product of the <code>maxLoadFactor</code> and the current
	 * capacity, the capacity is extended by <code>capacityRate</code>.
	 * Note that the capacity will never fall short of 
	 * <code>minCapacity</code> or exceed <code>maxCapacity</code>. <p>
	 * 
	 * Note also that the constructor will check all parameters whether
	 * they are valid. It is not checked if their combination makes sense. 
	 * 
	 * @param  minCapacity   the minimum capacity of the internal bucket array.
	 * @param  maxCapacity   the maximum capacity of the internal bucker array.
	 * @param  minLoadFactor the minimum tolerated load factor.
	 * @param  maxLoadFactor the maximum tolarated load factor. 
	 * @param  capacityRate  the capacity adaption rate.
	 * @throws IllegalArgumentException if <code>minCapacity</code> or
	 *         <code>maxCapacity</code> are less than <code>1</code>,
	 *         if <code>minLoadFactor</code> is less than <code>0.0f</code>,
	 *         if <code>maxLoadFactor</code> is equal or less than
	 *         <code>0.0f</code> or if <code>capacityRate</code> is 
	 *         equal or less than <code>1.0f</code>. 
	 */
	public SimpleHashtable(int minCapacity, int maxCapacity,
						   float minLoadFactor, float maxLoadFactor,
						   float capacityRate) {
		// Check params.
		if (minCapacity < 1) {
			throw new IllegalArgumentException("Illegal minCapacity: " +
					minCapacity);
		}
		if (maxCapacity < 1) {