hashtable.java

gcc的组建

    HashEntry e = buckets[idx];
    while (e != null)
      {
        if (e.key.equals(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 (e.key.equals(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 (e.key.equals(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 (e.key.equals(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();

    while (itr.hasNext())
      {
        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;
  }

  /**