HashMap

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> java >> [ util overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

SOURCE |

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

java.util
Class HashMap

java.lang.Object
  java.util.AbstractMap
      java.util.HashMap

All Implemented Interfaces:: java.lang.Cloneable, Map, java.io.Serializable

Direct Known Subclasses:: LinkedHashMap

public class HashMap
extends AbstractMap
implements Map, java.lang.Cloneable, java.io.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

Nested Class Summary

(package private) static class HashMap.HashEntry
          Class to represent an entry in the hash table.

private class HashMap.HashIterator
          Iterate over HashMap's entries.

Nested classes inherited from class java.util.AbstractMap

AbstractMap.BasicMapEntry

Nested classes inherited from class java.util.Map

Map.Entry

Field Summary

(package private) HashMap.HashEntry[] buckets
          Array containing the actual key-value mappings.

(package private) static int DEFAULT_CAPACITY
          Default number of buckets.

(package private) static float DEFAULT_LOAD_FACTOR
          The default load factor; this is explicitly specified by the spec.

private Set entries
          The cache for entrySet() 55 .

(package private) float loadFactor
          Load factor of this HashMap: used in computing the threshold.

(package private) int modCount
          Counts the number of modifications this HashMap has undergone, used by Iterators to know when to throw ConcurrentModificationExceptions.

private static long serialVersionUID
          Compatible with JDK 1.2.

(package private) int size
          The size of this HashMap: denotes the number of key-value pairs.

private int threshold
          The rounded product of the capacity and the load factor; when the number of elements exceeds the threshold, the HashMap calls rehash().

Fields inherited from class java.util.AbstractMap

ENTRIES, keys, KEYS, values, VALUES

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

(package private) void addEntry(java.lang.Object key, java.lang.Object value, int idx, boolean callRemove)
          Helper method for put, that creates and adds a new Entry.

void clear()
          Clears the Map so it has no keys.

java.lang.Object clone()
          Returns a shallow clone of this HashMap.

boolean containsKey(java.lang.Object key)
          Returns true if the supplied object equals() a key in this HashMap.

boolean containsValue(java.lang.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.

java.lang.Object get(java.lang.Object key)
          Return the value in this HashMap associated with the supplied key, or null if the key maps to nothing.

(package private) HashMap.HashEntry getEntry(java.lang.Object o)
          Helper method for entrySet(), which matches both key and value simultaneously.

(package private) int hash(java.lang.Object key)
          Helper method that returns an index in the buckets array for `key' based on its hashCode().

boolean isEmpty()
          Returns true if there are no key-value mappings currently in this Map.

(package private) Iterator iterator(int type)
          Generates a parameterized iterator.

Set keySet()
          Returns a "set view" of this HashMap's keys.

java.lang.Object put(java.lang.Object key, java.lang.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.

(package private) void putAllInternal(Map m)
          A simplified, more efficient internal implementation of putAll().

private void readObject(java.io.ObjectInputStream s)
          Deserializes this object from the given stream.

private void rehash()
          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.

java.lang.Object remove(java.lang.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.

private void writeObject(java.io.ObjectOutputStream s)
          Serializes this object to the given stream.

Methods inherited from class java.util.AbstractMap

equals, equals, hashCode, hashCode, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

equals, hashCode

Field Detail

DEFAULT_CAPACITY

static final int DEFAULT_CAPACITY

Default number of buckets. This is the value the JDK 1.3 uses. Some early documentation specified this value as 101. That is incorrect. Package visible for use by HashSet.

See Also:: Constant Field Values

DEFAULT_LOAD_FACTOR

static final float DEFAULT_LOAD_FACTOR

The default load factor; this is explicitly specified by the spec. Package visible for use by HashSet.

See Also:: Constant Field Values

serialVersionUID

private static final long serialVersionUID

Compatible with JDK 1.2.

See Also:: Constant Field Values

threshold

private int threshold

The rounded product of the capacity and the load factor; when the number of elements exceeds the threshold, the HashMap calls rehash().

loadFactor

final float loadFactor

Load factor of this HashMap: used in computing the threshold. Package visible for use by HashSet.

buckets

transient HashMap.HashEntry[] buckets

Array containing the actual key-value mappings. Package visible for use by nested and subclasses.

modCount

transient int modCount

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.

size

transient int size

The size of this HashMap: denotes the number of key-value pairs. Package visible for use by nested and subclasses.

entries

private transient Set entries

The cache for entrySet() 55 .

Constructor Detail

HashMap

public HashMap()

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

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.

HashMap

public HashMap(int initialCapacity)

Construct a new HashMap with a specific inital capacity and default load factor of 0.75.

HashMap

public HashMap(int initialCapacity,
               float loadFactor)

Construct a new HashMap with a specific inital capacity and load factor.

Method Detail

size

public int size()

Returns the number of kay-value mappings currently in this Map.

Specified by:: size in interface Map
Overrides:: size in class AbstractMap

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 class AbstractMap

get

public java.lang.Object get(java.lang.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 class AbstractMap

containsKey

public boolean containsKey(java.lang.Object key)

Returns true if the supplied object equals() a key in this HashMap.

Specified by:: containsKey in interface Map
Overrides:: containsKey in class AbstractMap

put

public java.lang.Object put(java.lang.Object key,
                            java.lang.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 class AbstractMap

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 class AbstractMap

remove

public java.lang.Object remove(java.lang.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 class AbstractMap

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 class AbstractMap

containsValue

public boolean containsValue(java.lang.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 class AbstractMap

clone

public java.lang.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 class AbstractMap

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 class AbstractMap

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 class AbstractMap

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
Specified by:: entrySet in class AbstractMap

addEntry

void addEntry(java.lang.Object key,
              java.lang.Object value,
              int idx,
              boolean callRemove)

Helper method for put, that creates and adds a new Entry. This is overridden in LinkedHashMap for bookkeeping purposes.

getEntry

final HashMap.HashEntry getEntry(java.lang.Object o)

Helper method for entrySet(), which matches both key and value simultaneously.

hash

final int hash(java.lang.Object key)

Helper method that returns an index in the buckets array for `key' based on its hashCode(). Package visible for use by subclasses.

iterator

Iterator iterator(int type)

Generates a parameterized iterator. Must be overrideable, since LinkedHashMap iterates in a different order.

putAllInternal

void putAllInternal(Map m)

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.

rehash

private void rehash()

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.

This is not specified, but the new size is twice the current size plus one; this number is not always prime, unfortunately.

writeObject

private void writeObject(java.io.ObjectOutputStream s)
                  throws java.io.IOException

Serializes this object to the given stream.

readObject

private void readObject(java.io.ObjectInputStream s)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException

Deserializes this object from the given stream.

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> java >> [ util overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

SOURCE |

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

Nested Class Summary
`(package private) static class`	`HashMap.HashEntry` Class to represent an entry in the hash table.
`private class`	`HashMap.HashIterator` Iterate over HashMap's entries.

Field Summary
`(package private) HashMap.HashEntry[]`	`buckets` Array containing the actual key-value mappings.
`(package private) static int`	`DEFAULT_CAPACITY` Default number of buckets.
`(package private) static float`	`DEFAULT_LOAD_FACTOR` The default load factor; this is explicitly specified by the spec.
`private Set`	`entries` The cache for `entrySet()` 55 .
`(package private) float`	`loadFactor` Load factor of this HashMap: used in computing the threshold.
`(package private) int`	`modCount` Counts the number of modifications this HashMap has undergone, used by Iterators to know when to throw ConcurrentModificationExceptions.
`private static long`	`serialVersionUID` Compatible with JDK 1.2.
`(package private) int`	`size` The size of this HashMap: denotes the number of key-value pairs.
`private int`	`threshold` The rounded product of the capacity and the load factor; when the number of elements exceeds the threshold, the HashMap calls `rehash()`.

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
`(package private) void`	`addEntry(java.lang.Object key, java.lang.Object value, int idx, boolean callRemove)` Helper method for put, that creates and adds a new Entry.
`void`	`clear()` Clears the Map so it has no keys.
`java.lang.Object`	`clone()` Returns a shallow clone of this HashMap.
`boolean`	`containsKey(java.lang.Object key)` Returns true if the supplied object `equals()` a key in this HashMap.
`boolean`	`containsValue(java.lang.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.
`java.lang.Object`	`get(java.lang.Object key)` Return the value in this HashMap associated with the supplied key, or `null` if the key maps to nothing.
`(package private) HashMap.HashEntry`	`getEntry(java.lang.Object o)` Helper method for entrySet(), which matches both key and value simultaneously.
`(package private) int`	`hash(java.lang.Object key)` Helper method that returns an index in the buckets array for `key' based on its hashCode().
`boolean`	`isEmpty()` Returns true if there are no key-value mappings currently in this Map.
`(package private) Iterator`	`iterator(int type)` Generates a parameterized iterator.
`Set`	`keySet()` Returns a "set view" of this HashMap's keys.
`java.lang.Object`	`put(java.lang.Object key, java.lang.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.
`(package private) void`	`putAllInternal(Map m)` A simplified, more efficient internal implementation of putAll().
`private void`	`readObject(java.io.ObjectInputStream s)` Deserializes this object from the given stream.
`private void`	`rehash()` 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.
`java.lang.Object`	`remove(java.lang.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.
`private void`	`writeObject(java.io.ObjectOutputStream s)` Serializes this object to the given stream.

java.util Class HashMap

DEFAULT_CAPACITY

DEFAULT_LOAD_FACTOR

serialVersionUID

threshold

loadFactor

buckets

modCount

size

entries

HashMap

HashMap

HashMap

HashMap

size

isEmpty

get

containsKey

put

putAll

remove

clear

containsValue

clone

keySet

values

entrySet

addEntry

getEntry

hash

iterator

putAllInternal

rehash

writeObject

readObject

java.util
Class HashMap