hashtable.java

来自「linux下建立JAVA虚拟机的源码KAFFE」· Java 代码 · 共 1,252 行 · 第 1/3 页

   * @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 EntryIterator instead.
    Iterator entries = new EntryIterator();
    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 KeyIterator();
          }

          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 ValueIterator();
          }

          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 EntryIterator();
          }

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

  /**
   * Returns true if this Hashtable equals the supplied Object <code>o</code>.
   * As specified by Map, this is:
   * <code>
   * (o instanceof Map) && entrySet().equals(((Map) o).entrySet());
   * </code>
   *
   * @param o the object to compare to
   * @return true if o is an equal map
   * @since 1.2
   */
  public boolean equals(Object o)
  {
    // no need to synchronize, entrySet().equals() does that
    if (o == this)
      return true;
    if (!(o instanceof Map))
      return false;

    return entrySet().equals(((Map) o).entrySet());
  }

  /**
   * Returns the hashCode for this Hashtable.  As specified by Map, this is
   * the sum of the hashCodes of all of its Map.Entry objects
   *
   * @return the sum of the hashcodes of the entries
   * @since 1.2
   */
  public synchronized int hashCode()
  {
    // Since we are already synchronized, and entrySet().iterator()
    // would repeatedly re-lock/release the monitor, we directly use the
    // unsynchronized EntryIterator instead.
    Iterator itr = new EntryIterator();
    int hashcode = 0;
    for (int pos = size; pos > 0; pos--)
      hashcode += itr.next().hashCode();

    return hashcode;
  }

  /**
   * Helper method that returns an index in the buckets array for `key'
   * based on its hashCode().
   *
   * @param key the key
   * @return the bucket number
   * @throws NullPointerException if key is null
   */
  private int hash(Object key)
  {
    // Note: Inline Math.abs here, for less method overhead, and to avoid
    // a bootstrap dependency, since Math relies on native methods.
    int hash = key.hashCode() % buckets.length;
    return hash < 0 ? -hash : hash;
  }

  /**
   * Helper method for entrySet(), which matches both key and value
   * simultaneously. Ignores null, as mentioned in entrySet().
   *
   * @param o the entry to match
   * @return the matching entry, if found, or null
   * @see #entrySet()
   */
  // Package visible, for use in nested classes.
  HashEntry getEntry(Object o)
  {
    if (! (o instanceof Map.Entry))
      return null;
    Object key = ((Map.Entry) o).getKey();
    if (key == null)
      return null;