hashmap.java

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

		for (int i = buckets.length - 1; i >= 0; i--) {
			HashEntry e = buckets[i];
			while (e != null) {
				if (equals(value, e.value))
					return true;
				e = e.next;
			}
		}
		return false;
	}

	/**
	 * Returns a shallow clone of this HashMap. The Map itself is cloned,
	 * but its contents are not.  This is O(n).
	 *
	 * @return the clone
	 */
	public Object clone() {
		HashMap copy = null;
		try {
			copy = (HashMap) super.clone();
		} catch (CloneNotSupportedException x) {
			// This is impossible.
		}
		copy.buckets = new HashEntry[buckets.length];
		copy.putAllInternal(this);
		// Clear the entry cache. AbstractMap.clone() does the others.
		copy.entries = null;
		return copy;
	}

	/**
	 * Returns a "set view" of this HashMap's keys. The set is backed by the
	 * HashMap, so changes in one show up in the other.  The set supports
	 * element removal, but not element addition.
	 *
	 * @return a set view of the keys
	 * @see #values()
	 * @see #entrySet()
	 */
	public Set keySet() {
		if (keys == null)
			// Create an AbstractSet with custom implementations of those methods
			// that can be overridden easily and efficiently.
			keys = new AbstractSet() {
			public int size() {
				return size;
			}

			public Iterator iterator() {
				// Cannot create the iterator directly, because of LinkedHashMap.
				return HashMap.this.iterator(KEYS);
			}

			public void clear() {
				HashMap.this.clear();
			}

			public boolean contains(Object o) {
				return containsKey(o);
			}

			public boolean remove(Object o) {
				// Test against the size of the HashMap to determine if anything
				// really got removed. This is necessary because the return value
				// of HashMap.remove() is ambiguous in the null case.
				int oldsize = size;
				HashMap.this.remove(o);
				return oldsize != size;
			}
		};
		return keys;
	}

	/**
	 * Returns a "collection view" (or "bag view") of this HashMap's values.
	 * The collection is backed by the HashMap, so changes in one show up
	 * in the other.  The collection supports element removal, but not element
	 * addition.
	 *
	 * @return a bag view of the values
	 * @see #keySet()
	 * @see #entrySet()
	 */
	public Collection values() {
		if (values == null)
			// We don't bother overriding many of the optional methods, as doing so
			// wouldn't provide any significant performance advantage.
			values = new AbstractCollection() {
			public int size() {
				return size;
			}

			public Iterator iterator() {
				// Cannot create the iterator directly, because of LinkedHashMap.
				return HashMap.this.iterator(VALUES);
			}

			public void clear() {
				HashMap.this.clear();
			}
		};
		return values;
	}

	/**
	 * Returns a "set view" of this HashMap's entries. The set is backed by
	 * the HashMap, so changes in one show up in the other.  The set supports
	 * element removal, but not element addition.<p>
	 *
	 * Note that the iterators for all three views, from keySet(), entrySet(),
	 * and values(), traverse the HashMap in the same sequence.
	 *
	 * @return a set view of the entries
	 * @see #keySet()
	 * @see #values()
	 * @see Map.Entry
	 */
	public Set entrySet() {
		if (entries == null)
			// Create an AbstractSet with custom implementations of those methods
			// that can be overridden easily and efficiently.
			entries = new AbstractSet() {
			public int size() {
				return size;
			}

			public Iterator iterator() {
				// Cannot create the iterator directly, because of LinkedHashMap.
				return HashMap.this.iterator(ENTRIES);
			}

			public void clear() {
				HashMap.this.clear();
			}

			public boolean contains(Object o) {
				return getEntry(o) != null;
			}

			public boolean remove(Object o) {
				HashEntry e = getEntry(o);
				if (e != null) {
					HashMap.this.remove(e.key);
					return true;
				}
				return false;
			}
		};
		return entries;
	}

	/**
	 * Helper method for put, that creates and adds a new Entry.  This is
	 * overridden in LinkedHashMap for bookkeeping purposes.
	 *
	 * @param key the key of the new Entry
	 * @param value the value
	 * @param idx the index in buckets where the new Entry belongs
	 * @param callRemove whether to call the removeEldestEntry method
	 * @see #put(Object, Object)
	 */
	void addEntry(Object key, Object value, int idx, boolean callRemove) {
		HashEntry e = new HashEntry(key, value);
		e.next = buckets[idx];
		buckets[idx] = e;
	}

	/**
	 * Helper method for entrySet(), which matches both key and value
	 * simultaneously.
	 *
	 * @param o the entry to match
	 * @return the matching entry, if found, or null
	 * @see #entrySet()
	 */
	// Package visible, for use in nested classes.
	final HashEntry getEntry(Object o) {
		if (!(o instanceof Map.Entry))
			return null;
		Map.Entry me = (Map.Entry) o;
		Object key = me.getKey();
		int idx = hash(key);
		HashEntry e = buckets[idx];
		while (e != null) {
			if (equals(e.key, key))
				return equals(e.value, me.getValue()) ? e : null;
			e = e.next;
		}
		return null;
	}

	/**
	 * Helper method that returns an index in the buckets array for `key'
	 * based on its hashCode().  Package visible for use by subclasses.
	 *
	 * @param key the key
	 * @return the bucket number
	 */
	final int hash(Object key) {
		try {
			if (key == null) {
				return 0;
			} else {
				return Math.abs(key.hashCode() % buckets.length);
			}
		} catch (Exception ex) {
			ex.printStackTrace(System.err);
			if (key != null) {
				System.err.println("buckets.length = " + buckets.length + " key.hc=" + key.hashCode());
			} else {
				System.err.println("buckets.length = " + buckets.length + " key=" + key);
			}
			return 0;
		}
	}

	/**
	 * Generates a parameterized iterator.  Must be overrideable, since
	 * LinkedHashMap iterates in a different order.
	 *
	 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
	 * @return the appropriate iterator
	 */
	Iterator iterator(int type) {
		return new HashIterator(type);
	}

	/**
	 * 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();
		size = msize;
		while (msize-- > 0) {
			Map.Entry e = (Map.Entry) itr.next();
			Object key = e.getKey();
			int idx = hash(key);
			addEntry(key, e.getValue(), idx, false);
		}
	}

	/**
	 * Increases the size of the HashMap 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.
	 */
	private 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 void writeObject(ObjectOutputStream s) throws IOException {
		// Write the threshold and loadFactor fields.
		s.defaultWriteObject();

		s.writeInt(buckets.length);
		s.writeInt(size);
		// Avoid creating a wasted Set by creating the iterator directly.
		Iterator it = iterator(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, followed by key/value pairs.
		buckets = new HashEntry[s.readInt()];
		int len = s.readInt();
		size = len;
		while (len-- > 0) {
			Object key = s.readObject();
			addEntry(key, s.readObject(), hash(key), false);
		}
	}

	/**
	 * Iterate over HashMap's entries.
	 * This implementation is parameterized to give a sequential view of
	 * keys, values, or entries.
	 *
	 * @author Jon Zeppieri
	 */
	private final class HashIterator implements Iterator {
		/**
		 * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
		 * or {@link #ENTRIES}.
		 */
		private final int type;
		/**
		 * The number of modifications to the backing HashMap that we know about.
		 */
		private int knownMod = modCount;
		/** The number of elements remaining to be returned by next(). */
		private int count = size;
		/** Current index in the physical hash table. */
		private int idx = buckets.length;
		/** The last Entry returned by a next() call. */
		private 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.
		 */
		private 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 HashMap 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 HashMap 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 HashMap the last element which was fetched
		 * with the <code>next()</code> method.
		 * @throws ConcurrentModificationException if the HashMap 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();

			HashMap.this.remove(last.key);
			last = null;
			knownMod++;
		}
	}
}