com.sun.sgs.app.util
Class ScalableHashMap<K,V>

java.lang.Object
  extended by java.util.AbstractMap<K,V>
      extended by com.sun.sgs.app.util.ScalableHashMap<K,V>
Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values
All Implemented Interfaces:
ManagedObject, ManagedObjectRemoval, Serializable, Map<K,V>

public class ScalableHashMap<K,V>
extends AbstractMap<K,V>
implements Serializable, ManagedObjectRemoval

A scalable implementation of Map. The internal structure of the map is separated into distributed pieces, which reduces the amount of data any one operation needs to access. The distributed structure increases the concurrency and allows for parallel write operations to successfully complete.

Developers may use this class as a drop-in replacement for the HashMap class for use in a ManagedObject. A HashMap will typically perform better than this class when the number of mappings is small, the objects being stored are small, and minimal concurrency is required. As the size of the serialized HashMap increases, this class will perform significantly better. Developers are encouraged to profile the serialized size of their map to determine which implementation will perform better. Note that HashMap does not provide any concurrency for Tasks running in parallel that attempt to modify the map at the same time, so this class may perform better in situations where multiple tasks need to modify the map concurrently, even if the total number of mappings is small. Also note that, unlike HashMap, this class can be used to store ManagedObject instances directly.

This implementation requires that all non-null keys and values implement Serializable. Attempting to add keys or values to the map that do not implement Serializable will result in an IllegalArgumentException being thrown. If a key or value is an instance of Serializable but does not implement ManagedObject, this class will persist the object as necessary; when such an object is removed from the map, it is also removed from the DataManager. If a key or value is an instance of ManagedObject, the developer will be responsible for removing these objects from the DataManager when done with them. Developers should not remove these object from the DataManager prior to removing them from the map.

Applications must make sure that objects used as keys in maps of this class have equals and hashCode methods that return the same values after the keys have been serialized and deserialized. In particular, keys that use Object.equals and Object.hashCode will typically not be equal, and will have different hash codes, each time they are deserialized, and so are probably not suitable for use with this class. The same requirements apply to objects used as values if the application intends to use containsValue or to compare map entries.

This class marks itself for update as necessary; no additional calls to the DataManager are necessary when modifying the map. Developers do not need to call markForUpdate or getForUpdate on this map, as this will eliminate all the concurrency benefits of this class. However, calling getForUpdate or markForUpdate can be used if a operation needs to prevent all access to the map.

Note that, unlike most collections, the size and isEmpty methods for this class are not constant-time operations. Because of the asynchronous nature of the map, these operations may require accessing all of the entries in the map.

An instance of ScalableHashMap offers one parameter for performance tuning: minConcurrency, which specifies the minimum number of write operations to support in parallel. This parameter acts as a hint to the map on how to perform resizing. As the map grows, the number of supported parallel operations will also grow beyond the specified minimum. Setting the minimum concurrency too high will waste space and time, while setting it too low will cause conflicts until the map grows sufficiently to support more concurrent operations.

Since the expected distribution of objects in the map is essentially random, the actual concurrency will vary. Developers are strongly encouraged to use hash codes that provide a normal distribution; a large number of collisions will likely reduce the performance.

This class provides Serializable views from the entrySet, keySet and values methods. These views may be shared and persisted by multiple ManagedObject instances.

The Iterator for each view also implements Serializable. A single iterator may be saved by different ManagedObject instances, which will create distinct copies of the original iterator. A copy starts its iteration from where the state of the original was at the time of the copy. However, each copy maintains a separate, independent state from the original and will therefore not reflect any changes to the original iterator. To share a single Iterator between multiple ManagedObject and have the iterator use a consistent view for each, the iterator should be contained within a shared ManagedObject.

The iterators do not throw ConcurrentModificationException. The iterators are stable with respect to concurrent changes to the associated collection, but may ignore additions and removals made to the collection during iteration, and may also visit more than once a key value that is removed and re-added. Attempting to use an iterator when the associated map has been removed from the DataManager will result in an ObjectNotFoundException being thrown, although the remove method may throw IllegalStateException instead if that is appropriate.

