hashmap.java

this gcc-g++-3.3.1.tar.gz is a source file of gcc, you can learn more about gcc through this codes f

        HashEntry e = buckets[i];
        while (e != null)
          {
            if (equals(value, e.value))
              return true;
            e = e.next;
          }
      }
    return false;
  }

  /**
   * Returns a shallow clone of this HashMap. The Map itself is cloned,
   * but its contents are not.  This is O(n).
   *
   * @return the clone
   */
  public Object clone()
  {
    HashMap copy = null;
    try
      {
        copy = (HashMap) super.clone();
      }
    catch (CloneNotSupportedException x)
      {
        // This is impossible.
      }
    copy.buckets = new HashEntry[buckets.length];
    copy.putAllInternal(this);
    // Clear the entry cache. AbstractMap.clone() does the others.
    copy.entries = null;
    return copy;
  }

  /**
   * Returns a "set view" of this HashMap's keys. The set is backed by the
   * HashMap, so changes in one show up in the other.  The set supports
   * element removal, but not element addition.
   *
   * @return a set view of the keys
   * @see #values()
   * @see #entrySet()
   */
  public Set keySet()
  {
    if (keys == null)
      // Create an AbstractSet with custom implementations of those methods
      // that can be overridden easily and efficiently.
      keys = new AbstractSet()
      {
        public int size()
        {
          return size;
        }

        public Iterator iterator()
        {
          // Cannot create the iterator directly, because of LinkedHashMap.
          return HashMap.this.iterator(KEYS);
        }

        public void clear()
        {
          HashMap.this.clear();
        }

        public boolean contains(Object o)
        {
          return containsKey(o);
        }

        public boolean remove(Object o)
        {
          // Test against the size of the HashMap to determine if anything
          // really got removed. This is necessary because the return value
          // of HashMap.remove() is ambiguous in the null case.
          int oldsize = size;
          HashMap.this.remove(o);
          return oldsize != size;
        }
      };
    return keys;
  }

  /**
   * Returns a "collection view" (or "bag view") of this HashMap's values.
   * The collection is backed by the HashMap, so changes in one show up
   * in the other.  The collection supports element removal, but not element
   * addition.
   *
   * @return a bag view of the values
   * @see #keySet()
   * @see #entrySet()
   */
  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.
      values = new AbstractCollection()
      {
        public int size()
        {
          return size;
        }

        public Iterator iterator()
        {
          // Cannot create the iterator directly, because of LinkedHashMap.
          return HashMap.this.iterator(VALUES);
        }

        public void clear()
        {
          HashMap.this.clear();
        }
      };
    return values;
  }

  /**
   * Returns a "set view" of this HashMap's entries. The set is backed by
   * the HashMap, so changes in one show up in the other.  The set supports
   * element removal, but not element addition.<p>
   *
   * Note that the iterators for all three views, from keySet(), entrySet(),
   * and values(), traverse the HashMap in the same sequence.
   *
   * @return a set view of the entries
   * @see #keySet()
   * @see #values()
   * @see Map.Entry
   */
  public Set entrySet()
  {
    if (entries == null)
      // Create an AbstractSet with custom implementations of those methods
      // that can be overridden easily and efficiently.
      entries = new AbstractSet()
      {
        public int size()
        {
          return size;
        }

        public Iterator iterator()
        {
          // Cannot create the iterator directly, because of LinkedHashMap.
          return HashMap.this.iterator(ENTRIES);
        }

        public void clear()
        {
          HashMap.this.clear();
        }

        public boolean contains(Object o)
        {
          return getEntry(o) != null;
        }

        public boolean remove(Object o)
        {
          HashEntry e = getEntry(o);
          if (e != null)
            {
              HashMap.this.remove(e.key);
              return true;
            }
          return false;
        }
      };
    return entries;
  }

  /**
   * Helper method for put, that creates and adds a new Entry.  This is
   * overridden in LinkedHashMap for bookkeeping purposes.
   *
   * @param key the key of the new Entry
   * @param value the value
   * @param idx the index in buckets where the new Entry belongs
   * @param callRemove whether to call the removeEldestEntry method
   * @see #put(Object, Object)
   */
  void addEntry(Object key, Object value, int idx, boolean callRemove)
  {
    HashEntry e = new HashEntry(key, value);
    e.next = buckets[idx];
    buckets[idx] = e;
  }

  /**
   * Helper method for entrySet(), which matches both key and value
   * simultaneously.
   *
   * @param o the entry to match
   * @return the matching entry, if found, or null
   * @see #entrySet()
   */
  // Package visible, for use in nested classes.
  final HashEntry getEntry(Object o)
  {
    if (! (o instanceof Map.Entry))
      return null;
    Map.Entry me = (Map.Entry) o;
    Object key = me.getKey();
    int idx = hash(key);
    HashEntry e = buckets[idx];
    while (e != null)
      {
        if (equals(e.key, key))
          return equals(e.value, me.getValue()) ? e : null;
        e = e.next;
      }
    return null;
  }

  /**
   * Helper method that returns an index in the buckets array for `key'
   * based on its hashCode().  Package visible for use by subclasses.
   *
   * @param key the key
   * @return the bucket number
   */
  final int hash(Object key)
  {
    return key == null ? 0 : Math.abs(key.hashCode() % buckets.length);
  }

  /**
   * Generates a parameterized iterator.  Must be overrideable, since
   * LinkedHashMap iterates in a different order.
   *
   * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
   * @return the appropriate iterator
   */
  Iterator iterator(int type)
  {
    return new HashIterator(type);
  }

  /**
   * A simplified, more efficient internal implementation of putAll(). The 
   * Map constructor and 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();
    int msize = m.size();
    size = msize;
    while (msize-- > 0)
      {
	Map.Entry e = (Map.Entry) itr.next();
	Object key = e.getKey();
	int idx = hash(key);
	addEntry(key, e.getValue(), idx, false);
      }
  }

  /**
   * Increases the size of the HashMap and rehashes all keys to new
   * array indices; this is called when the addition of a new value
   * would cause size() &gt; 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.
   */
  private 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)
              {
                while (dest.next != null)
                  dest = 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 void writeObject(ObjectOutputStream s) throws IOException
  {
    // Write the threshold and loadFactor fields.
    s.defaultWriteObject();

    s.writeInt(buckets.length);
    s.writeInt(size);
    // Avoid creating a wasted Set by creating the iterator directly.
    Iterator it = iterator(ENTRIES);
    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, followed by key/value pairs.
    buckets = new HashEntry[s.readInt()];
    int len = s.readInt();
    while (len-- > 0)
      {
        Object key = s.readObject();
        addEntry(key, s.readObject(), hash(key), false);
      }
  }

  /**
   * Iterate over HashMap's entries.
   * This implementation is parameterized to give a sequential view of
   * keys, values, or entries.
   *
   * @author Jon Zeppieri
   */
  private final class HashIterator implements Iterator
  {
    /**
     * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
     * or {@link #ENTRIES}.
     */
    private final int type;
    /**
     * The number of modifications to the backing HashMap that we know about.
     */
    private int knownMod = modCount;
    /** The number of elements remaining to be returned by next(). */
    private int count = size;
    /** Current index in the physical hash table. */
    private int idx = buckets.length;
    /** The last Entry returned by a next() call. */
    private 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.
     */
    private HashEntry next;

    /**
     * Construct a new HashIterator with the supplied type.
     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
     */
    HashIterator(int type)
    {
      this.type = type;
    }

    /**
     * Returns true if the Iterator has more elements.
     * @return true if there are more elements
     * @throws ConcurrentModificationException if the HashMap 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 HashMap 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)
        e = buckets[--idx];

      next = e.next;
      last = e;
      if (type == VALUES)
        return e.value;
      if (type == KEYS)
        return e.key;
      return e;
    }

    /**
     * Removes from the backing HashMap the last element which was fetched
     * with the <code>next()</code> method.
     * @throws ConcurrentModificationException if the HashMap 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();

      HashMap.this.remove(last.key);
      last = null;
      knownMod++;
    }
  }
}