java.util

Class HashMap

Implemented Interfaces:
Cloneable, Map, Serializable
Known Direct Subclasses:
LinkedHashMap, PrinterStateReasons

public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable

This class provides a hashtable-backed implementation of the Map interface.

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.

Under ideal circumstances (no collisions), HashMap offers O(1) performance on most operations (containsValue() is, of course, O(n)). In the worst case (all keys map to the same hash code -- very unlikely), most operations are O(n).

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:
Map m = Collections.synchronizedMap(new HashMap(...));

The iterators are fail-fast, meaning that any structural modification, except for remove() called on the iterator itself, cause the iterator to throw a ConcurrentModificationException rather than exhibit non-deterministic behavior.

Since:
1.2
See Also:
Object.hashCode(), Collection, Map, TreeMap, LinkedHashMap, IdentityHashMap, Hashtable, Serialized Form

Constructor Summary

HashMap()
Construct a new HashMap with the default capacity (11) and the default load factor (0.75).
HashMap(int initialCapacity)
Construct a new HashMap with a specific inital capacity and default load factor of 0.75.
HashMap(int initialCapacity, float loadFactor)
Construct a new HashMap with a specific inital capacity and load factor.
HashMap(Map m)
Construct a new HashMap from the given Map, with initial capacity the greater of the size of m or the default of 11.

Method Summary

void
clear()
Clears the Map so it has no keys.
Object
clone()
Returns a shallow clone of this HashMap.
boolean
containsKey(Object key)
Returns true if the supplied object equals() a key in this HashMap.
boolean
containsValue(Object value)
Returns true if this HashMap contains a value o, such that o.equals(value).
Set
entrySet()
Returns a "set view" of this HashMap's entries.
Object
get(Object key)
Return the value in this HashMap associated with the supplied key, or null if the key maps to nothing.
boolean
isEmpty()
Returns true if there are no key-value mappings currently in this Map.
Set
keySet()
Returns a "set view" of this HashMap's keys.
Object
put(Object key, Object value)
Puts the supplied value into the Map, mapped by the supplied key.
void
putAll(Map m)
Copies all elements of the given map into this hashtable.
Object
remove(Object key)
Removes from the HashMap and returns the value which is mapped by the supplied key.
int
size()
Returns the number of kay-value mappings currently in this Map.
Collection
values()
Returns a "collection view" (or "bag view") of this HashMap's values.

Methods inherited from class java.util.AbstractMap

clear, clone, containsKey, containsValue, entrySet, equals, get, hashCode, isEmpty, keySet, put, putAll, remove, size, toString, values

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

HashMap

public HashMap()
Construct a new HashMap with the default capacity (11) and the default load factor (0.75).

HashMap

public HashMap(int initialCapacity)
Construct a new HashMap with a specific inital capacity and default load factor of 0.75.
Parameters:
initialCapacity - the initial capacity of this HashMap (>=0)
Throws:
IllegalArgumentException - if (initialCapacity < 0)

HashMap

public HashMap(int initialCapacity,
               float loadFactor)
Construct a new HashMap with a specific inital capacity and load factor.
Parameters:
initialCapacity - the initial capacity (>=0)
loadFactor - the load factor (> 0, not NaN)
Throws:
IllegalArgumentException - if (initialCapacity < 0) || ! (loadFactor > 0.0)

HashMap

public HashMap(Map m)
Construct a new HashMap from the given Map, with initial capacity the greater of the size of m or the default of 11.

Every element in Map m will be put into this new HashMap.

Parameters:
m - a Map whose key / value pairs will be put into the new HashMap. NOTE: key / value pairs are not cloned in this constructor.
Throws:
NullPointerException - if m is null

Method Details

clear

public void clear()
Clears the Map so it has no keys. This is O(1).
Specified by:
clear in interface Map
Overrides:
clear in interface AbstractMap

clone

public Object clone()
Returns a shallow clone of this HashMap. The Map itself is cloned, but its contents are not. This is O(n).
Overrides:
clone in interface AbstractMap
Returns:
the clone

containsKey

public boolean containsKey(Object key)
Returns true if the supplied object equals() a key in this HashMap.
Specified by:
containsKey in interface Map
Overrides:
containsKey in interface AbstractMap
Parameters:
key - the key to search for in this HashMap
Returns:
true if the key is in the table

containsValue

public boolean containsValue(Object value)
Returns true if this HashMap contains a value o, such that o.equals(value).
Specified by:
containsValue in interface Map
Overrides:
containsValue in interface AbstractMap
Parameters:
value - the value to search for in this HashMap
Returns:
true if at least one key maps to the value

entrySet

public Set entrySet()
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.

Note that the iterators for all three views, from keySet(), entrySet(), and values(), traverse the HashMap in the same sequence.

Specified by:
entrySet in interface Map
Overrides:
entrySet in interface AbstractMap
Returns:
a set view of the entries

get

public Object get(Object key)
Return the value in this HashMap associated with the supplied key, or null 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.
Specified by:
get in interface Map
Overrides:
get in interface AbstractMap
Parameters:
key - the key for which to fetch an associated value
Returns:
what the key maps to, if present

isEmpty

public boolean isEmpty()
Returns true if there are no key-value mappings currently in this Map.
Specified by:
isEmpty in interface Map
Overrides:
isEmpty in interface AbstractMap
Returns:
size() == 0

keySet

public Set keySet()
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.
Specified by:
keySet in interface Map
Overrides:
keySet in interface AbstractMap
Returns:
a set view of the keys

put

public Object put(Object key,
                  Object value)
Puts the supplied value into the Map, mapped by the supplied key. The value may be retrieved by any object which equals() 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.
Specified by:
put in interface Map
Overrides:
put in interface AbstractMap
Parameters:
key - the key used to locate the value
value - the value to be stored in the HashMap
Returns:
the prior mapping of the key, or null if there was none

putAll

public void putAll(Map m)
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.
Specified by:
putAll in interface Map
Overrides:
putAll in interface AbstractMap
Parameters:
m - the map to be hashed into this

remove

public Object remove(Object key)
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 null is returned. NOTE: Since the value could also be null, you must use containsKey to see if you are actually removing a mapping.
Specified by:
remove in interface Map
Overrides:
remove in interface AbstractMap
Parameters:
key - the key used to locate the value to remove
Returns:
whatever the key mapped to, if present

size

public int size()
Returns the number of kay-value mappings currently in this Map.
Specified by:
size in interface Map
Overrides:
size in interface AbstractMap
Returns:
the size

values

public Collection values()
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.
Specified by:
values in interface Map
Overrides:
values in interface AbstractMap
Returns:
a bag view of the values

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.