concurrenthashmap.java

java彩信开发

  /**
   * 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;
   *          <code>null</code> if the key is not mapped to any value in
   *          this table.
   * @exception  NullPointerException  if the key is
   *               <code>null</code>.
   * @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  <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 NullPointerException();

    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 <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 NullPointerException();

    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;
        }
      }