hashtable.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 1,058 行 · 第 1/3 页

	 * </code>
	 *
	 * @param o the object to compare to
	 * @return true if o is an equal map
	 * @since 1.2
	 */
	public boolean equals(Object o) {
		// no need to synchronize, entrySet().equals() does that
		if (o == this)
			return true;
		if (!(o instanceof Map))
			return false;

		return entrySet().equals(((Map) o).entrySet());
	}

	/**
	 * Returns the hashCode for this Hashtable.  As specified by Map, this is
	 * the sum of the hashCodes of all of its Map.Entry objects
	 *
	 * @return the sum of the hashcodes of the entries
	 * @since 1.2
	 */
	public synchronized int hashCode() {
		// Since we are already synchronized, and entrySet().iterator()
		// would repeatedly re-lock/release the monitor, we directly use the
		// unsynchronized HashIterator instead.
		Iterator itr = new HashIterator(ENTRIES);
		int hashcode = 0;
		for (int pos = size; pos > 0; pos--)
			hashcode += itr.next().hashCode();

		return hashcode;
	}

	/**
	 * Helper method that returns an index in the buckets array for `key'
	 * based on its hashCode().
	 *
	 * @param key the key
	 * @return the bucket number
	 * @throws NullPointerException if key is null
	 */
	private int hash(Object key) {
		// Note: Inline Math.abs here, for less method overhead, and to avoid
		// a bootstrap dependency, since Math relies on native methods.
		int hash = key.hashCode() % buckets.length;
		return hash < 0 ? -hash : hash;
	}

	/**
	 * Helper method for entrySet(), which matches both key and value
	 * simultaneously. Ignores null, as mentioned in entrySet().
	 *
	 * @param o the entry to match
	 * @return the matching entry, if found, or null
	 * @see #entrySet()
	 */
	// Package visible, for use in nested classes.
	HashEntry getEntry(Object o) {
		if (!(o instanceof Map.Entry))
			return null;
		Object key = ((Map.Entry) o).getKey();
		if (key == null)
			return null;

		int idx = hash(key);
		HashEntry e = buckets[idx];
		while (e != null) {
			if (o.equals(e))
				return e;
			e = e.next;
		}
		return null;
	}

	/**
	 * A simplified, more efficient internal implementation of putAll(). The 
	 * Map constructor and clone() should not call putAll or put, in order to 
	 * be compatible with the JDK implementation with respect to subclasses.
	 *
	 * @param m the map to initialize this from
	 */
	void putAllInternal(Map m) {
		Iterator itr = m.entrySet().iterator();
		int msize = m.size();
		this.size = msize;

		for (; msize > 0; msize--) {
			Map.Entry e = (Map.Entry) itr.next();
			Object key = e.getKey();
			int idx = hash(key);
			HashEntry he = new HashEntry(key, e.getValue());
			he.next = buckets[idx];
			buckets[idx] = he;
		}
	}

	/**
	 * Increases the size of the Hashtable and rehashes all keys to new array
	 * indices; this is called when the addition of a new value would cause
	 * size() &gt; threshold. Note that the existing Entry objects are reused in
	 * the new hash table.
	 * <p>
	 *
	 * This is not specified, but the new size is twice the current size plus
	 * one; this number is not always prime, unfortunately. This implementation
	 * is not synchronized, as it is only invoked from synchronized methods.
	 */
	protected void rehash() {
		HashEntry[] oldBuckets = buckets;

		int newcapacity = (buckets.length * 2) + 1;
		threshold = (int) (newcapacity * loadFactor);
		buckets = new HashEntry[newcapacity];

		for (int i = oldBuckets.length - 1; i >= 0; i--) {
			HashEntry e = oldBuckets[i];
			while (e != null) {
				int idx = hash(e.key);
				HashEntry dest = buckets[idx];

				if (dest != null) {
					while (dest.next != null)
						dest = dest.next;
					dest.next = e;
				} else {
					buckets[idx] = e;
				}

				HashEntry next = e.next;
				e.next = null;
				e = next;
			}
		}
	}

	/**
	 * Serializes this object to the given stream.
	 *
	 * @param s the stream to write to
	 * @throws IOException if the underlying stream fails
	 * @serialData the <i>capacity</i> (int) that is the length of the
	 *             bucket array, the <i>size</i> (int) of the hash map
	 *             are emitted first.  They are followed by size entries,
	 *             each consisting of a key (Object) and a value (Object).
	 */
	private synchronized void writeObject(ObjectOutputStream s) throws IOException {
		// Write the threshold and loadFactor fields.
		s.defaultWriteObject();

		s.writeInt(buckets.length);
		s.writeInt(size);
		// Since we are already synchronized, and entrySet().iterator()
		// would repeatedly re-lock/release the monitor, we directly use the
		// unsynchronized HashIterator instead.
		Iterator it = new HashIterator(ENTRIES);
		while (it.hasNext()) {
			HashEntry entry = (HashEntry) it.next();
			s.writeObject(entry.key);
			s.writeObject(entry.value);
		}
	}

	/**
	 * Deserializes this object from the given stream.
	 *
	 * @param s the stream to read from
	 * @throws ClassNotFoundException if the underlying stream fails
	 * @throws IOException if the underlying stream fails
	 * @serialData the <i>capacity</i> (int) that is the length of the
	 *             bucket array, the <i>size</i> (int) of the hash map
	 *             are emitted first.  They are followed by size entries,
	 *             each consisting of a key (Object) and a value (Object).
	 */
	private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
		// Read the threshold and loadFactor fields.
		s.defaultReadObject();

		// Read and use capacity.
		buckets = new HashEntry[s.readInt()];
		int len = s.readInt();

		// Read and use key/value pairs.
		// TODO: should we be defensive programmers, and check for illegal nulls?
		while (--len >= 0)
			put(s.readObject(), s.readObject());
	}

	/**
	 * A class which implements the Iterator interface and is used for
	 * iterating over Hashtables.
	 * This implementation is parameterized to give a sequential view of
	 * keys, values, or entries; it also allows the removal of elements,
	 * as per the Javasoft spec.  Note that it is not synchronized; this is
	 * a performance enhancer since it is never exposed externally and is
	 * only used within synchronized blocks above.
	 *
	 * @author Jon Zeppieri
	 */
	private final class HashIterator implements Iterator {
		/**
		 * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
		 * or {@link #ENTRIES}.
		 */
		final int type;
		/**
		 * The number of modifications to the backing Hashtable that we know about.
		 */
		int knownMod = modCount;
		/** The number of elements remaining to be returned by next(). */
		int count = size;
		/** Current index in the physical hash table. */
		int idx = buckets.length;
		/** The last Entry returned by a next() call. */
		HashEntry last;
		/**
		 * The next entry that should be returned by next(). It is set to something
		 * if we're iterating through a bucket that contains multiple linked
		 * entries. It is null if next() needs to find a new bucket.
		 */
		HashEntry next;

		/**
		 * Construct a new HashIterator with the supplied type.
		 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
		 */
		HashIterator(int type) {
			this.type = type;
		}

		/**
		 * Returns true if the Iterator has more elements.
		 * @return true if there are more elements
		 * @throws ConcurrentModificationException if the hashtable was modified
		 */
		public boolean hasNext() {
			if (knownMod != modCount)
				throw new ConcurrentModificationException();
			return count > 0;
		}

		/**
		 * Returns the next element in the Iterator's sequential view.
		 * @return the next element
		 * @throws ConcurrentModificationException if the hashtable was modified
		 * @throws NoSuchElementException if there is none
		 */
		public Object next() {
			if (knownMod != modCount)
				throw new ConcurrentModificationException();
			if (count == 0)
				throw new NoSuchElementException();
			count--;
			HashEntry e = next;

			while (e == null)
				e = buckets[--idx];

			next = e.next;
			last = e;
			if (type == VALUES)
				return e.value;
			if (type == KEYS)
				return e.key;
			return e;
		}

		/**
		 * Removes from the backing Hashtable the last element which was fetched
		 * with the <code>next()</code> method.
		 * @throws ConcurrentModificationException if the hashtable was modified
		 * @throws IllegalStateException if called when there is no last element
		 */
		public void remove() {
			if (knownMod != modCount)
				throw new ConcurrentModificationException();
			if (last == null)
				throw new IllegalStateException();

			Hashtable.this.remove(last.key);
			last = null;
			knownMod++;
		}
	} // class HashIterator

	/**
	 * Enumeration view of this Hashtable, providing sequential access to its
	 * elements; this implementation is parameterized to provide access either
	 * to the keys or to the values in the Hashtable.
	 *
	 * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
	 * as this could cause a rehash and we'd completely lose our place.  Even
	 * without a rehash, it is undetermined if a new element added would
	 * appear in the enumeration.  The spec says nothing about this, but
	 * the "Java Class Libraries" book infers that modifications to the
	 * hashtable during enumeration causes indeterminate results.  Don't do it!
	 *
	 * @author Jon Zeppieri
	 */
	private final class Enumerator implements Enumeration {
		/**
		 * The type of this Iterator: {@link #KEYS} or {@link #VALUES}.
		 */
		final int type;
		/** The number of elements remaining to be returned by next(). */
		int count = size;
		/** Current index in the physical hash table. */
		int idx = buckets.length;
		/**
		 * Entry which will be returned by the next nextElement() call. It is
		 * set if we are iterating through a bucket with multiple entries, or null
		 * if we must look in the next bucket.
		 */
		HashEntry next;

		/**
		 * Construct the enumeration.
		 * @param type either {@link #KEYS} or {@link #VALUES}.
		 */
		Enumerator(int type) {
			this.type = type;
		}

		/**
		 * Checks whether more elements remain in the enumeration.
		 * @return true if nextElement() will not fail.
		 */
		public boolean hasMoreElements() {
			return count > 0;
		}

		/**
		 * Returns the next element.
		 * @return the next element
		 * @throws NoSuchElementException if there is none.
		 */
		public Object nextElement() {
			if (count == 0)
				throw new NoSuchElementException("Hashtable Enumerator");
			count--;
			HashEntry e = next;

			while (e == null)
				e = buckets[--idx];

			next = e.next;
			return type == VALUES ? e.value : e.key;
		}
	} // class Enumerator
} // class Hashtable