If a call to the next method on the iterators causes an ObjectNotFoundException to be thrown because the return value has been removed from the DataManager, the iterator will still have successfully moved to the next entry in its iteration. In this case, the remove method may be called on the iterator to remove the current object even though that object could not be returned.

This class and its iterator implement all optional operations and support both null keys and values. This map provides no guarantees on the order of elements when iterating over the key set, values or entry set.

See Also:
Object.hashCode, Map, Serializable, ManagedObject, Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>
 
Nested classes/interfaces inherited from interface java.util.Map
Map.Entry<K,V>
 
Constructor Summary
ScalableHashMap()
          Constructs an empty map with the default minimum concurrency (32).
ScalableHashMap(int minConcurrency)
          Creates an empty map with the specified minimum concurrency.
ScalableHashMap(Map<? extends K,? extends V> map)
          Constructs a new map with the same mappings as the specified Map, and the default minimum concurrency (32).
 
Method Summary
 void clear()
          Clears the map of all entries.
 boolean containsKey(Object key)
          
 boolean containsValue(Object value)
           Note that the execution time of this method grows substantially as the map size increases due to the cost of accessing the data manager.
 Set<Map.Entry<K,V>> entrySet()
          Returns a concurrent, Serializable Set of all the mappings contained in this map.
 V get(Object key)
          Returns the value to which this key is mapped or null if the map contains no mapping for this key.
 boolean isEmpty()
          Returns whether this map has no mappings.
 Set<K> keySet()
          Returns a concurrent, Serializable Set of all the keys contained in this map.
 V put(K key, V value)
          Associates the specified key with the provided value and returns the previous value if the key was previous mapped.
 void putAll(Map<? extends K,? extends V> m)
          Copies all of the mappings from the provided map into this map.
 V remove(Object key)
          Removes the mapping for the specified key from this map if present.
 void removingObject()
          Performs additional operations that are needed when this object is removed.
 int size()
          Returns the size of the tree.
 Collection<V> values()
          Returns a concurrent, Serializable Collection of all the values contained in this map.
 
Methods inherited from class java.util.AbstractMap
equals, hashCode, toString
 
Methods inherited from class java.lang.Object
getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

ScalableHashMap

public ScalableHashMap(int minConcurrency)
Creates an empty map with the specified minimum concurrency.

Parameters:
minConcurrency - the minimum number of concurrent write operations to support
Throws:
IllegalArgumentException - if minConcurrency is not greater than zero

ScalableHashMap

public ScalableHashMap()
Constructs an empty map with the default minimum concurrency (32).


ScalableHashMap

public ScalableHashMap(Map<? extends K,? extends V> map)
Constructs a new map with the same mappings as the specified Map, and the default minimum concurrency (32).

Parameters:
map - the mappings to include
Throws:
IllegalArgumentException - if any of the keys or values contained in the argument are not null and do not implement Serializable
Method Detail

clear

public void clear()
Clears the map of all entries. When clearing, all non-ManagedObject keys and values persisted by this map will be removed from the DataManager.

Specified by:
clear in interface Map<K,V>
Overrides:
clear in class AbstractMap<K,V>

containsKey

public boolean containsKey(Object key)

Specified by:
containsKey in interface Map<K,V>
Overrides:
containsKey in class AbstractMap<K,V>

containsValue

public boolean containsValue(Object value)
Note that the execution time of this method grows substantially as the map size increases due to the cost of accessing the data manager.

Specified by:
containsValue in interface Map<K,V>
Overrides:
containsValue in class AbstractMap<K,V>

get

public V get(Object key)
Returns the value to which this key is mapped or null if the map contains no mapping for this key. Note that the return value of null does not necessarily imply that no mapping for this key existed since this implementation supports null values. The containsKey method can be used to determine whether a mapping exists.

Specified by:
get in interface Map<K,V>
Overrides:
get in class AbstractMap<K,V>
Parameters:
key - the key whose mapped value is to be returned
Returns:
the value mapped to the provided key or null if no such mapping exists
Throws:
ObjectNotFoundException - if the value associated with the key has been removed from the DataManager

put

public V put(K key,
             V value)
