diff options
Diffstat (limited to 'libjava/classpath/java/util/HashMap.java')
| -rw-r--r-- | libjava/classpath/java/util/HashMap.java | 909 |
1 files changed, 0 insertions, 909 deletions
diff --git a/libjava/classpath/java/util/HashMap.java b/libjava/classpath/java/util/HashMap.java deleted file mode 100644 index f5194a2..0000000 --- a/libjava/classpath/java/util/HashMap.java +++ /dev/null @@ -1,909 +0,0 @@ -/* HashMap.java -- a class providing a basic hashtable data structure, - mapping Object --> Object - Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. - -This file is part of GNU Classpath. - -GNU Classpath is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. - -GNU Classpath is distributed in the hope that it will be useful, but -WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GNU Classpath; see the file COPYING. If not, write to the -Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301 USA. - -Linking this library statically or dynamically with other modules is -making a combined work based on this library. Thus, the terms and -conditions of the GNU General Public License cover the whole -combination. - -As a special exception, the copyright holders of this library give you -permission to link this library with independent modules to produce an -executable, regardless of the license terms of these independent -modules, and to copy and distribute the resulting executable under -terms of your choice, provided that you also meet, for each linked -independent module, the terms and conditions of the license of that -module. An independent module is a module which is not derived from -or based on this library. If you modify this library, you may extend -this exception to your version of the library, but you are not -obligated to do so. If you do not wish to do so, delete this -exception statement from your version. */ - - -package java.util; - -import java.io.IOException; -import java.io.ObjectInputStream; -import java.io.ObjectOutputStream; -import java.io.Serializable; - -// NOTE: This implementation is very similar to that of Hashtable. If you fix -// a bug in here, chances are you should make a similar change to the Hashtable -// code. - -// NOTE: This implementation has some nasty coding style in order to -// support LinkedHashMap, which extends this. - -/** - * This class provides a hashtable-backed implementation of the - * Map interface. - * <p> - * - * It uses a hash-bucket approach; that is, hash collisions are handled - * by linking the new node off of the pre-existing node (or list of - * nodes). In this manner, techniques such as linear probing (which - * can cause primary clustering) and rehashing (which does not fit very - * well with Java's method of precomputing hash codes) are avoided. - * <p> - * - * Under ideal circumstances (no collisions), HashMap offers O(1) - * performance on most operations (<code>containsValue()</code> is, - * of course, O(n)). In the worst case (all keys map to the same - * hash code -- very unlikely), most operations are O(n). - * <p> - * - * HashMap is part of the JDK1.2 Collections API. It differs from - * Hashtable in that it accepts the null key and null values, and it - * does not support "Enumeration views." Also, it is not synchronized; - * if you plan to use it in multiple threads, consider using:<br> - * <code>Map m = Collections.synchronizedMap(new HashMap(...));</code> - * <p> - * - * The iterators are <i>fail-fast</i>, meaning that any structural - * modification, except for <code>remove()</code> called on the iterator - * itself, cause the iterator to throw a - * <code>ConcurrentModificationException</code> rather than exhibit - * non-deterministic behavior. - * - * @author Jon Zeppieri - * @author Jochen Hoenicke - * @author Bryce McKinlay - * @author Eric Blake (ebb9@email.byu.edu) - * @see Object#hashCode() - * @see Collection - * @see Map - * @see TreeMap - * @see LinkedHashMap - * @see IdentityHashMap - * @see Hashtable - * @since 1.2 - * @status updated to 1.4 - */ -public class HashMap<K, V> extends AbstractMap<K, V> - implements Map<K, V>, Cloneable, Serializable -{ - /** - * Default number of buckets; this is currently set to 16. - * Package visible for use by HashSet. - */ - static final int DEFAULT_CAPACITY = 16; - - /** - * The default load factor; this is explicitly specified by the spec. - * Package visible for use by HashSet. - */ - static final float DEFAULT_LOAD_FACTOR = 0.75f; - - /** - * Compatible with JDK 1.2. - */ - private static final long serialVersionUID = 362498820763181265L; - - /** - * The rounded product of the capacity and the load factor; when the number - * of elements exceeds the threshold, the HashMap calls - * <code>rehash()</code>. - * @serial the threshold for rehashing - */ - private int threshold; - - /** - * Load factor of this HashMap: used in computing the threshold. - * Package visible for use by HashSet. - * @serial the load factor - */ - final float loadFactor; - - /** - * Array containing the actual key-value mappings. - * Package visible for use by nested and subclasses. - */ - transient HashEntry<K, V>[] buckets; - - /** - * Counts the number of modifications this HashMap has undergone, used - * by Iterators to know when to throw ConcurrentModificationExceptions. - * Package visible for use by nested and subclasses. - */ - transient int modCount; - - /** - * The size of this HashMap: denotes the number of key-value pairs. - * Package visible for use by nested and subclasses. - */ - transient int size; - - /** - * The cache for {@link #entrySet()}. - */ - private transient Set<Map.Entry<K, V>> entries; - - /** - * Class to represent an entry in the hash table. Holds a single key-value - * pair. Package visible for use by subclass. - * - * @author Eric Blake (ebb9@email.byu.edu) - */ - static class HashEntry<K, V> extends AbstractMap.SimpleEntry<K, V> - { - /** - * The next entry in the linked list. Package visible for use by subclass. - */ - HashEntry<K, V> next; - - /** - * Simple constructor. - * @param key the key - * @param value the value - */ - HashEntry(K key, V value) - { - super(key, value); - } - - /** - * Called when this entry is accessed via {@link #put(Object, Object)}. - * This version does nothing, but in LinkedHashMap, it must do some - * bookkeeping for access-traversal mode. - */ - void access() - { - } - - /** - * Called when this entry is removed from the map. This version simply - * returns the value, but in LinkedHashMap, it must also do bookkeeping. - * - * @return the value of this key as it is removed - */ - V cleanup() - { - return value; - } - } - - /** - * Construct a new HashMap with the default capacity (11) and the default - * load factor (0.75). - */ - public HashMap() - { - this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); - } - - /** - * Construct a new HashMap from the given Map, with initial capacity - * the greater of the size of <code>m</code> or the default of 11. - * <p> - * - * Every element in Map m will be put into this new HashMap. - * - * @param m a Map whose key / value pairs will be put into the new HashMap. - * <b>NOTE: key / value pairs are not cloned in this constructor.</b> - * @throws NullPointerException if m is null - */ - public HashMap(Map<? extends K, ? extends V> m) - { - this(Math.max(m.size() * 2, DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR); - putAll(m); - } - - /** - * Construct a new HashMap with a specific inital capacity and - * default load factor of 0.75. - * - * @param initialCapacity the initial capacity of this HashMap (>=0) - * @throws IllegalArgumentException if (initialCapacity < 0) - */ - public HashMap(int initialCapacity) - { - this(initialCapacity, DEFAULT_LOAD_FACTOR); - } - - /** - * Construct a new HashMap with a specific inital capacity and load factor. - * - * @param initialCapacity the initial capacity (>=0) - * @param loadFactor the load factor (> 0, not NaN) - * @throws IllegalArgumentException if (initialCapacity < 0) || - * ! (loadFactor > 0.0) - */ - public HashMap(int initialCapacity, float loadFactor) - { - if (initialCapacity < 0) - throw new IllegalArgumentException("Illegal Capacity: " - + initialCapacity); - if (! (loadFactor > 0)) // check for NaN too - throw new IllegalArgumentException("Illegal Load: " + loadFactor); - - if (initialCapacity == 0) - initialCapacity = 1; - buckets = (HashEntry<K, V>[]) new HashEntry[initialCapacity]; - this.loadFactor = loadFactor; - threshold = (int) (initialCapacity * loadFactor); - } - - /** - * Returns the number of kay-value mappings currently in this Map. - * - * @return the size - */ - public int size() - { - return size; - } - - /** - * Returns true if there are no key-value mappings currently in this Map. - * - * @return <code>size() == 0</code> - */ - public boolean isEmpty() - { - return size == 0; - } - - /** - * Return the value in this HashMap associated with the supplied key, - * or <code>null</code> if the key maps to nothing. NOTE: Since the value - * could also be null, you must use containsKey to see if this key - * actually maps to something. - * - * @param key the key for which to fetch an associated value - * @return what the key maps to, if present - * @see #put(Object, Object) - * @see #containsKey(Object) - */ - public V get(Object key) - { - int idx = hash(key); - HashEntry<K, V> e = buckets[idx]; - while (e != null) - { - if (equals(key, e.key)) - return e.value; - e = e.next; - } - return null; - } - - /** - * Returns true if the supplied object <code>equals()</code> a key - * in this HashMap. - * - * @param key the key to search for in this HashMap - * @return true if the key is in the table - * @see #containsValue(Object) - */ - public boolean containsKey(Object key) - { - int idx = hash(key); - HashEntry<K, V> e = buckets[idx]; - while (e != null) - { - if (equals(key, e.key)) - return true; - e = e.next; - } - return false; - } - - /** - * 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. - * - * @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) - * @see Object#equals(Object) - */ - public V put(K key, V value) - { - int idx = hash(key); - HashEntry<K, V> e = buckets[idx]; - - int hash1 = key == null ? 0 : key.hashCode(); - while (e != null) - { - int hash2 = e.key == null ? 0 : e.key.hashCode(); - - if ((hash1 == hash2) && equals(key, e.key)) - { - e.access(); // Must call this for bookkeeping in LinkedHashMap. - V 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); - } - - // LinkedHashMap cannot override put(), hence this call. - addEntry(key, value, idx, true); - return null; - } - - /** - * Copies all elements of the given map into this hashtable. 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 - */ - public void putAll(Map<? extends K, ? extends V> m) - { - final Map<K,V> addMap = (Map<K,V>) m; - final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator(); - while (it.hasNext()) - { - final Map.Entry<K,V> e = it.next(); - // Optimize in case the Entry is one of our own. - if (e instanceof AbstractMap.SimpleEntry) - { - AbstractMap.SimpleEntry<? extends K, ? extends V> entry - = (AbstractMap.SimpleEntry<? extends K, ? extends V>) e; - put(entry.key, entry.value); - } - else - put(e.getKey(), e.getValue()); - } - } - - /** - * 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. - * - * @param key the key used to locate the value to remove - * @return whatever the key mapped to, if present - */ - public V remove(Object key) - { - int idx = hash(key); - HashEntry<K, V> e = buckets[idx]; - HashEntry<K, V> last = null; - - while (e != null) - { - if (equals(key, e.key)) - { - modCount++; - if (last == null) - buckets[idx] = e.next; - else - last.next = e.next; - size--; - // Method call necessary for LinkedHashMap to work correctly. - return e.cleanup(); - } - last = e; - e = e.next; - } - return null; - } - - /** - * Clears the Map so it has no keys. This is O(1). - */ - public void clear() - { - if (size != 0) - { - modCount++; - Arrays.fill(buckets, null); - size = 0; - } - } - - /** - * Returns true if this HashMap contains a value <code>o</code>, such that - * <code>o.equals(value)</code>. - * - * @param value the value to search for in this HashMap - * @return true if at least one key maps to the value - * @see #containsKey(Object) - */ - public boolean containsValue(Object value) - { - for (int i = buckets.length - 1; i >= 0; i--) - { - HashEntry<K, V> 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<K, V> copy = null; - try - { - copy = (HashMap<K, V>) super.clone(); - } - catch (CloneNotSupportedException x) - { - // This is impossible. - } - copy.buckets = (HashEntry<K, V>[]) 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<K> keySet() - { - if (keys == null) - // Create an AbstractSet with custom implementations of those methods - // that can be overridden easily and efficiently. - keys = new AbstractSet<K>() - { - public int size() - { - return size; - } - - public Iterator<K> 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<V> 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<V>() - { - public int size() - { - return size; - } - - public Iterator<V> 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<Map.Entry<K, V>> entrySet() - { - if (entries == null) - // Create an AbstractSet with custom implementations of those methods - // that can be overridden easily and efficiently. - entries = new AbstractSet<Map.Entry<K, V>>() - { - public int size() - { - return size; - } - - public Iterator<Map.Entry<K, V>> 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<K, V> 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(K key, V value, int idx, boolean callRemove) - { - HashEntry<K, V> e = new HashEntry<K, V>(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<K, V> getEntry(Object o) - { - if (! (o instanceof Map.Entry)) - return null; - Map.Entry<K, V> me = (Map.Entry<K, V>) o; - K key = me.getKey(); - int idx = hash(key); - HashEntry<K, V> 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 - */ - <T> Iterator<T> iterator(int type) - { - // FIXME: bogus cast here. - return new HashIterator<T>(type); - } - - /** - * 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<? extends K, ? extends V> m) - { - final Map<K,V> addMap = (Map<K,V>) m; - final Iterator<Map.Entry<K,V>> it = addMap.entrySet().iterator(); - size = 0; - while (it.hasNext()) - { - final Map.Entry<K,V> e = it.next(); - size++; - K 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() > 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<K, V>[] oldBuckets = buckets; - - int newcapacity = (buckets.length * 2) + 1; - threshold = (int) (newcapacity * loadFactor); - buckets = (HashEntry<K, V>[]) new HashEntry[newcapacity]; - - for (int i = oldBuckets.length - 1; i >= 0; i--) - { - HashEntry<K, V> e = oldBuckets[i]; - while (e != null) - { - int idx = hash(e.key); - HashEntry<K, V> dest = buckets[idx]; - HashEntry<K, V> next = e.next; - e.next = buckets[idx]; - buckets[idx] = e; - 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<HashEntry<K, V>> it = iterator(ENTRIES); - while (it.hasNext()) - { - HashEntry<K, V> entry = 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 = (HashEntry<K, V>[]) new HashEntry[s.readInt()]; - int len = s.readInt(); - size = len; - while (len-- > 0) - { - Object key = s.readObject(); - addEntry((K) key, (V) 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<T> implements Iterator<T> - { - /** - * 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 - */ - public boolean hasNext() - { - 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 T 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 (T) e.value; - if (type == KEYS) - return (T) e.key; - return (T) 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++; - } - } -} |