hashtable.java

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

	}

	/**
	 * Returns true if the supplied object <code>equals()</code> a key
	 * in this Hashtable.
	 *
	 * @param key the key to search for in this Hashtable
	 * @return true if the key is in the table
	 * @throws NullPointerException if key is null
	 * @see #containsValue(Object)
	 */
	public synchronized boolean containsKey(Object key) {
		int idx = hash(key);
		HashEntry e = buckets[idx];
		while (e != null) {
			if (key.equals(e.key))
				return true;
			e = e.next;
		}
		return false;
	}

	/**
	 * Return the value in this Hashtable associated with the supplied key,
	 * or <code>null</code> if the key maps to nothing.
	 *
	 * @param key the key for which to fetch an associated value
	 * @return what the key maps to, if present
	 * @throws NullPointerException if key is null
	 * @see #put(Object, Object)
	 * @see #containsKey(Object)
	 */
	public synchronized Object get(Object key) {
		int idx = hash(key);
		HashEntry e = buckets[idx];
		while (e != null) {
			if (key.equals(e.key))
				return e.value;
			e = e.next;
		}
		return null;
	}

	/**
	 * Puts the supplied value into the Map, mapped by the supplied key.
	 * Neither parameter may be null.  The value may be retrieved by any
	 * object which <code>equals()</code> this key.
	 *
	 * @param key the key used to locate the value
	 * @param value the value to be stored in the table
	 * @return the prior mapping of the key, or null if there was none
	 * @throws NullPointerException if key or value is null
	 * @see #get(Object)
	 * @see Object#equals(Object)
	 */
	public synchronized Object put(Object key, Object value) {
		int idx = hash(key);
		HashEntry e = buckets[idx];

		// Check if value is null since it is not permitted.
		if (value == null)
			throw new NullPointerException();

		while (e != null) {
			if (key.equals(e.key)) {
				// Bypass e.setValue, since we already know value is non-null.
				Object r = e.value;
				e.value = value;
				return r;
			} else {
				e = e.next;
			}
		}

		// At this point, we know we need to add a new entry.
		modCount++;
		if (++size > threshold) {
			rehash();
			// Need a new hash value to suit the bigger table.
			idx = hash(key);
		}

		e = new HashEntry(key, value);

		e.next = buckets[idx];
		buckets[idx] = e;

		return null;
	}

	/**
	 * Removes from the table and returns the value which is mapped by the
	 * supplied key. If the key maps to nothing, then the table remains
	 * unchanged, and <code>null</code> is returned.
	 *
	 * @param key the key used to locate the value to remove
	 * @return whatever the key mapped to, if present
	 */
	public synchronized Object remove(Object key) {
		int idx = hash(key);
		HashEntry e = buckets[idx];
		HashEntry last = null;

		while (e != null) {
			if (key.equals(e.key)) {
				modCount++;
				if (last == null)
					buckets[idx] = e.next;
				else
					last.next = e.next;
				size--;
				return e.value;
			}
			last = e;
			e = e.next;
		}
		return null;
	}

	/**
	 * Copies all elements of the given map into this hashtable.  However, no
	 * mapping can contain null as key or value.  If this table already has
	 * a mapping for a key, the new mapping replaces the current one.
	 *
	 * @param m the map to be hashed into this
	 * @throws NullPointerException if m is null, or contains null keys or values
	 */
	public synchronized void putAll(Map m) {
		Iterator itr = m.entrySet().iterator();

		for (int msize = m.size(); msize > 0; msize--) {
			Map.Entry e = (Map.Entry) itr.next();
			// Optimize in case the Entry is one of our own.
			if (e instanceof AbstractMap.BasicMapEntry) {
				AbstractMap.BasicMapEntry entry = (AbstractMap.BasicMapEntry) e;
				put(entry.key, entry.value);
			} else {
				put(e.getKey(), e.getValue());
			}
		}
	}

	/**
	 * Clears the hashtable so it has no keys.  This is O(1).
	 */
	public synchronized void clear() {
		if (size > 0) {
			modCount++;
			Arrays.fill(buckets, null);
			size = 0;
		}
	}

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

	/**
	 * Converts this Hashtable to a String, surrounded by braces, and with
	 * key/value pairs listed with an equals sign between, separated by a
	 * comma and space. For example, <code>"{a=1, b=2}"</code>.<p>
	 *
	 * NOTE: if the <code>toString()</code> method of any key or value
	 * throws an exception, this will fail for the same reason.
	 *
	 * @return the string representation
	 */
	public synchronized String toString() {
		// Since we are already synchronized, and entrySet().iterator()
		// would repeatedly re-lock/release the monitor, we directly use the
		// unsynchronized HashIterator instead.
		Iterator entries = new HashIterator(ENTRIES);
		StringBuffer r = new StringBuffer("{");
		for (int pos = size; pos > 0; pos--) {
			r.append(entries.next());
			if (pos > 1)
				r.append(", ");
		}
		r.append("}");
		return r.toString();
	}

	/**
	 * Returns a "set view" of this Hashtable's keys. The set is backed by
	 * the hashtable, so changes in one show up in the other.  The set supports
	 * element removal, but not element addition.  The set is properly
	 * synchronized on the original hashtable.  Sun has not documented the
	 * proper interaction of null with this set, but has inconsistent behavior
	 * in the JDK. Therefore, in this implementation, contains, remove,
	 * containsAll, retainAll, removeAll, and equals just ignore a null key
	 * rather than throwing a {@link NullPointerException}.
	 *
	 * @return a set view of the keys
	 * @see #values()
	 * @see #entrySet()
	 * @since 1.2
	 */
	public Set keySet() {
		if (keys == null) {
			// Create a synchronized AbstractSet with custom implementations of
			// those methods that can be overridden easily and efficiently.
			Set r = new AbstractSet() {
				public int size() {
					return size;
				}

				public Iterator iterator() {
					return new HashIterator(KEYS);
				}

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

				public boolean contains(Object o) {
					if (o == null)
						return false;
					return containsKey(o);
				}

				public boolean remove(Object o) {
					return Hashtable.this.remove(o) != null;
				}
			};
			// We must specify the correct object to synchronize upon, hence the
			// use of a non-public API
			keys = new Collections.SynchronizedSet(this, r);
		}
		return keys;
	}

	/**
	 * Returns a "collection view" (or "bag view") of this Hashtable's values.
	 * The collection is backed by the hashtable, so changes in one show up
	 * in the other.  The collection supports element removal, but not element
	 * addition.  The collection is properly synchronized on the original
	 * hashtable.  Sun has not documented the proper interaction of null with
	 * this set, but has inconsistent behavior in the JDK. Therefore, in this
	 * implementation, contains, remove, containsAll, retainAll, removeAll, and
	 * equals just ignore a null value rather than throwing a
	 * {@link NullPointerException}.
	 *
	 * @return a bag view of the values
	 * @see #keySet()
	 * @see #entrySet()
	 * @since 1.2
	 */
	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.
			Collection r = new AbstractCollection() {
				public int size() {
					return size;
				}

				public Iterator iterator() {
					return new HashIterator(VALUES);
				}

				public void clear() {
					Hashtable.this.clear();
				}
			};
			// We must specify the correct object to synchronize upon, hence the
			// use of a non-public API
			values = new Collections.SynchronizedCollection(this, r);
		}
		return values;
	}

	/**
	 * Returns a "set view" of this Hashtable's entries. The set is backed by
	 * the hashtable, so changes in one show up in the other.  The set supports
	 * element removal, but not element addition.  The set is properly
	 * synchronized on the original hashtable.  Sun has not documented the
	 * proper interaction of null with this set, but has inconsistent behavior
	 * in the JDK. Therefore, in this implementation, contains, remove,
	 * containsAll, retainAll, removeAll, and equals just ignore a null entry,
	 * or an entry with a null key or value, rather than throwing a
	 * {@link NullPointerException}. However, calling entry.setValue(null)
	 * will fail.
	 * <p>
	 *
	 * Note that the iterators for all three views, from keySet(), entrySet(),
	 * and values(), traverse the hashtable in the same sequence.
	 *
	 * @return a set view of the entries
	 * @see #keySet()
	 * @see #values()
	 * @see Map.Entry
	 * @since 1.2
	 */
	public Set entrySet() {
		if (entries == null) {
			// Create an AbstractSet with custom implementations of those methods
			// that can be overridden easily and efficiently.
			Set r = new AbstractSet() {
				public int size() {
					return size;
				}

				public Iterator iterator() {
					return new HashIterator(ENTRIES);
				}

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

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

				public boolean remove(Object o) {
					HashEntry e = getEntry(o);
					if (e != null) {
						Hashtable.this.remove(e.key);
						return true;
					}
					return false;
				}
			};
			// We must specify the correct object to synchronize upon, hence the
			// use of a non-public API
			entries = new Collections.SynchronizedSet(this, r);
		}
		return entries;
	}

	/**
	 * Returns true if this Hashtable equals the supplied Object <code>o</code>.
	 * As specified by Map, this is:
	 * <code>
	 * (o instanceof Map) && entrySet().equals(((Map) o).entrySet());