HashMap

java.lang.Object
- ptolemy.backtrack.util.java.util.AbstractMap
- - ptolemy.backtrack.util.java.util.HashMap

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, Rollbackable, Map

Direct Known Subclasses:

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

Author:

Jon Zeppieri, Jochen Hoenicke, Bryce McKinlay, Eric Blake (ebb9@email.byu.edu)

See Also:

Object.hashCode(), Collection, Map, TreeMap, LinkedHashMap, IdentityHashMap, Hashtable, Serialized Form

Status

updated to 1.4

Nested Class Summary
- Nested classes/interfaces inherited from interface ptolemy.backtrack.util.java.util.Map
  Map.Entry

Field Summary
- Fields inherited from class ptolemy.backtrack.util.java.util.AbstractMap
  $CHECKPOINT, $RECORD$$CHECKPOINT

Constructor Summary

Constructors
Constructor and Description
`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

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`$COMMIT(long timestamp)` Commit changes up to the given timestamp, but not including changes made at timestamp and afterward.
`void`	`$RESTORE(long timestamp, boolean trim)` Restore a previous state to all the private fields of this rollbackable object.
`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.
`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.
`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.
`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.

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractMap
$GET$CHECKPOINT, $SET$CHECKPOINT, equals, hashCode, toString

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface ptolemy.backtrack.util.java.util.Map
$GET$CHECKPOINT, $SET$CHECKPOINT, equals, hashCode

- 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.
    
    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:
    
    java.lang.NullPointerException - if m is null
  - 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:
    
    java.lang.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:
    
    java.lang.IllegalArgumentException - if (initialCapacity < 0) || ! (loadFactor > 0.0)
- 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
    
    Returns:
    
    the size
    
    See Also:
    
    Set.size()
  - 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
    
    Returns:
    
    size() == 0
    
    See Also:
    
    AbstractMap.size()
  - 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
    
    Parameters:
    
    key - the key for which to fetch an associated value
    
    Returns:
    
    what the key maps to, if present
    
    See Also:
    
    put(Object, Object), containsKey(Object)
  - 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
    
    Parameters:
    
    key - the key to search for in this HashMap
    
    Returns:
    
    true if the key is in the table
    
    See Also:
    
    containsValue(Object)
  - 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
    
    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
    
    See Also:
    
    get(Object), Object.equals(Object)
  - 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
    
    Parameters:
    
    m - the map to be hashed into this
    
    See Also:
    
    AbstractMap.put(Object, Object)
  - 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
    
    Parameters:
    
    key - the key used to locate the value to remove
    
    Returns:
    
    whatever the key mapped to, if present
    
    See Also:
    
    Iterator.remove()
  - 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
    
    See Also:
    
    Set.clear()
  - 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
    
    Parameters:
    
    value - the value to search for in this HashMap
    
    Returns:
    
    true if at least one key maps to the value
    
    See Also:
    
    containsKey(Object)
  - 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
    
    Returns:
    
    the clone
    
    See Also:
    
    Cloneable, Object.clone()
  - 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
    
    Returns:
    
    a set view of the keys
    
    See Also:
    
    values(), entrySet()
  - 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
    
    Returns:
    
    a bag view of the values
    
    See Also:
    
    keySet(), entrySet()
  - 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
    
    Returns:
    
    a set view of the entries
    
    See Also:
    
    keySet(), values(), Map.Entry
  - $COMMIT
```
public void $COMMIT(long timestamp)
```
    Description copied from interface: Rollbackable
    
    Commit changes up to the given timestamp, but not including changes made at timestamp and afterward.
    
    Specified by:
    
    $COMMIT in interface Rollbackable
    
    Specified by:
    
    $COMMIT in interface Map
    
    Overrides:
    
    $COMMIT in class AbstractMap
    
    Parameters:
    
    timestamp - The timestamp.
  - $RESTORE
```
public void $RESTORE(long timestamp,
                     boolean trim)
```
    Description copied from interface: Rollbackable
    
    Restore a previous state to all the private fields of this rollbackable object.
    
    Specified by:
    
    $RESTORE in interface Rollbackable
    
    Specified by:
    
    $RESTORE in interface Map
    
    Overrides:
    
    $RESTORE in class AbstractMap
    
    Parameters:
    
    timestamp - The timestamp taken at the time when the previous state was recorded.
    
    trim - Whether to delete the records used for the rollback.
    
    See Also:
    
    Checkpoint.rollback(long, boolean)

Class HashMap

Nested Class Summary

Nested classes/interfaces inherited from interface ptolemy.backtrack.util.java.util.Map

Field Summary

Fields inherited from class ptolemy.backtrack.util.java.util.AbstractMap

Constructor Summary

Method Summary

Methods inherited from class ptolemy.backtrack.util.java.util.AbstractMap

Methods inherited from class java.lang.Object

Methods inherited from interface ptolemy.backtrack.util.java.util.Map

Constructor Detail

HashMap

HashMap

HashMap

HashMap

Method Detail

size

isEmpty

get

containsKey

put

putAll

remove

clear

containsValue

clone

keySet

values

entrySet

$COMMIT

$RESTORE