concurrenthashmap.java

Wicket一个开发Java Web应用程序框架。它使得开发web应用程序变得容易而轻松。 Wicket利用一个POJO data beans组件使得它可以与任何持久层技术相结合。

			}
			return null;
		}
	}

	/**
	 * Tests if the specified object is a key in this table.
	 * 
	 * @param key
	 *            possible key.
	 * @return <code>true</code> if and only if the specified object is a key in this table, as
	 *         determined by the <tt>equals</tt> method; <code>false</code> otherwise.
	 * @exception NullPointerException
	 *                if the key is <code>null</code>.
	 * @see #contains(Object)
	 */
	public boolean containsKey(Object key)
	{
		return get(key) != null;
	}

	/**
	 * Maps the specified <code>key</code> to the specified <code>value</code> in this table.
	 * Neither the key nor the value can be <code>null</code>. (Note that this policy is the same
	 * as for java.util.Hashtable, but unlike java.util.HashMap, which does accept nulls as valid
	 * keys and values.)
	 * <p>
	 * 
	 * The value can be retrieved by calling the <code>get</code> method with a key that is equal
	 * to the original key.
	 * 
	 * @param key
	 *            the table key.
	 * @param value
	 *            the value.
	 * @return the previous value of the specified key in this table, or <code>null</code> if it
	 *         did not have one.
	 * @exception NullPointerException
	 *                if the key or value is <code>null</code>.
	 * @see Object#equals(Object)
	 * @see #get(Object)
	 */
	public Object put(Object key, Object value)
	{
		if (value == null)
		{
			throw new IllegalArgumentException("Value must not be null");
		}
		int hash = hash(key);
		Segment seg = segments[hash & SEGMENT_MASK];
		int segcount;
		Entry[] tab;
		int votes;

		synchronized (seg)
		{
			tab = table;
			int index = hash & (tab.length - 1);
			Entry first = tab[index];

			for (Entry e = first; e != null; e = e.next)
			{
				if (e.hash == hash && eq(key, e.key))
				{
					Object oldValue = e.value;
					e.value = value;
					return oldValue;
				}
			}

			// Add to front of list
			Entry newEntry = new Entry(hash, key, value, first);
			tab[index] = newEntry;

			if ((segcount = ++seg.count) < threshold)
			{
				return null;
			}

			int bit = (1 << (hash & SEGMENT_MASK));
			votes = votesForResize;
			if ((votes & bit) == 0)
			{
				votes = votesForResize |= bit;
			}
		}

		// Attempt resize if 1/4 segs vote,
		// or if this seg itself reaches the overall threshold.
		// (The latter check is just a safeguard to avoid pathological cases.)
		if (bitcount(votes) >= CONCURRENCY_LEVEL / 4 || segcount > (threshold * CONCURRENCY_LEVEL))
		{
			resize(0, tab);
		}

		return null;
	}

	/**
	 * Gather all locks in order to call rehash, by recursing within synch blocks for each segment
	 * index.
	 * 
	 * @param index
	 *            the current segment. initially call value must be 0
	 * @param assumedTab
	 *            the state of table on first call to resize. If this changes on any call, the
	 *            attempt is aborted because the table has already been resized by another thread.
	 */
	protected void resize(int index, Entry[] assumedTab)
	{
		Segment seg = segments[index];
		synchronized (seg)
		{
			if (assumedTab == table)
			{
				int next = index + 1;
				if (next < segments.length)
				{
					resize(next, assumedTab);
				}
				else
				{
					rehash();
				}
			}
		}
	}

	/**
	 * Rehashes the contents of this map into a new table with a larger capacity.
	 */
	protected void rehash()
	{
		votesForResize = 0; // reset

		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;

		if (oldCapacity >= MAXIMUM_CAPACITY)
		{
			threshold = Integer.MAX_VALUE; // avoid retriggering
			return;
		}

		int newCapacity = oldCapacity << 1;
		Entry[] newTable = newTable(newCapacity);
		int mask = newCapacity - 1;

		/*
		 * Reclassify nodes in each list to new Map. Because we are using power-of-two expansion,
		 * the elements from each bin must either stay at same index, or move to oldCapacity+index.
		 * We also eliminate unnecessary node creation by catching cases where old nodes can be
		 * reused because their next fields won't change. Statistically, at the default threshold,
		 * only about one-sixth of them need cloning. (The nodes they replace will be garbage
		 * collectable as soon as they are no longer referenced by any reader thread that may be in
		 * the midst of traversing table right now.)
		 */

		for (int i = 0; i < oldCapacity; i++)
		{
			// We need to guarantee that any existing reads of old Map can
			// proceed. So we cannot yet null out each bin.
			Entry e = oldTable[i];

			if (e != null)
			{
				int idx = e.hash & mask;
				Entry next = e.next;

				// Single node on list
				if (next == null)
				{
					newTable[idx] = e;
				}
				else
				{
					// Reuse trailing consecutive sequence of all same bit
					Entry lastRun = e;
					int lastIdx = idx;
					for (Entry last = next; last != null; last = last.next)
					{
						int k = last.hash & mask;
						if (k != lastIdx)
						{
							lastIdx = k;
							lastRun = last;
						}
					}
					newTable[lastIdx] = lastRun;

					// Clone all remaining nodes
					for (Entry p = e; p != lastRun; p = p.next)
					{
						int k = p.hash & mask;
						newTable[k] = new Entry(p.hash, p.key, p.value, newTable[k]);
					}
				}
			}
		}

		table = newTable;
	}

	/**
	 * Removes the key (and its corresponding value) from this table. This method does nothing if
	 * the key is not in the table.
	 * 
	 * @param key
	 *            the key that needs to be removed.
	 * @return the value to which the key had been mapped in this table, or <code>null</code> if
	 *         the key did not have a mapping.
	 * @exception NullPointerException
	 *                if the key is <code>null</code>.
	 */
	public Object remove(Object key)
	{
		return remove(key, null);
	}

	/**
	 * Removes the (key, value) pair from this table. This method does nothing if the key is not in
	 * the table, or if the key is associated with a different value. This method is needed by
	 * EntrySet.
	 * 
	 * @param key
	 *            the key that needs to be removed.
	 * @param value
	 *            the associated value. If the value is null, it means "any value".
	 * @return the value to which the key had been mapped in this table, or <code>null</code> if
	 *         the key did not have a mapping.
	 * @exception NullPointerException
	 *                if the key is <code>null</code>.
	 */
	protected Object remove(Object key, Object value)
	{
		/*
		 * Find the entry, then 1. Set value field to null, to force get() to retry 2. Rebuild the
		 * list without this entry. All entries following removed node can stay in list, but all
		 * preceeding ones need to be cloned. Traversals rely on this strategy to ensure that
		 * elements will not be repeated during iteration.
		 */

		int hash = hash(key);
		Segment seg = segments[hash & SEGMENT_MASK];

		synchronized (seg)
		{
			Entry[] tab = table;
			int index = hash & (tab.length - 1);
			Entry first = tab[index];
			Entry e = first;

			for (;;)
			{
				if (e == null)
				{
					return null;
				}
				if (e.hash == hash && eq(key, e.key))
				{
					break;
				}
				e = e.next;
			}

			Object oldValue = e.value;
			if (value != null && !value.equals(oldValue))
			{
				return null;
			}

			e.value = null;

			Entry head = e.next;
			for (Entry p = first; p != e; p = p.next)
			{
				head = new Entry(p.hash, p.key, p.value, head);
			}
			tab[index] = head;
			seg.count--;
			return oldValue;
		}
	}

	/**
	 * Returns <tt>true</tt> if this map maps one or more keys to the specified value. Note: This
	 * method requires a full internal traversal of the hash table, and so is much slower than
	 * method <tt>containsKey</tt>.
	 * 
	 * @param value
	 *            value whose presence in this map is to be tested.
	 * @return <tt>true</tt> if this map maps one or more keys to the specified value.
	 * @exception NullPointerException
	 *                if the value is <code>null</code>.
	 */
	public boolean containsValue(Object value)
	{
		if (value == null)
		{
			throw new IllegalArgumentException("Value must not be null");
		}
		for (int s = 0; s < segments.length; ++s)
		{
			Segment seg = segments[s];
			Entry[] tab;
			synchronized (seg)
			{
				tab = table;
			}
			for (int i = s; i < tab.length; i += segments.length)
			{
				for (Entry e = tab[i]; e != null; e = e.next)
				{
					if (value.equals(e.value))
					{
						return true;
					}
				}
			}
		}
		return false;
	}

	/**
	 * Tests if some key maps into the specified value in this table. This operation is more
	 * expensive than the <code>containsKey</code> method.
	 * <p>
	 * 
	 * Note that this method is identical in functionality to containsValue, (which is part of the
	 * Map interface in the collections framework).
	 * 
	 * @param value
	 *            a value to search for.
	 * @return <code>true</code> if and only if some key maps to the <code>value</code> argument
	 *         in this table as determined by the <tt>equals</tt> method; <code>false</code>
	 *         otherwise.
	 * @exception NullPointerException
	 *                if the value is <code>null</code>.
	 * @see #containsKey(Object)
	 * @see #containsValue(Object)
	 * @see Map
	 */
	public boolean contains(Object value)
	{
		return containsValue(value);
	}

	/**
	 * 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.
	 */
	public void putAll(Map t)
	{
		int n = t.size();
		if (n == 0)
		{
			return;
		}

		// Expand enough to hold at least n elements without resizing.
		// We can only resize table by factor of two at a time.
		// It is faster to rehash with fewer elements, so do it now.
		for (;;)
		{
			Entry[] tab;
			int max;
			synchronized (segments[0])
			{ // must synch on some segment. pick 0.
				tab = table;
				max = threshold * CONCURRENCY_LEVEL;
			}
			if (n < max)
			{
				break;
			}
			resize(0, tab);
		}

		for (Iterator it = t.entrySet().iterator(); it.hasNext();)
		{
			Map.Entry entry = (Map.Entry)it.next();
			put(entry.getKey(), entry.getValue());
		}
	}

	/**
	 * Removes all mappings from this map.
	 */
	public void clear()
	{
		// We don't need all locks at once so long as locks
		// are obtained in low to high order
		for (int s = 0; s < segments.length; ++s)
		{
			Segment seg = segments[s];
			synchronized (seg)
			{
				Entry[] tab = table;
				for (int i = s; i < tab.length; i += segments.length)
				{
					for (Entry e = tab[i]; e != null; e = e.next)
					{
						e.value = null;
					}
					tab[i] = null;
					seg.count = 0;
				}
			}
		}
	}

	/**
	 * Returns a shallow copy of this <tt>ConcurrentHashMap</tt> instance: the keys and values
	 * themselves are not cloned.
	 * 
	 * @return a shallow copy of this map.
	 */
	public Object clone()
	{
		// We cannot call super.clone, since it would share final segments
		// array,
		// and there's no way to reassign finals.
		return new ConcurrentHashMap(this);
	}

	// Views

	protected transient Set keySet = null;
	protected transient Set entrySet = null;
	protected transient Collection values = null;

	/**
	 * Returns a set view of the keys contained in this map. The set is backed by the map, so
	 * changes to the map are reflected in the set, and vice-versa. The set supports element
	 * removal, which removes the corresponding mapping from this map, via the
	 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
	 * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support the <tt>add</tt>
	 * or <tt>addAll</tt> operations.
	 * 
	 * @return a set view of the keys contained in this map.
	 */
	public Set keySet()
	{
		Set ks = keySet;
		return (ks != null) ? ks : (keySet = new KeySet());
	}

	private class KeySet extends AbstractSet
	{
		/**
		 * @see java.util.Set#iterator()
		 */
		public Iterator iterator()
		{
			return new KeyIterator();
		}

		/**
		 * @see java.util.Set#size()
		 */
		public int size()
		{
			return ConcurrentHashMap.this.size();
		}

		/**
		 * @see java.util.Set#contains(java.lang.Object)
		 */
		public boolean contains(Object o)
		{
			return containsKey(o);
		}

		/**
		 * @see java.util.Set#remove(java.lang.Object)
		 */
		public boolean remove(Object o)
		{
			return ConcurrentHashMap.this.remove(o) != null;