inthashmap.java

Jodd是一个开源的公用Java基础类库

package jodd.util;

import java.io.IOException;
import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * A Map that accepts int or Integer keys only. The implementation is based on
 * <code>java.util.HashMap</code>. IntHashMap is about 25% faster.
 *
 * @see java.util.HashMap
 */

public class IntHashMap extends AbstractMap implements Map, Cloneable, Serializable {

	/**
	 * The hash table data.
	 */
	private transient Entry table[];

	/**
	 * The total number of mappings in the hash table.
	 */
	private transient int count;

	/**
	 * The table is rehashed when its size exceeds this threshold. (The value of
	 * this field is (int)(capacity * loadFactor).)
	 */
	private int threshold;

	/**
	 * The load factor for the hashtable.
	 */
	private float loadFactor;

	/**
	 * The number of times this IntHashMap has been structurally modified
	 * Structural modifications are those that change the number of mappings in
	 * the IntHashMap or otherwise modify its internal structure (e.g., rehash).
	 * This field is used to make iterators on Collection-views of the IntHashMap
	 * fail-fast.
	 */
	private transient int modCount = 0;

	/**
	 * Constructs a new, empty map with the specified initial
	 * capacity and the specified load factor.
	 *
	 * @param initialCapacity
	 *                   the initial capacity of the IntHashMap.
	 * @param loadFactor the load factor of the IntHashMap
	 *
	 * @throws IllegalArgumentException
	 *                if the initial capacity is less
	 *                than zero, or if the load factor is nonpositive.
	 */
	public IntHashMap(int initialCapacity, float loadFactor) {
		if (initialCapacity < 0) {
			throw new IllegalArgumentException("Illegal Initial Capacity: "+ initialCapacity);
		}
		if (loadFactor <= 0) {
			throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor);
		}
		if (initialCapacity == 0) {
			initialCapacity = 1;
		}
		this.loadFactor = loadFactor;
		table = new Entry[initialCapacity];
		threshold = (int)(initialCapacity * loadFactor);
	}

	/**
	 * Constructs a new, empty map with the specified initial capacity
	 * and default load factor, which is 0.75.
	 *
	 * @param initialCapacity
	 *               the initial capacity of the IntHashMap.
	 *
	 * @throws IllegalArgumentException
	 *                if the initial capacity is less
	 *                than zero.
	 */
	public IntHashMap(int initialCapacity) {
		this(initialCapacity, 0.75f);
	}

	/**
	 * Constructs a new, empty map with a default capacity and load
	 * factor, which is 0.75.
	 */
	public IntHashMap() {
		this(101, 0.75f);
	}

	/**
	 * Constructs a new map with the same mappings as the given map.  The
	 * map is created with a capacity of twice the number of mappings in
	 * the given map or 11 (whichever is greater), and a default load factor,
	 * which is 0.75.
	 *
	 * @param t
	 */
	public IntHashMap(Map t) {
		this(Math.max(2 * t.size(), 11), 0.75f);
		putAll(t);
	}

	/**
	 * Returns the number of key-value mappings in this map.
	 *
	 * @return the number of key-value mappings in this map.
	 */
	public int size() {
		return count;
	}

	/**
	 * Returns <code>true</code> if this map contains no key-value mappings.
	 *
	 * @return <code>true</code> if this map contains no key-value mappings.
	 */
	public boolean isEmpty() {
		return count == 0;
	}

	/**
	 * Returns <code>true</code> if this map maps one or more keys to the
	 * specified value.
	 *
	 * @param value  value whose presence in this map is to be tested.
	 *
	 * @return <code>true</code> if this map maps one or more keys to the
	 *         specified value.
	 */
	public boolean containsValue(Object value) {
		Entry tab[] = table;
		if (value == null) {
			for (int i = tab.length; i-- > 0 ;) {
				for (Entry e = tab[i] ; e != null ; e = e.next) {
					if (e.value == null) {
						return true;
					}
				}
			}
		} else {
			for (int i = tab.length; i-- > 0 ;) {
				for (Entry e = tab[i]; e != null; e = e.next) {
					if (value.equals(e.value)) {
						return true;
					}
				}
			}
		}
		return false;
	}

	/**
	 * Returns <code>true</code> if this map contains a mapping for the specified
	 * key.
	 *
	 * @param key    key whose presence in this Map is to be tested.
	 *
	 * @return <code>true</code> if this map contains a mapping for the specified
	 *         key.
	 */
	public boolean containsKey(Object key) {
		if (key instanceof Number) {
			return containsKey( ((Number)key).intValue() );
		} else {
			return false;
		}
	}

	/**
	 * Returns <code>true</code> if this map contains a mapping for the specified
	 * key.
	 *
	 * @param key    key whose presence in this Map is to be tested.
	 *
	 * @return <code>true</code> if this map contains a mapping for the specified
	 *         key.
	 */
	public boolean containsKey(int key) {
		Entry tab[] = table;

		int index = (key & 0x7FFFFFFF) % tab.length;
		for (Entry e = tab[index]; e != null; e = e.next) {
			if (e.key == key) {
				return true;
			}
		}

		return false;
	}

	/**
	 * Returns the value to which this map maps the specified key. Returns
	 * <code>null</code> if the map contains no mapping for this key. A return
	 * value of <code>null</code> does not <i>necessarily</i> indicate that the
	 * map contains no mapping for the key; it's also possible that the map
	 * explicitly maps the key to <code>null</code>. The <code>containsKey</code>
	 * operation may be used to distinguish these two cases.
	 *
	 * @param key    key whose associated value is to be returned.
	 *
	 * @return the value to which this map maps the specified key.
	 */
	public Object get(Object key) {
		if (key instanceof Number) {
			return get( ((Number)key).intValue() );
		} else {
			return null;
		}
	}

	/**
	 * Returns the value to which this map maps the specified key. Returns
	 * <code>null</code> if the map contains no mapping for this key. A return
	 * value of <code>null</code> does not <i>necessarily</i> indicate that the
	 * map contains no mapping for the key; it's also possible that the map
	 * explicitly maps the key to <code>null</code>. The <code>containsKey</code>
	 * operation may be used to distinguish these two cases.
	 *
	 * @param key    key whose associated value is to be returned.
	 *
	 * @return the value to which this map maps the specified key.
	 */
	public Object get(int key) {
		Entry tab[] = table;

		int index = (key & 0x7FFFFFFF) % tab.length;
		for (Entry e = tab[index]; e != null; e = e.next) {
			if (e.key == key) {
				return e.value;
			}
		}

		return null;
	}

	/**
	 * Rehashes the contents of this map into a new <code>IntHashMap</code>
	 * instance with a larger capacity. This method is called automatically when
	 * the number of keys in this map exceeds its capacity and load factor.
	 */
	private void rehash() {
		int oldCapacity = table.length;
		Entry oldMap[] = table;

		int newCapacity = oldCapacity * 2 + 1;
		Entry newMap[] = new Entry[newCapacity];

		modCount++;
		threshold = (int)(newCapacity * loadFactor);
		table = newMap;

		for (int i = oldCapacity ; i-- > 0 ;) {
			for (Entry old = oldMap[i] ; old != null ; ) {
				Entry e = old;
				old = old.next;

				int index = (e.key & 0x7FFFFFFF) % newCapacity;
				e.next = newMap[index];
				newMap[index] = e;
			}
		}
	}

	/**
	 * Associates the specified value with the specified key in this map. If the
	 * map previously contained a mapping for this key, the old value is
	 * replaced.
	 *
	 * @param key    key with which the specified value is to be associated.
	 * @param value  value to be associated with the specified key.
	 *
	 * @return previous value associated with specified key, or <code>null</code> if
	 *         there was no mapping for key. A <code>null</code> return can also indicate
	 *         that the IntHashMap previously associated <code>null</code> with the
	 *         specified key.
	 */
	public Object put(Object key, Object value) {
		if (key instanceof Number) {
			return put( ((Number)key).intValue(), value );
		} else {
			throw new UnsupportedOperationException
			("IntHashMap key must be a number");
		}
	}

	/**
	 * Associates the specified value with the specified key in this map. If the
	 * map previously contained a mapping for this key, the old value is
	 * replaced.
	 *
	 * @param key    key with which the specified value is to be associated.
	 * @param value  value to be associated with the specified key.
	 *
	 * @return previous value associated with specified key, or <code>null</code> if
	 *         there was no mapping for key. A <code>null</code> return can also indicate
	 *         that the IntHashMap previously associated <code>null</code> with the
	 *         specified key.
	 */
	public Object put(int key, Object value) {
		// makes sure the key is not already in the IntHashMap.
		Entry tab[] = table;
		int index = 0;

		index = (key & 0x7FFFFFFF) % tab.length;
		for (Entry e = tab[index] ; e != null ; e = e.next) {
			if (e.key == key) {
				Object old = e.value;
				e.value = value;
				return old;
			}
		}

		modCount++;
		if (count >= threshold) {
			// rehash the table if the threshold is exceeded
			rehash();

			tab = table;
			index = (key & 0x7FFFFFFF) % tab.length;
		}

		// creates the new entry.
		Entry e = new Entry(key, value, tab[index]);
		tab[index] = e;
		count++;
		return null;
	}

	/**
	 * Removes the mapping for this key from this map if present.
	 *
	 * @param key    key whose mapping is to be removed from the map.
	 *
	 * @return previous value associated with specified key, or <code>null</code> if
	 *         there was no mapping for key. A <code>null</code> return can also indicate
	 *         that the map previously associated <code>null</code> with the specified
	 *         key.
	 */
	public Object remove(Object key) {
		if (key instanceof Number) {
			return remove( ((Number)key).intValue() );
		} else {
			return null;
		}
	}

	/**
	 * Removes the mapping for this key from this map if present.
	 *
	 * @param key    key whose mapping is to be removed from the map.
	 *
	 * @return previous value associated with specified key, or <code>null</code> if
	 *         there was no mapping for key. A <code>null</code> return can also indicate
	 *         that the map previously associated <code>null</code> with the specified
	 *         key.
	 */
	public Object remove(int key) {
		Entry tab[] = table;

		int index = (key & 0x7FFFFFFF) % tab.length;

		for (Entry e = tab[index], prev = null; e != null;
			prev = e, e = e.next) {

			if (e.key == key) {
				modCount++;
				if (prev != null) {
					prev.next = e.next;
				} else {
					tab[index] = e.next;
				}

				count--;
				Object oldValue = e.value;
				e.value = null;
				return oldValue;
			}
		}

		return null;
	}

	/**
	 * Copies all of the mappings from the specified map to this one.
	 * These mappings replace any mappings that this map had for any of the
	 * keys currently in the specified Map.
	 *
	 * @param t      Mappings to be stored in this map.
	 */