Collections Data Structure Java

 * 

 Retrievals
 * 
 * 

 Retrievals may overlap updates. (This is the same policy as
 * ConcurrentReaderHashMap.) Successful retrievals using get(key) and
 * containsKey(key) usually run without locking. Unsuccessful retrievals (i.e.,
 * when the key is not present) do involve brief synchronization (locking).
 * Because retrieval operations can ordinarily overlap with update operations
 * (i.e., put, remove, and their derivatives), retrievals can only be guaranteed
 * to return the results of the most recently completed operations
 * holding upon their onset. Retrieval operations may or may not return results
 * reflecting in-progress writing operations. However, the retrieval operations
 * do always return consistent results -- either those holding before any single
 * modification or after it, but never a nonsense result. For aggregate
 * operations such as putAll and clear, concurrent reads may reflect insertion
 * or removal of only some entries.
 * 

 * 
 * Iterators and Enumerations (i.e., those returned by keySet().iterator(),
 * entrySet().iterator(), values().iterator(), keys(), and elements()) return
 * elements reflecting the state of the hash table at some point at or since the
 * creation of the iterator/enumeration. They will return at most one instance
 * of each element (via next()/nextElement()), but might or might not reflect
 * puts and removes that have been processed since they were created. They do
 * not throw ConcurrentModificationException. However, these
 * iterators are designed to be used by only one thread at a time. Passing an
 * iterator across multiple threads may lead to unpredictable results if the
 * table is being concurrently modified.
 * 

 * 
 * 
 * 

 Updates
 * 
 * 

 This class supports a hard-wired preset concurrency
 * level of
 * 32. This allows a maximum of 32 put and/or remove operations to proceed
 * concurrently. This level is an upper bound on concurrency, not a guarantee,
 * since it interacts with how well-strewn elements are across bins of the
 * table. (The preset value in part reflects the fact that even on large
 * multiprocessors, factors other than synchronization tend to be bottlenecks
 * when more than 32 threads concurrently attempt updates.) Additionally,
 * operations triggering internal resizing and clearing do not execute
 * concurrently with any operation.
 * 

 * 
 * There is NOT any support for locking the entire table to prevent
 * updates. This makes it imposssible, for example, to add an element only if it
 * is not already present, since another thread may be in the process of doing
 * the same thing. If you need such capabilities, consider instead using the
 * ConcurrentReaderHashMap class.
 * 
 * 

 * 
 * This class may be used as a direct replacement for java.util.Hashtable in any
 * application that does not rely on the ability to lock the entire table to
 * prevent updates. As of this writing, it performs much faster than Hashtable
 * in typical multi-threaded applications with multiple readers and writers.
 * Like Hashtable but unlike java.util.HashMap, this class does NOT allow
 * null to be used as a key or value.
 * 

 * 
 * Implementation note: A slightly faster implementation of this class will be
 * possible once planned Java Memory Model revisions are in place.
 * 
 * 

[ * href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html">
 * Introduction to this package. ]
 * 
 */
public class ConcurrentHashMap extends AbstractMap implements Map, Cloneable, Serializable
{
  private static final long serialVersionUID = 1L;
  /*
   * The basic strategy is an optimistic-style scheme based on the guarantee
   * that the hash table and its lists are always kept in a consistent enough
   * state to be read without locking:
   * 
   * Read operations first proceed without locking, by traversing the
   * apparently correct list of the apparently correct bin. If an entry is
   * found, but not invalidated (value field null), it is returned. If not
   * found, operations must recheck (after a memory barrier) to make sure they
   * are using both the right list and the right table (which can change under
   * resizes). If invalidated, reads must acquire main update lock to wait out
   * the update, and then re-traverse.
   * 
   * All list additions are at the front of each bin, making it easy to check
   * changes, and also fast to traverse. Entry next pointers are never
   * assigned. Remove() builds new nodes when necessary to preserve this.
   * 
   * Remove() (also clear()) invalidates removed nodes to alert read
   * operations that they must wait out the full modifications.
   * 
   * Locking for puts, removes (and, when necessary gets, etc) is controlled
   * by Segments, each covering a portion of the table. During operations
   * requiring global exclusivity (mainly resize and clear), ALL of these
   * locks are acquired at once. Note that these segments are NOT contiguous --
   * they are based on the least 5 bits of hashcodes. This ensures that the
   * same segment controls the same slots before and after resizing, which is
   * necessary for supporting concurrent retrievals. This comes at the price
   * of a mismatch of logical vs physical locality, but this seems not to be a
   * performance problem in practice.
   * 
   */
  /**
   * The hash table data.
   */
  protected transient Entry[] table;
  /**
   * The number of concurrency control segments. The value can be at most 32
   * since ints are used as bitsets over segments. Emprically, it doesn't seem
   * to pay to decrease it either, so the value should be at least 32. In
   * other words, do not redefine this :-)
   */
  protected static final int CONCURRENCY_LEVEL = 32;
  /**
   * Mask value for indexing into segments
   */
  protected static final int SEGMENT_MASK = CONCURRENCY_LEVEL - 1;
  /**
   * Bookkeeping for each concurrency control segment. Each segment contains a
   * local count of the number of elements in its region. However, the main
   * use of a Segment is for its lock.
   */
  protected final static class Segment implements Serializable
  {
    private static final long serialVersionUID = 1L;
    
