hashtable.java

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

    int idx = hash(key);
    HashEntry e = buckets[idx];
    while (e != null)
      {
        if (e.equals(o))
          return e;
        e = e.next;
      }
    return null;
  }

  /**
   * A simplified, more efficient internal implementation of putAll(). clone() 
   * should not call putAll or put, in order to be compatible with the JDK 
   * implementation with respect to subclasses.
   *
   * @param m the map to initialize this from
   */
  void putAllInternal(Map m)
  {
    Iterator itr = m.entrySet().iterator();
    size = 0;

    while (itr.hasNext())
      {
        size++;
	Map.Entry e = (Map.Entry) itr.next();
	Object key = e.getKey();
	int idx = hash(key);
	HashEntry he = new HashEntry(key, e.getValue());
	he.next = buckets[idx];
	buckets[idx] = he;
      }
  }

  /**
   * Increases the size of the Hashtable and rehashes all keys to new array
   * indices; this is called when the addition of a new value would cause
   * size() > threshold. Note that the existing Entry objects are reused in
   * the new hash table.
   * <p>
   *
   * This is not specified, but the new size is twice the current size plus
   * one; this number is not always prime, unfortunately. This implementation
   * is not synchronized, as it is only invoked from synchronized methods.
   */
  protected void rehash()
  {
    HashEntry[] oldBuckets = buckets;

    int newcapacity = (buckets.length * 2) + 1;
    threshold = (int) (newcapacity * loadFactor);
    buckets = new HashEntry[newcapacity];

    for (int i = oldBuckets.length - 1; i >= 0; i--)
      {
        HashEntry e = oldBuckets[i];
        while (e != null)
          {
            int idx = hash(e.key);
            HashEntry dest = buckets[idx];

            if (dest != null)
              {
                HashEntry next = dest.next;
                while (next != null)
                  {
                    dest = next;
                    next = dest.next;
                  }
                dest.next = e;
              }
            else
              {
                buckets[idx] = e;
              }

            HashEntry next = e.next;
            e.next = null;
            e = next;
          }
      }
  }

  /**
   * Serializes this object to the given stream.
   *
   * @param s the stream to write to
   * @throws IOException if the underlying stream fails
   * @serialData the <i>capacity</i> (int) that is the length of the
   *             bucket array, the <i>size</i> (int) of the hash map
   *             are emitted first.  They are followed by size entries,
   *             each consisting of a key (Object) and a value (Object).
   */
  private synchronized void writeObject(ObjectOutputStream s)
    throws IOException
  {
    // Write the threshold and loadFactor fields.
    s.defaultWriteObject();

    s.writeInt(buckets.length);
    s.writeInt(size);
    // Since we are already synchronized, and entrySet().iterator()
    // would repeatedly re-lock/release the monitor, we directly use the
    // unsynchronized EntryIterator instead.
    Iterator it = new EntryIterator();
    while (it.hasNext())
      {
        HashEntry entry = (HashEntry) it.next();
        s.writeObject(entry.key);
        s.writeObject(entry.value);
      }
  }

  /**
   * Deserializes this object from the given stream.
   *
   * @param s the stream to read from
   * @throws ClassNotFoundException if the underlying stream fails
   * @throws IOException if the underlying stream fails
   * @serialData the <i>capacity</i> (int) that is the length of the
   *             bucket array, the <i>size</i> (int) of the hash map
   *             are emitted first.  They are followed by size entries,
   *             each consisting of a key (Object) and a value (Object).
   */
  private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException
  {
    // Read the threshold and loadFactor fields.
    s.defaultReadObject();

    // Read and use capacity.
    buckets = new HashEntry[s.readInt()];
    int len = s.readInt();

    // Read and use key/value pairs.
    // TODO: should we be defensive programmers, and check for illegal nulls?
    while (--len >= 0)
      put(s.readObject(), s.readObject());
  }

  /**
   * A class which implements the Iterator interface and is used for
   * iterating over Hashtables.
   * This implementation iterates entries. Subclasses are used to
   * iterate key and values. It also allows the removal of elements,
   * as per the Javasoft spec.  Note that it is not synchronized; this
   * is a performance enhancer since it is never exposed externally
   * and is only used within synchronized blocks above.
   *
   * @author Jon Zeppieri
   * @author Fridjof Siebert
   */
  private class EntryIterator implements Iterator
  {
    /**
     * The number of modifications to the backing Hashtable that we know about.
     */
    int knownMod = modCount;
    /** The number of elements remaining to be returned by next(). */
    int count = size;
    /** Current index in the physical hash table. */
    int idx = buckets.length;
    /** The last Entry returned by a next() call. */
    HashEntry last;
    /**
     * The next entry that should be returned by next(). It is set to something
     * if we're iterating through a bucket that contains multiple linked
     * entries. It is null if next() needs to find a new bucket.
     */
    HashEntry next;

    /**
     * Construct a new EtryIterator
     */
    EntryIterator()
    {
    }


    /**
     * Returns true if the Iterator has more elements.
     * @return true if there are more elements
     * @throws ConcurrentModificationException if the hashtable was modified
     */
    public boolean hasNext()
    {
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      return count > 0;
    }

    /**
     * Returns the next element in the Iterator's sequential view.
     * @return the next element
     * @throws ConcurrentModificationException if the hashtable was modified
     * @throws NoSuchElementException if there is none
     */
    public Object next()
    {
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      if (count == 0)
        throw new NoSuchElementException();
      count--;
      HashEntry e = next;

      while (e == null)
	if (idx <= 0)
	  return null;
	else
	  e = buckets[--idx];

      next = e.next;
      last = e;
      return e;
    }

    /**
     * Removes from the backing Hashtable the last element which was fetched
     * with the <code>next()</code> method.
     * @throws ConcurrentModificationException if the hashtable was modified
     * @throws IllegalStateException if called when there is no last element
     */
    public void remove()
    {
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      if (last == null)
        throw new IllegalStateException();

      Hashtable.this.remove(last.key);
      last = null;
      knownMod++;
    }
  } // class EntryIterator

  /**
   * A class which implements the Iterator interface and is used for
   * iterating over keys in Hashtables.
   *
   * @author Fridtjof Siebert
   */
  private class KeyIterator extends EntryIterator
  {
    /**
     * Returns the next element in the Iterator's sequential view.
     *
     * @return the next element
     *
     * @throws ConcurrentModificationException if the hashtable was modified
     * @throws NoSuchElementException if there is none
     */
    public Object next()
    {
      return ((HashEntry)super.next()).key;
    }
  } // class KeyIterator



  /**
   * A class which implements the Iterator interface and is used for
   * iterating over values in Hashtables.
   *
   * @author Fridtjof Siebert
   */
  private class ValueIterator extends EntryIterator
  {
    /**
     * Returns the next element in the Iterator's sequential view.
     *
     * @return the next element
     *
     * @throws ConcurrentModificationException if the hashtable was modified
     * @throws NoSuchElementException if there is none
     */
    public Object next()
    {
      return ((HashEntry)super.next()).value;
    }
  } // class ValueIterator

  /**
   * Enumeration view of the entries in this Hashtable, providing
   * sequential access to its elements.
   *
   * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
   * as this could cause a rehash and we'd completely lose our place.  Even
   * without a rehash, it is undetermined if a new element added would
   * appear in the enumeration.  The spec says nothing about this, but
   * the "Java Class Libraries" book implies that modifications to the
   * hashtable during enumeration causes indeterminate results.  Don't do it!
   *
   * @author Jon Zeppieri
   * @author Fridjof Siebert
   */
  private class EntryEnumerator implements Enumeration
  {
    /** The number of elements remaining to be returned by next(). */
    int count = size;
    /** Current index in the physical hash table. */
    int idx = buckets.length;
    /**
     * Entry which will be returned by the next nextElement() call. It is
     * set if we are iterating through a bucket with multiple entries, or null
     * if we must look in the next bucket.
     */
    HashEntry next;

    /**
     * Construct the enumeration.
     */
    EntryEnumerator()
    {
      // Nothing to do here.
    }

    /**
     * Checks whether more elements remain in the enumeration.
     * @return true if nextElement() will not fail.
     */
    public boolean hasMoreElements()
    {
      return count > 0;
    }

    /**
     * Returns the next element.
     * @return the next element
     * @throws NoSuchElementException if there is none.
     */
    public Object nextElement()
    {
      if (count == 0)
        throw new NoSuchElementException("Hashtable Enumerator");
      count--;
      HashEntry e = next;

      while (e == null)
        if (idx <= 0)
          return null;
        else
          e = buckets[--idx];

      next = e.next;
      return e;
    }
  } // class EntryEnumerator


  /**
   * Enumeration view of this Hashtable, providing sequential access to its
   * elements.
   *
   * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
   * as this could cause a rehash and we'd completely lose our place.  Even
   * without a rehash, it is undetermined if a new element added would
   * appear in the enumeration.  The spec says nothing about this, but
   * the "Java Class Libraries" book implies that modifications to the
   * hashtable during enumeration causes indeterminate results.  Don't do it!
   *
   * @author Jon Zeppieri
   * @author Fridjof Siebert
   */
  private final class KeyEnumerator extends EntryEnumerator
  {
    /**
     * Returns the next element.
     * @return the next element
     * @throws NoSuchElementException if there is none.
     */
    public Object nextElement()
    {
      HashEntry entry = (HashEntry) super.nextElement();
      Object retVal = null;
      if (entry != null)
        retVal = entry.key;
      return retVal;
    }
  } // class KeyEnumerator


  /**
   * Enumeration view of this Hashtable, providing sequential access to its
   * values.
   *
   * <b>NOTE</b>: Enumeration is not safe if new elements are put in the table
   * as this could cause a rehash and we'd completely lose our place.  Even
   * without a rehash, it is undetermined if a new element added would
   * appear in the enumeration.  The spec says nothing about this, but
   * the "Java Class Libraries" book implies that modifications to the
   * hashtable during enumeration causes indeterminate results.  Don't do it!
   *
   * @author Jon Zeppieri
   * @author Fridjof Siebert
   */
  private final class ValueEnumerator extends EntryEnumerator
  {
    /**
     * Returns the next element.
     * @return the next element
     * @throws NoSuchElementException if there is none.
     */
    public Object nextElement()
    {
      HashEntry entry = (HashEntry) super.nextElement();
      Object retVal = null;
      if (entry != null)
        retVal = entry.value;
      return retVal;
    }
  } // class ValueEnumerator

} // class Hashtable