identityhashmap.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 933 行 · 第 1/2 页

  }

  /**
   * Puts the supplied value into the Map, mapped by the supplied key.
   * The value may be retrieved by any object which <code>equals()</code>
   * this key. NOTE: Since the prior value could also be null, you must
   * first use containsKey if you want to see if you are replacing the
   * key's mapping.  Unlike normal maps, this tests for the key
   * with <code>entry == key</code> instead of
   * <code>entry == null ? key == null : entry.equals(key)</code>.
   *
   * @param key the key used to locate the value
   * @param value the value to be stored in the HashMap
   * @return the prior mapping of the key, or null if there was none
   * @see #get(Object)
   */
  public Object put(Object key, Object value)
  {
    // Rehash if the load factor is too high.
    if (size > threshold)
      {
        Object[] old = table;
        // This isn't necessarily prime, but it is an odd number of key/value
        // slots, which has a higher probability of fewer collisions.
        table = new Object[old.length << 1 + 2];
        Arrays.fill(table, emptyslot);
        size = 0;
        threshold = (table.length >>> 3) * 3;

        for (int i = old.length - 2; i >= 0; i -= 2)
          {
            Object oldkey = old[i];
            if (oldkey != tombstone && oldkey != emptyslot)
              // Just use put.  This isn't very efficient, but it is ok.
              put(oldkey, old[i + 1]);
          }
      }

    int h = hash(key);
    if (table[h] == key)
      {
        Object r = table[h + 1];
        table[h + 1] = value;
        return r;
      }

    // At this point, we add a new mapping.
    modCount++;
    size++;
    table[h] = key;
    table[h + 1] = value;
    return null;
  }

  /**
   * Copies all of the mappings from the specified map to this. If a key
   * is already in this map, its value is replaced.
   *
   * @param m the map to copy
   * @throws NullPointerException if m is null
   */
  public void putAll(Map m)
  {
    // Why did Sun specify this one? The superclass does the right thing.
    super.putAll(m);
  }

  /**
   * Removes from the HashMap and returns the value which is mapped by
   * the supplied key. If the key maps to nothing, then the HashMap
   * remains unchanged, and <code>null</code> is returned.
   *
   * NOTE: Since the value could also be null, you must use
   * containsKey to see if you are actually removing a mapping.
   * Unlike normal maps, this tests for the key with <code>entry ==
   * key</code> instead of <code>entry == null ? key == null :
   * entry.equals(key)</code>.
   *
   * @param key the key used to locate the value to remove
   * @return whatever the key mapped to, if present
   */
  public Object remove(Object key)
  {
    int h = hash(key);
    if (table[h] == key)
      {
        modCount++;
        size--;
        Object r = table[h + 1];
        table[h] = tombstone;
        table[h + 1] = tombstone;
        return r;
      }
    return null;
  }

  /**
   * Returns the number of kay-value mappings currently in this Map
   * @return the size
   */
  public int size()
  {
    return size;
  }

  /**
   * Returns a "collection view" (or "bag view") of this Map's values.
   * The collection is backed by the Map, so changes in one show up
   * in the other.  The collection supports element removal, but not element
   * addition.
   * <p>
   *
   * <em>The semantics of this set are different from the contract of
   * Collection in order to make IdentityHashMap work.  This means that
   * while you can compare these objects between IdentityHashMaps, comparing
   * them with regular sets is likely to have undefined behavior.</em>
   * Likewise, contains and remove go by == instead of equals().
   * <p>
   *
   * @return a bag view of the values
   * @see #keySet()
   * @see #entrySet()
   */
  public Collection values()
  {
    if (values == null)
      values = new AbstractCollection()
      {
        public int size()
        {
          return size;
        }

        public Iterator iterator()
        {
          return new IdentityIterator(VALUES);
        }

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

        public boolean remove(Object o)
        {
          for (int i = table.length - 1; i > 0; i -= 2)
            if (table[i] == o)
              {
                modCount++;
                table[i - 1] = tombstone;
                table[i] = tombstone;
                size--;
                return true;
              }
          return false;
        }
      };
    return values;
  }

  /**
   * Helper method which computes the hash code, then traverses the table
   * until it finds the key, or the spot where the key would go.
   *
   * @param key the key to check
   * @return the index where the key belongs
   * @see #IdentityHashMap(int)
   * @see #put(Object, Object)
   */
  // Package visible for use by nested classes.
  int hash(Object key)
  {
    // Implementation note: it is feasible for the table to have no
    // emptyslots, if it is full with entries and tombstones, so we must
    // remember where we started. If we encounter the key or an emptyslot,
    // we are done.  If we encounter a tombstone, the key may still be in
    // the array.  If we don't encounter the key, we use the first emptyslot
    // or tombstone we encountered as the location where the key would go.
    // By requiring at least 2 key/value slots, and rehashing at 75%
    // capacity, we guarantee that there will always be either an emptyslot
    // or a tombstone somewhere in the table.
    int h = Math.abs(System.identityHashCode(key) % (table.length >> 1)) << 1;
    int del = -1;
    int save = h;

    do
      {
        if (table[h] == key)
          return h;
        if (table[h] == emptyslot)
          break;
        if (table[h] == tombstone && del < 0)
          del = h;
        h -= 2;
        if (h < 0)
          h = table.length - 2;
      }
    while (h != save);

    return del < 0 ? h : del;
  }

  /**
   * This class allows parameterized iteration over IdentityHashMaps.  Based
   * on its construction, it returns the key or value of a mapping, or
   * creates the appropriate Map.Entry object with the correct fail-fast
   * semantics and identity comparisons.
   *
   * @author Tom Tromey <[e-mail]>
   * @author Eric Blake <[e-mail]>
   */
  private final class IdentityIterator implements Iterator
  {
    /**
     * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
     * or {@link #ENTRIES}.
     */
    final int type;
    /** The number of modifications to the backing Map that we know about. */
    int knownMod = modCount;
    /** The number of elements remaining to be returned by next(). */
    int count = size;
    /** Location in the table. */
    int loc = table.length;

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

    /**
     * Returns true if the Iterator has more elements.
     * @return true if there are more elements
     * @throws ConcurrentModificationException if the Map 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 Map was modified
     * @throws NoSuchElementException if there is none
     */
    public Object next()
    {
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      if (count == 0)
        throw new NoSuchElementException();
      count--;

      Object key;
      do
        {
          loc -= 2;
          key = table[loc];
        }
      while (key == emptyslot || key == tombstone);

      return type == KEYS ? key : (type == VALUES ? table[loc + 1]
                                   : new IdentityEntry(loc));
    }

    /**
     * Removes from the backing Map the last element which was fetched
     * with the <code>next()</code> method.
     *
     * @throws ConcurrentModificationException if the Map was modified
     * @throws IllegalStateException if called when there is no last element
     */
    public void remove()
    {
      if (knownMod != modCount)
        throw new ConcurrentModificationException();
      if (loc == table.length || table[loc] == tombstone)
        throw new IllegalStateException();
      modCount++;
      size--;
      table[loc] = tombstone;
      table[loc + 1] = tombstone;
      knownMod++;
    }
  } // class IdentityIterator

  /**
   * This class provides Map.Entry objects for IdentityHashMaps.  The entry
   * is fail-fast, and will throw a ConcurrentModificationException if
   * the underlying map is modified, or if remove is called on the iterator
   * that generated this object.  It is identity based, so it violates
   * the general contract of Map.Entry, and is probably unsuitable for
   * comparison to normal maps; but it works among other IdentityHashMaps.
   *
   * @author Eric Blake <[e-mail]>
   */
  private final class IdentityEntry implements Map.Entry
  {
    /** The location of this entry. */
    final int loc;
    /** The number of modifications to the backing Map that we know about. */
    final int knownMod = modCount;

    /**
     * Constructs the Entry.
     *
     * @param loc the location of this entry in table
     */
    IdentityEntry(int loc)
    {
      this.loc = loc;
    }

    /**
     * Compares the specified object with this entry, using identity
     * semantics. Note that this can lead to undefined results with
     * Entry objects created by normal maps.
     *
     * @param o the object to compare
     * @return true if it is equal
     * @throws ConcurrentModificationException if the entry was invalidated
     *         by modifying the Map or calling Iterator.remove()
     */
    public boolean equals(Object o)
    {
      if (knownMod != modCount || table[loc] == tombstone)
        throw new ConcurrentModificationException();
      if (! (o instanceof Map.Entry))
        return false;
      Map.Entry e = (Map.Entry) o;
      return table[loc] == e.getKey() && table[loc + 1] == e.getValue();
    }

    /**
     * Returns the key of this entry.
     *
     * @return the key
     * @throws ConcurrentModificationException if the entry was invalidated
     *         by modifying the Map or calling Iterator.remove()
     */
    public Object getKey()
    {
      if (knownMod != modCount || table[loc] == tombstone)
        throw new ConcurrentModificationException();
      return table[loc];
    }

    /**
     * Returns the value of this entry.
     *
     * @return the value
     * @throws ConcurrentModificationException if the entry was invalidated
     *         by modifying the Map or calling Iterator.remove()
     */
    public Object getValue()
    {
      if (knownMod != modCount || table[loc] == tombstone)
        throw new ConcurrentModificationException();
      return table[loc + 1];
    }

    /**
     * Returns the hashcode of the entry, using identity semantics.
     * Note that this can lead to undefined results with Entry objects
     * created by normal maps.
     *
     * @return the hash code
     * @throws ConcurrentModificationException if the entry was invalidated
     *         by modifying the Map or calling Iterator.remove()
     */
    public int hashCode()
    {
      if (knownMod != modCount || table[loc] == tombstone)
        throw new ConcurrentModificationException();
      return (System.identityHashCode(table[loc])
              ^ System.identityHashCode(table[loc + 1]));
    }

    /**
     * Replaces the value of this mapping, and returns the old value.
     *
     * @param value the new value
     * @return the old value
     * @throws ConcurrentModificationException if the entry was invalidated
     *         by modifying the Map or calling Iterator.remove()
     */
    public Object setValue(Object value)
    {
      if (knownMod != modCount || table[loc] == tombstone)
        throw new ConcurrentModificationException();
      Object r = table[loc + 1];
      table[loc + 1] = value;
      return r;
    }

    /**
     * This provides a string representation of the entry. It is of the form
     * "key=value", where string concatenation is used on key and value.
     *
     * @return the string representation
     * @throws ConcurrentModificationException if the entry was invalidated
     *         by modifying the Map or calling Iterator.remove()
     */
    public final String toString()
    {
      if (knownMod != modCount || table[loc] == tombstone)
        throw new ConcurrentModificationException();
      return table[loc] + "=" + table[loc + 1];
    }
  } // class IdentityEntry

  /**
   * Reads the object from a serial stream.
   *
   * @param s the stream to read from
   * @throws ClassNotFoundException if the underlying stream fails
   * @throws IOException if the underlying stream fails
   * @serialData expects the size (int), followed by that many key (Object)
   *             and value (Object) pairs, with the pairs in no particular
   *             order
   */
  private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException
  {
    s.defaultReadObject();

    int num = s.readInt();
    table = new Object[Math.max(num << 1, DEFAULT_CAPACITY) << 1];
    // Read key/value pairs.
    while (--num >= 0)
      put(s.readObject(), s.readObject());
  }

  /**
   * Writes the object to a serial stream.
   *
   * @param s the stream to write to
   * @throws IOException if the underlying stream fails
   * @serialData outputs the size (int), followed by that many key (Object)
   *             and value (Object) pairs, with the pairs in no particular
   *             order
   */
  private void writeObject(ObjectOutputStream s)
    throws IOException
  {
    s.defaultWriteObject();
    s.writeInt(size);
    for (int i = table.length - 2; i >= 0; i -= 2)
      {
        Object key = table[i];
        if (key != tombstone && key != emptyslot)
          {
            s.writeObject(key);
            s.writeObject(table[i + 1]);
          }
      }
  }
}