    /**
     * The number of elements in this segment's region. It is always updated
     * within synchronized blocks.
     */
    protected int count;
    /**
     * Get the count under synch.
     * @return count under sync
     */
    protected synchronized int getCount()
    {
      return count;
    }
    /**
     * Force a synchronization
     */
    protected synchronized void synch()
    {
    }
  }
  /**
   * The array of concurrency control segments.
   */
  protected final Segment[] segments = new Segment[CONCURRENCY_LEVEL];
  /**
   * The default initial number of table slots for this table (32). Used when
   * not otherwise specified in constructor.
   */
  public static final int DEFAULT_INITIAL_CAPACITY = 32;
  /**
   * The minimum capacity, used if a lower value is implicitly specified by
   * either of the constructors with arguments. MUST be a power of two.
   */
  private static final int MINIMUM_CAPACITY = 32;
  /**
   * The maximum capacity, used if a higher value is implicitly specified by
   * either of the constructors with arguments. MUST be a power of two <= 1<<30.
   */
  private static final int MAXIMUM_CAPACITY = 1 << 30;
  /**
   * The default load factor for this table (0.75) Used when not otherwise
   * specified in constructor.
   */
  public static final float DEFAULT_LOAD_FACTOR = 0.75f;
  /**
   * The load factor for the hash table.
   * 
   * @serial
   */
  protected final float loadFactor;
  /**
   * Per-segment resize threshold.
   * 
   * @serial
   */
  protected int threshold;
  /**
   * Number of segments voting for resize. The table is doubled when 1/4 of
   * the segments reach threshold. Volatile but updated without synch since
   * this is just a heuristic.
   */
  protected transient volatile int votesForResize;
  /**
   * Return the number of set bits in w. For a derivation of this algorithm,
   * see "Algorithms and data structures with applications to graphics and
   * geometry", by Jurg Nievergelt and Klaus Hinrichs, Prentice Hall, 1993.
   * See also notes by Torsten Sillke at
   * http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/bitcount
   * @param w arg
   * @return number of set bits
   */
  protected static int bitcount(int w)
  {
    w -= (0xaaaaaaaa & w) >>> 1;
    w = (w & 0x33333333) + ((w >>> 2) & 0x33333333);
    w = (w + (w >>> 4)) & 0x0f0f0f0f;
    w += w >>> 8;
    w += w >>> 16;
    return w & 0xff;
  }
  /**
   * Returns the appropriate capacity (power of two) for the specified initial
   * capacity argument.
   * @param initialCapacity the initial capacity
   * @return appropriate capacity
   */
  private int p2capacity(int initialCapacity)
  {
    int cap = initialCapacity;
    // Compute the appropriate capacity
    int result;
    if (cap > MAXIMUM_CAPACITY || cap < 0)
    {
      result = MAXIMUM_CAPACITY;
    }
    else
    {
      result = MINIMUM_CAPACITY;
      while (result < cap)
      {
        result <<= 1;
      }
    }
    return result;
  }
  /**
   * Return hash code for Object x. Since we are using power-of-two tables, it
   * is worth the effort to improve hashcode via the same multiplicative
   * scheme as used in IdentityHashMap.
   * @param x 
   * @return hash code
   */
  protected static int hash(Object x)
  {
    int h = x.hashCode();
    // Multiply by 127 (quickly, via shifts), and mix in some high
    // bits to help guard against bunching of codes that are
    // consecutive or equally spaced.
    return ((h << 7) - h + (h >>> 9) + (h >>> 17));
  }
  /**
   * Check for equality of non-null references x and y.
   * @param x ref
   * @param y ref
   * @return is equal
   */
  protected boolean eq(Object x, Object y)
  {
    return x == y || x.equals(y);
  }
  /**
   * Create table array and set the per-segment threshold * 
   * @param capacity 
   * @return table array
   */
  protected Entry[] newTable(int capacity)
  {
    threshold = (int)(capacity * loadFactor / CONCURRENCY_LEVEL) + 1;
    return new Entry[capacity];
  }
  /**
   * Constructs a new, empty map with the specified initial capacity and the
   * specified load factor.
   * 
   * @param initialCapacity
   *            the initial capacity. The actual initial capacity is rounded
   *            to the nearest power of two.
   * @param loadFactor
   *            the load factor threshold, used to control resizing. This
   *            value is used in an approximate way: When at least a quarter
   *            of the segments of the table reach per-segment threshold, or
   *            one of the segments itself exceeds overall threshold, the
   *            table is doubled. This will on average cause resizing when the
   *            table-wide load factor is slightly less than the threshold. If
   *            you'd like to avoid resizing, you can set this to a
   *            ridiculously large value.
   * @throws IllegalArgumentException
   *             if the load factor is nonpositive.
   */
  public ConcurrentHashMap(int initialCapacity, float loadFactor)
  {
    if (!(loadFactor > 0))
    {
      throw new IllegalArgumentException("Illegal Load factor: " + loadFactor);
    }
    this.loadFactor = loadFactor;
    for (int i = 0; i < segments.length; ++i)
    {
      segments[i] = new Segment();
    }
    int cap = p2capacity(initialCapacity);
    table = newTable(cap);
  }
  /**
   * Constructs a new, empty map with the specified initial capacity and
   * default load factor.
   * 
   * @param initialCapacity
   *            the initial capacity of the ConcurrentHashMap.
   * @throws IllegalArgumentException
   *             if the initial maximum number of elements is less than zero.
   */
  public ConcurrentHashMap(int initialCapacity)
  {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }
  /**
   * Constructs a new, empty map with a default initial capacity and default
   * load factor.
   */
  public ConcurrentHashMap()
  {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  }
  /**
   * Constructs a new map with the same mappings as the given map. The map is
   * created with a capacity of twice the number of mappings in the given map
   * or 32 (whichever is greater), and a default load factor.
   * @param t map to copy
   */
  public ConcurrentHashMap(Map t)
  {
    this(Math.max((int)(t.size() / DEFAULT_LOAD_FACTOR) + 1, MINIMUM_CAPACITY),
        DEFAULT_LOAD_FACTOR);
    putAll(t);
  }
  /**
   * Returns the number of key-value mappings in this map.
   * 
   * @return the number of key-value mappings in this map.
   */
  public int size()
  {
    int c = 0;
    for (int i = 0; i < segments.length; ++i)
    {
      c += segments[i].getCount();
    }
    return c;
  }
  /**
   * Returns true if this map contains no key-value mappings.
   * 
   * @return true if this map contains no key-value mappings.
   */
  public boolean isEmpty()
  {
    for (int i = 0; i < segments.length; ++i)
    {
      if (segments[i].getCount() != 0)
      {
        return false;
      }
    }
    return true;
  }
  /**
   * Returns the value to which the specified key is mapped in this table.
   * 
   * @param key
   *            a key in the table.
   * @return the value to which the key is mapped in this table;
   *         null if the key is not mapped to any value in this
   *         table.
   * @exception NullPointerException
   *                if the key is null.
   * @see #put(Object, Object)
   */
  public Object get(Object key)
  {
    int hash = hash(key); // throws null pointer exception if key null
    // Try first without locking...
    Entry[] tab = table;
    int index = hash & (tab.length - 1);
    Entry first = tab[index];
    Entry e;
    for (e = first; e != null; e = e.next)
    {
      if (e.hash == hash && eq(key, e.key))
      {
        Object value = e.value;
        if (value != null)
        {
          return value;
        }
        else
        {
          break;
        }
      }
    }
    // Recheck under synch if key apparently not there or interference
    Segment seg = segments[hash & SEGMENT_MASK];
    synchronized (seg)
    {
      tab = table;
      index = hash & (tab.length - 1);
      Entry newFirst = tab[index];
      if (e != null || first != newFirst)
      {
        for (e = newFirst; e != null; e = e.next)
        {
          if (e.hash == hash && eq(key, e.key))
          {
            return e.value;
          }
        }
      }
      return null;
    }
  }
  /**
   * Tests if the specified object is a key in this table.
   * 
   * @param key
   *            possible key.
   * @return true if and only if the specified object is a key
   *         in this table, as determined by the equals method;
   *         false otherwise.
   * @exception NullPointerException
   *                if the key is null.
   * @see #contains(Object)
   */
  public boolean containsKey(Object key)
  {
    return get(key) != null;
  }
  /**
   * Maps the specified key to the specified value
   * in this table. Neither the key nor the value can be null.
   * (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.)
   * 

   * 
   * The value can be retrieved by calling the get 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
   *         null if it did not have one.
   * @exception NullPointerException
   *                if the key or value is null.
   * @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 threshhold, 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
   *         null if the key did not have a mapping.
   * @exception NullPointerException
   *                if the key is null.
   */
  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
   *         null if the key did not have a mapping.
   * @exception NullPointerException
   *                if the key is null.
   */
  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 true 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 containsKey.
   * 
   * @param value
   *            value whose presence in this map is to be tested.
   * @return true if this map maps one or more keys to the
   *         specified value.
   * @exception NullPointerException
   *                if the value is null.
   */
  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 containsKey method.
   *