simplehashtable.java

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

			throw new IllegalArgumentException("Illegal maxCapacity: " + 
					maxCapacity);
		}
		
		if (minLoadFactor < 0.0 || Float.isNaN(minLoadFactor)) {
			throw new IllegalArgumentException("Illegal minLoadFactor: " +
					minLoadFactor);
		}
		if (maxLoadFactor <= 0.0 || Float.isNaN(maxLoadFactor)) {
			throw new IllegalArgumentException("Illegal maxLoadFactor: " +
					maxLoadFactor);			
		}
		if (capacityRate <= 1.0 || Float.isNaN(capacityRate)) {
			throw new IllegalArgumentException("Illegal capacityRate: " +
					capacityRate);
		}
		// Initialize all fields.
		this.minCapacity = minCapacity;
		this.maxCapacity = maxCapacity;
		this.minLoadFactor = minLoadFactor;
		this.maxLoadFactor = maxLoadFactor;
		this.capacityRate = capacityRate;
		this.table = new Entry[minCapacity];
		this.count = 0;
		this.minThreshold = (int)(table.length * minLoadFactor);
		this.maxThreshold = (int)(table.length * maxLoadFactor); 
		this.keyIterator = new TableIterator(KEYS);
		this.valueIterator = new TableIterator(VALUES);
		this.entryIterator = new TableIterator(ENTRIES);
	}

	/**
	 * Reorganizes the hashtable to use a new internal bucket array of the
	 * specified capacity. 
	 * This method is called automatically if the number of stored entries
	 * drops below the product of minimum load factor and the current
	 * capacity or if the number of stored entries exceeds the product of
	 * the maximum load factor and the current capacity.
	 * 
	 * @param capacity the new capacity of the internal bucket array.
	 */
	protected void rehash(int capacity){
		Entry[] oldTable; // The old bucket array.
		Entry[] newTable; // The new bucket array.
		int index;        // The entry's index in the new table.
		// Replace the old array with a new one.
		oldTable = this.table;
		this.table = newTable = new Entry[capacity];
		// Compute the new thresholds.
		minThreshold = (int)(capacity * minLoadFactor);
		maxThreshold = (int)(capacity * maxLoadFactor);
		// For each entry in the old table
		for (int i = oldTable.length - 1; i >= 0; i--) {
			for (Entry e = oldTable[i]; e != null; e = oldTable[i]) {
				oldTable[i] = e.next;
				// compute its new index
				index = (e.hash & 0x7FFFFFFF) % capacity;
				// and store it in the new table.
				e.next = newTable[index];
				newTable[index] = e;
			}
		}
	}
	
	/**
	 * Maps the specified <code>key</code> to the specified 
     * <code>value</code> in this hashtable. Both the key and the 
     * value can be <code>null</code>. <p>
     *
     * The value can be retrieved by calling the <code>get</code> method 
     * with a key that is equal to the original key. <p>
     * 
     * The table is rehashed, when the <code>put</code> operation causes
     * the number of entries to exceed the product of the maximum load factor
     * and the current capacity.
     * 
	 * @param key   the hashtable key. 
	 * @param value the value.
	 * @return the previous value of the specified key in this hashtable,
     *         or <code>null</code> if it did not have one.
     * @see    #get(Object)
	 */
	public Object put(Object key, Object value) {
		int hash;     // The key's hash value.
		int index;    // The entry's index specified by the hash value.
		Object old;   // The previous value belonging to the key.
		int capacity; // The new capacity in case of a necessary rehashing.
		// Replace null references.
		key = key == null ? NULL : key;
		value = value == null ? NULL : value;
		// Calculate hash and index.
		hash = key.hashCode();
		index = (hash & 0x7FFFFFFF) % table.length;
		// Does the table already contain the key?
		for (Entry e = table[index] ; e != null ; e = e.next) {
		    if ((e.hash == hash) && e.key.equals(key)) {
		    	old = e.value;
		    	e.value = value;
		    	return (old == NULL ? null : old);
		    }
		}
		// Capacity exceeded and rehashing necessary?
	    if ((count >= maxThreshold) && (table.length < maxCapacity)) {
	    	capacity = (int)(table.length * capacityRate) + 1;
	    	capacity = capacity > maxCapacity ? maxCapacity : capacity;
	    	rehash(capacity);
	    	index = (hash & 0x7FFFFFFF) % capacity;
	    }
	    // Create a new entry and store it.
	    table[index] = new Entry(hash, key, value, table[index]);
	    count++;
	    return null;
	}

	/**
     * Removes the key (and its corresponding value) from this hashtable. 
     * This method does nothing if the key is not in the hashtable. <p>
     * 
     * The table is rehashed, when the <code>remove</code> operation causes
     * the number of entries to drops below the product of the minimum load 
     * factor and the current capacity.
     *
     * @param   key the key that needs to be removed.
     * @return  the value to which the key had been mapped in this hashtable,
     *          or <code>null</code> if the key did not have a mapping.
     */
	public Object remove(Object key) {
		int hash;     // The key's hash value.
		int index;    // The entry's index specified by the hash value.
		int capacity; // The new capacity in case of a necessary rehashing.
		// Replace null references.
		key = key == null ? NULL : key;
		// Compute hash value and index.
		hash = key.hashCode();
		index = (hash & 0x7FFFFFFF) % table.length;
		// Does the table contain the key?
		for (Entry cur=table[index], prev=null; cur!=null; prev=cur, 
		                                                         cur=cur.next) {
			if ((cur.hash == hash) && cur.key.equals(key)) {
				// Remove the entry.
				if (prev != null) {
				    prev.next = cur.next;
				} else {
				    table[index] = cur.next;
				}
				count--;
                // Table underloaded and rehashing necessary?
				if ((count < minThreshold) && (table.length > minCapacity)) {
			    	capacity = (int)(table.length / capacityRate);
			    	capacity = capacity < minCapacity ? minCapacity : capacity;
			    	rehash(capacity);
			    }
				// Return the mapped value. 
				return (cur.value == NULL ? null : cur.value);
			}
		}
		return null;
	}
	
    /**
     * Returns the value to which the specified key is mapped in this hashtable.
     *
     * @param  key a key in the hashtable.
     * @return the value to which the key is mapped in this hashtable or
     *         <code>null</code> if the key is not mapped to any value in
     *         this hashtable.
     * @see    #put(Object, Object)
     */
	public Object get(Object key) {
		int hash;  // The key's hash value.
		int index; // The entry's index specified by the hash value.
		// Replace null references.
		key = key == null ? NULL : key;
		// Calculate hash value and index.
		hash = key.hashCode();
		index = (hash & 0x7FFFFFFF) % table.length;
		// Does the table contain the key?
		for (Entry e = table[index]; e != null; e = e.next) {
			if ((e.hash == hash) && e.key.equals(key)) {
				// Then return its mapped value.
				return (e.value == NULL ? null : e.value);
			}
		}
		return null;
	}
	
	/**
     * Tests if the specified object is a key in this hashtable.
     * 
     * @param   key the object to test.
     * @return  <code>true</code> if and only if the specified object 
     *          is a key in this hashtable, as determined by the 
     *          <tt>equals</tt> method; <code>false</code> otherwise.
     * @see     #contains(Object)
     */
	public boolean containsKey(Object key) {
		int hash;  // The key's hash value.
		int index; // The entry's index specified by the hash value.
		// Replace null references.
		key = key == null ? NULL : key;
		// Compute the hash value and index.
		hash = key.hashCode();
		index = (hash & 0x7FFFFFFF) % table.length;
		// Does the table contain the key.
		for (Entry e = table[index]; e != null; e = e.next) {
			if ((e.hash == hash) && e.key.equals(key)) {
				// Then return true.
				return true;
			}
		}
		return false;
	}

	/**
     * Tests if the specified value is stored in this hashtable.
     * This operation is more expensive than the <code>containsKey</code>
     * method, since it sequentially searches the table. <p>
     *
     * Note that this method is identical in functionality to 
     * <code>containsValue</code>.
     * 
     * @param  value the value to search for.
     * @return <code>true</code> if and only if some key maps to the
     *         <code>value</code> argument in this hashtable as 
     *         determined by the <tt>equals</tt> method;
     *         <code>false</code> otherwise.
     * @see    #containsKey(Object)
     * @see    #containsValue(Object)
     */
	public boolean contains(Object value) {
		// Replace null references.
		value = value == null ? NULL : value;
		// For each entry in the hashtable
		for(int i = table.length - 1; i >= 0; i--) {
			for(Entry e = table[i]; e != null; e = e.next) {
				// compare its value to the specified one.
				if (e.value.equals(value)) {
					return true;
				}
			}
		}
		return false;
	}
	
	/**
     * Tests if the specified value is stored in this hashtable.
     * This operation is more expensive than the <code>containsKey</code>
     * method, since it sequentially searches the table. <p>
     *
     * Note that this method is identical in functionality to 
     * <code>contains</code>.
     * 
     * @param  value the value to search for.
     * @return <code>true</code> if and only if some key maps to the
     *         <code>value</code> argument in this hashtable as 
     *         determined by the <tt>equals</tt> method;
     *         <code>false</code> otherwise.
     * @see    #containsKey(Object)
     * @see    #contains(Object)
     */
	public boolean containsValue(Object value) {
		return contains(value);
	}
	
	/**
	 * Tests if this hashtable stores any entries.
	 * 
	 * @return <code>true<code> if this hashtable stores at least one entry;
	 *         otherwise <code>false</code>.
	 */
	public boolean isEmpty() {
		return count == 0;
	}
	
	/**
	 * Returns the number of entries stored in this hashtable.
	 * 
	 * @return the number of entries stored in this hashtable.
	 */
	public int size() {
		return count;
	}
	
	/**
	 * Clears this hashtable by replacing the internal bucket arry with
	 * an empty new one of minimum capacity.
	 */
	public void clear() {
		table = new Entry[minCapacity];
		minThreshold = (int)(table.length * minLoadFactor);
		maxThreshold = (int)(table.length * maxLoadFactor); 
		count = 0;
	}
	
	/**
	 * Returns a new iterator of the hashtable keys, which is 
	 * <i>not</i> fail-fast. 
	 * Use the iterator methods on the returned object to fetch the keys
     * sequentially.
     * Note that no specific guarantee is made on the order of the elements
     * returned.
     * 
	 * @return an iterator of the hashtable keys.
	 */
	public ResetableIterator keyIterator() {
		return new TableIterator(KEYS);
	}
	
	/**
	 * Returns a new iterator of the hashtable values, which is 
	 * <i>not</i> fail-fast. 
	 * Use the iterator methods on the returned object to fetch the values
     * sequentially.
     * Note that no specific guarantee is made on the order of the elements
     * returned.
     * 
	 * @return an iterator of the hashtable values.
	 */
	public ResetableIterator valueIterator() {
		return new TableIterator(VALUES);
	}
	
	public ResetableIterator entryIterator() {
		return new TableIterator(ENTRIES);
	}
}