weakhashmap.java

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

			/**
			 * Returns the value.
			 * @return the value
			 */
			public Object getValue() {
				return value;
			}

			/**
			 * This changes the value.  This change takes place in
			 * the underlying hash map.
			 * @param newVal the new value
			 * @return the old value
			 */
			public Object setValue(Object newVal) {
				Object oldVal = value;
				value = newVal;
				return oldVal;
			}

			/**
			 * The hashCode as specified in the Entry interface.
			 * @return the hash code
			 */
			public int hashCode() {
				return key.hashCode() ^ WeakHashMap.hashCode(value);
			}

			/**
			 * The equals method as specified in the Entry interface.
			 * @param o the object to compare to
			 * @return true iff o represents the same key/value pair
			 */
			public boolean equals(Object o) {
				if (o instanceof Map.Entry) {
					Map.Entry e = (Map.Entry) o;
					return key.equals(e.getKey()) && WeakHashMap.equals(value, e.getValue());
				}
				return false;
			}

			public String toString() {
				return key + "=" + value;
			}
		}

		/**
		 * This returns the entry stored in this bucket, or null, if the
		 * bucket got cleared in the mean time.
		 * @return the Entry for this bucket, if it exists
		 */
		WeakEntry getEntry() {
			final Object key = this.get();
			if (key == null)
				return null;
			return new WeakEntry(key);
		}
	}

	/**
	 * The entry set returned by <code>entrySet()</code>.
	 */
	private final WeakEntrySet theEntrySet;

	/**
	 * The hash buckets.  These are linked lists. Package visible for use in
	 * nested classes.
	 */
	WeakBucket[] buckets;

	/**
	 * Creates a new weak hash map with default load factor and default
	 * capacity.
	 */
	public WeakHashMap() {
		this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
	}

	/**
	 * Creates a new weak hash map with default load factor and the given
	 * capacity.
	 * @param initialCapacity the initial capacity
	 * @throws IllegalArgumentException if initialCapacity is negative
	 */
	public WeakHashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_LOAD_FACTOR);
	}

	/**
	 * Creates a new weak hash map with the given initial capacity and
	 * load factor.
	 * @param initialCapacity the initial capacity.
	 * @param loadFactor the load factor (see class description of HashMap).
	 * @throws IllegalArgumentException if initialCapacity is negative, or
	 *         loadFactor is non-positive
	 */
	public WeakHashMap(int initialCapacity, float loadFactor) {
		// Check loadFactor for NaN as well.
		if (initialCapacity < 0 || !(loadFactor > 0))
			throw new IllegalArgumentException();
		this.loadFactor = loadFactor;
		threshold = (int) (initialCapacity * loadFactor);
		theEntrySet = new WeakEntrySet();
		queue = new ReferenceQueue();
		buckets = new WeakBucket[initialCapacity];
	}

	/**
	 * Construct a new WeakHashMap with the same mappings as the given map.
	 * The WeakHashMap has a default load factor of 0.75.
	 *
	 * @param m the map to copy
	 * @throws NullPointerException if m is null
	 * @since 1.3
	 */
	public WeakHashMap(Map m) {
		this(m.size(), DEFAULT_LOAD_FACTOR);
		putAll(m);
	}

	/**
	 * Simply hashes a non-null Object to its array index.
	 * @param key the key to hash
	 * @return its slot number
	 */
	private int hash(Object key) {
		return Math.abs(key.hashCode() % buckets.length);
	}

	/**
	 * Cleans the reference queue.  This will poll all references (which
	 * are WeakBuckets) from the queue and remove them from this map.
	 * This will not change modCount, even if it modifies the map.  The
	 * iterators have to make sure that nothing bad happens.  <br>
	 *
	 * Currently the iterator maintains a strong reference to the key, so
	 * that is no problem.
	 */
	// Package visible for use by nested classes.
	void cleanQueue() {
		Object bucket = queue.poll();
		while (bucket != null) {
			internalRemove((WeakBucket) bucket);
			bucket = queue.poll();
		}
	}

	/**
	 * Rehashes this hashtable.  This will be called by the
	 * <code>add()</code> method if the size grows beyond the threshold.
	 * It will grow the bucket size at least by factor two and allocates
	 * new buckets.
	 */
	private void rehash() {
		WeakBucket[] oldBuckets = buckets;
		int newsize = buckets.length * 2 + 1; // XXX should be prime.
		threshold = (int) (newsize * loadFactor);
		buckets = new WeakBucket[newsize];

		// Now we have to insert the buckets again.
		for (int i = 0; i < oldBuckets.length; i++) {
			WeakBucket bucket = oldBuckets[i];
			WeakBucket nextBucket;
			while (bucket != null) {
				nextBucket = bucket.next;

				Object key = bucket.get();
				if (key == null) {
					// This bucket should be removed; it is probably
					// already on the reference queue.  We don't insert it
					// at all, and mark it as cleared.
					bucket.slot = -1;
					size--;
				} else {
					// Add this bucket to its new slot.
					int slot = hash(key);
					bucket.slot = slot;
					bucket.next = buckets[slot];
					buckets[slot] = bucket;
				}
				bucket = nextBucket;
			}
		}
	}

	/**
	 * Finds the entry corresponding to key.  Since it returns an Entry
	 * it will also prevent the key from being removed under us.
	 * @param key the key, may be null
	 * @return The WeakBucket.WeakEntry or null, if the key wasn't found.
	 */
	private WeakBucket.WeakEntry internalGet(Object key) {
		if (key == null)
			key = NULL_KEY;
		int slot = hash(key);
		WeakBucket bucket = buckets[slot];
		while (bucket != null) {
			WeakBucket.WeakEntry entry = bucket.getEntry();
			if (entry != null && key.equals(entry.key))
				return entry;

			bucket = bucket.next;
		}
		return null;
	}

	/**
	 * Adds a new key/value pair to the hash map.
	 * @param key the key. This mustn't exists in the map. It may be null.
	 * @param value the value.
	 */
	private void internalAdd(Object key, Object value) {
		if (key == null)
			key = NULL_KEY;
		int slot = hash(key);
		WeakBucket bucket = new WeakBucket(key, queue, value, slot);
		bucket.next = buckets[slot];
		buckets[slot] = bucket;
		size++;
	}

	/**
	 * Removes a bucket from this hash map, if it wasn't removed before
	 * (e.g. one time through rehashing and one time through reference queue).
	 * Package visible for use in nested classes.
	 *
	 * @param bucket the bucket to remove.
	 */
	void internalRemove(WeakBucket bucket) {
		int slot = bucket.slot;
		if (slot == -1)
			// This bucket was already removed.
			return;

		// Mark the bucket as removed.  This is necessary, since the
		// bucket may be enqueued later by the garbage collection, and
		// internalRemove will be called a second time.
		bucket.slot = -1;
		if (buckets[slot] == bucket)
			buckets[slot] = bucket.next;
		else {
			WeakBucket prev = buckets[slot];
			/* This may throw a NullPointerException.  It shouldn't but if
			 * a race condition occurred (two threads removing the same
			 * bucket at the same time) it may happen.  <br>
			 * But with race condition many much worse things may happen
			 * anyway.
			 */
			while (prev.next != bucket)
				prev = prev.next;
			prev.next = bucket.next;
		}
		size--;
	}

	/**
	 * Returns the size of this hash map.  Note that the size() may shrink
	 * spontaneously, if the some of the keys were only weakly reachable.
	 * @return the number of entries in this hash map.
	 */
	public int size() {
		cleanQueue();
		return size;
	}

	/**
	 * Tells if the map is empty.  Note that the result may change
	 * spontanously, if all of the keys were only weakly reachable.
	 * @return true, iff the map is empty.
	 */
	public boolean isEmpty() {
		cleanQueue();
		return size == 0;
	}

	/**
	 * Tells if the map contains the given key.  Note that the result
	 * may change spontanously, if the key was only weakly
	 * reachable.
	 * @param key the key to look for
	 * @return true, iff the map contains an entry for the given key.
	 */
	public boolean containsKey(Object key) {
		cleanQueue();
		return internalGet(key) != null;
	}

	/**
	 * Gets the value the key is mapped to.
	 * @return the value the key was mapped to.  It returns null if
	 *         the key wasn't in this map, or if the mapped value was
	 *         explicitly set to null.
	 */
	public Object get(Object key) {
		cleanQueue();
		WeakBucket.WeakEntry entry = internalGet(key);
		return entry == null ? null : entry.getValue();
	}

	/**
	 * Adds a new key/value mapping to this map.
	 * @param key the key, may be null
	 * @param value the value, may be null
	 * @return the value the key was mapped to previously.  It returns
	 *         null if the key wasn't in this map, or if the mapped value
	 *         was explicitly set to null.
	 */
	public Object put(Object key, Object value) {
		cleanQueue();
		WeakBucket.WeakEntry entry = internalGet(key);
		if (entry != null)
			return entry.setValue(value);

		modCount++;
		if (size >= threshold)
			rehash();

		internalAdd(key, value);
		return null;
	}

	/**
	 * Removes the key and the corresponding value from this map.
	 * @param key the key. This may be null.
	 * @return the value the key was mapped to previously.  It returns
	 *         null if the key wasn't in this map, or if the mapped value was
	 *         explicitly set to null.
	 */
	public Object remove(Object key) {
		cleanQueue();
		WeakBucket.WeakEntry entry = internalGet(key);
		if (entry == null)
			return null;

		modCount++;
		internalRemove(entry.getBucket());
		return entry.getValue();
	}

	/**
	 * Returns a set representation of the entries in this map.  This
	 * set will not have strong references to the keys, so they can be
	 * silently removed.  The returned set has therefore the same
	 * strange behaviour (shrinking size(), disappearing entries) as
	 * this weak hash map.
	 * @return a set representation of the entries.
	 */
	public Set entrySet() {
		cleanQueue();
		return theEntrySet;
	}

	/**
	 * Clears all entries from this map.
	 */
	public void clear() {
		super.clear();
	}

	/**
	 * Returns true if the map contains at least one key which points to
	 * the specified object as a value.  Note that the result
	 * may change spontanously, if its key was only weakly reachable.
	 * @param value the value to search for
	 * @return true if it is found in the set.
	 */
	public boolean containsValue(Object value) {
		cleanQueue();
		return super.containsValue(value);
	}

	/**
	 * Returns a set representation of the keys in this map.  This
	 * set will not have strong references to the keys, so they can be
	 * silently removed.  The returned set has therefore the same
	 * strange behaviour (shrinking size(), disappearing entries) as
	 * this weak hash map.
	 * @return a set representation of the keys.
	 */
	public Set keySet() {
		cleanQueue();
		return super.keySet();
	}

	/**
	 * Puts all of the mappings from the given map into this one. If the
	 * key already exists in this map, its value is replaced.
	 * @param m the map to copy in
	 */
	public void putAll(Map m) {
		super.putAll(m);
	}

	/**
	 * Returns a collection representation of the values in this map.  This
	 * collection will not have strong references to the keys, so mappings
	 * can be silently removed.  The returned collection has therefore the same
	 * strange behaviour (shrinking size(), disappearing entries) as
	 * this weak hash map.
	 * @return a collection representation of the values.
	 */
	public Collection values() {
		cleanQueue();
		return super.values();
	}
} // class WeakHashMap