Associates the specified key with the provided value and returns the previous value if the key was previous mapped. This map supports both null keys and values.

If the value currently associated with key has been removed from the DataManager, then an ObjectNotFoundException will be thrown and the mapping will not be changed.

Specified by:
put in interface Map<K,V>
Overrides:
put in class AbstractMap<K,V>
Parameters:
key - the key
value - the value to be mapped to the key
Returns:
the previous value mapped to the provided key, if any
Throws:
IllegalArgumentException - if either key or value is not null and does not implement Serializable
ObjectNotFoundException - if the previous value associated with the key has been removed from the DataManager

putAll

public void putAll(Map<? extends K,? extends V> m)
Copies all of the mappings from the provided map into this map. This operation will replace any mappings for keys currently in the map if they occur in both this map and the provided map.

Specified by:
putAll in interface Map<K,V>
Overrides:
putAll in class AbstractMap<K,V>
Parameters:
m - the map to be copied
Throws:
IllegalArgumentException - if any of the keys or values contained in the argument are not null and do not implement Serializable. If this exception is thrown, some of the entries from the argument may have already been added to this map.

isEmpty

public boolean isEmpty()
Returns whether this map has no mappings.

Specified by:
isEmpty in interface Map<K,V>
Overrides:
isEmpty in class AbstractMap<K,V>
Returns:
true if this map contains no mappings

size

public int size()
Returns the size of the tree. Note that this implementation runs in O(n*log(n)) time. Developers should be cautious of calling this method on large maps, as the execution time grows significantly.

Developers can avoid possible scaling problems by using an iterator to count the number of elements in the tree, but counting only a few elements before scheduling the rest of the job as a task to be performed by the task scheduler.

Specified by:
size in interface Map<K,V>
Overrides:
size in class AbstractMap<K,V>
Returns:
the size of the tree

remove

public V remove(Object key)
Removes the mapping for the specified key from this map if present.

If the value currently associated with key has been removed from the DataManager, then an ObjectNotFoundException will be thrown and the mapping will not be removed.

Specified by:
remove in interface Map<K,V>
Overrides:
remove in class AbstractMap<K,V>
Parameters:
key - key whose mapping is to be removed from the map
Returns:
the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.)
Throws:
ObjectNotFoundException - if the value associated with the key has been removed from the DataManager

removingObject

public void removingObject()
Performs additional operations that are needed when this object is removed.

This implementation removes from the DataManager all non-ManagedObject keys and values persisted by this map, as well as objects that make up the internal structure of the map itself.

Specified by:
removingObject in interface ManagedObjectRemoval

entrySet

public Set<Map.Entry<K,V>> entrySet()
Returns a concurrent, Serializable Set of all the mappings contained in this map. The returned Set is backed by the map, so changes to the map will be reflected by this view. Note that the time complexity of the operations on this set will be the same as those on the map itself.

The iterator returned by this set also implements Serializable. See the javadoc for details.

Specified by:
entrySet in interface Map<K,V>
Specified by:
entrySet in class AbstractMap<K,V>
Returns:
the set of all mappings contained in this map

keySet

public Set<K> keySet()
Returns a concurrent, Serializable Set of all the keys contained in this map. The returned Set is backed by the map, so changes to the map will be reflected by this view. Note that the time complexity of the operations on this set will be the same as those on the map itself.

The iterator returned by this set also implements Serializable. See the javadoc for details.

Specified by:
keySet in interface Map<K,V>
Overrides:
keySet in class AbstractMap<K,V>
Returns:
the set of all keys contained in this map

values

public Collection<V> values()
Returns a concurrent, Serializable Collection of all the values contained in this map. The returned Collection is backed by the map, so changes to the map will be reflected by this view. Note that the time complexity of the operations on this set will be the same as those on the map itself.

The iterator returned by this set also implements Serializable. See the javadoc for details.

Specified by:
values in interface Map<K,V>
Overrides:
values in class AbstractMap<K,V>
Returns:
the collection of all values contained in this map

Project Darkstar, Version 0.9.9.6
2009-05-08 15:39:40

Copyright © 2007-2009 Sun Microsystems, Inc. All rights reserved