com.sun.sgs.app.util
Class ScalableHashSet<E>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractSet<E>
          extended by com.sun.sgs.app.util.ScalableHashSet<E>
Type Parameters:
E - the type of elements maintained by this set
All Implemented Interfaces:
ManagedObject, ManagedObjectRemoval, Serializable, Iterable<E>, Collection<E>, Set<E>

public class ScalableHashSet<E>
extends AbstractSet<E>
implements Serializable, ManagedObjectRemoval

A scalable implementation of Set backed by a ScalableHashMap. The internal structure of the set 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 HashSet class for use in a ManagedObject. A HashSet 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 HashSet increases, this class will perform significantly better. Developers are encouraged to profile the serialized size of their set to determine which implementation will perform better. Note that HashSet does not provide any concurrency for Tasks running in parallel that attempt to modify the set at the same time, so this class may perform better in situations where multiple tasks need to modify the set concurrently, even if the total number of elements is small. Also note that, unlike HashSet, this class can be used to store ManagedObject instances directly.

This implementation requires that all non-null elements implement Serializable. Attempting to add elements to the set that do not implement Serializable will result in an IllegalArgumentException being thrown. If an element is an instance of Serializable but does not implement ManagedObject, this class will persist the element as necessary; when such an element is removed from the set, it is also removed from the DataManager. If an element 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 set.

Applications must make sure that objects used as elements in sets of this class have equals and hashCode methods that return the same values after the elements have been serialized and deserialized. In particular, elements 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.

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 set, 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 set.

This class offers constant-time implementations of the add, remove and contains methods. 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 set, these operations may require accessing all of the entries in the set.

An instance of ScalableHashSet 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 backing map on how to perform resizing. As the set 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 set 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.

The Iterator for this class 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 iterator do not throw ConcurrentModificationException. The iterator for this class is stable with respect to the concurrent changes to the associated collection, but may ignore additions and removals made to the set during iteration.

If a call to the next method on the iterator causes a 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 null elements. This set provides no guarantees on the order of elements when iterating.

See Also:
Object.hashCode, Set, HashSet, ScalableHashMap, Serializable, ManagedObject, Serialized Form

Constructor Summary
ScalableHashSet()
          Creates an empty set; the backing ScalableHashMap has the default minimum concurrency (32).
ScalableHashSet(Collection<? extends E> c)
          Creates a new set containing the elements in the specified collection.
ScalableHashSet(int minConcurrency)
          Creates an empty set; the backing ScalableHashMap has the specified minimum concurrency.
 
Method Summary
 boolean add(E e)
          Adds the specified element to this set if it was not already present.
 void clear()
          Removes all the elements in this set.
 boolean contains(Object o)
          Returns true if this set contains the specified element.
 boolean isEmpty()
          Returns true if this set contains no elements.
 Iterator<E> iterator()
          Returns a concurrent, Serializable Iterator over the elements in this set.
 boolean remove(Object o)
          Removes the specified element from this set if it was present.
 void removingObject()
          Performs additional operations that are needed when this object is removed.
 boolean retainAll(Collection<?> c)
          Retains only the elements in this collection that are contained in the specified collection.
 int size()
          Returns the number of elements in this set.
 
Methods inherited from class java.util.AbstractSet
equals, hashCode, removeAll
 
Methods inherited from class java.util.AbstractCollection
addAll, containsAll, toArray, toArray, toString
 
Methods inherited from class java.lang.Object
getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Set
addAll, containsAll, toArray, toArray
 

Constructor Detail

ScalableHashSet

public ScalableHashSet()
Creates an empty set; the backing ScalableHashMap has the default minimum concurrency (32).

See Also:
ScalableHashMap.ScalableHashMap()

ScalableHashSet

public ScalableHashSet(int minConcurrency)
Creates an empty set; the backing ScalableHashMap has the specified minimum concurrency.

Parameters:
minConcurrency - the minimum number of concurrent write operations to support
Throws:
IllegalArgumentException - if minConcurrency is not greater than zero
See Also:
ScalableHashMap.ScalableHashMap(int)

ScalableHashSet

public ScalableHashSet(Collection<? extends E> c)
Creates a new set containing the elements in the specified collection. The new set will have the default minimum concurrency (32).

Parameters:
c - the collection of elements to be added to the set
Throws:
IllegalArgumentException - if any elements contained in the argument are not null and do not implement Serializable
Method Detail

add

public boolean add(E e)
Adds the specified element to this set if it was not already present.

Specified by:
add in interface Collection<E>
Specified by:
add in interface Set<E>
Overrides:
add in class AbstractCollection<E>
Parameters:
e - the element to be added
Returns:
true if the set did not already contain the specified element
Throws:
IllegalArgumentException - if the argument is not null and does not implement Serializable

clear

public void clear()
Removes all the elements in this set. Note that unlike HashSet, this operation is not constant time. Clearing a set takes O(n*log(n)) time.

Specified by:
clear in interface Collection<E>
Specified by:
clear in interface Set<E>
Overrides:
clear in class AbstractCollection<E>

contains

public boolean contains(Object o)
Returns true if this set contains the specified element.

Specified by:
contains in interface Collection<E>
Specified by:
contains in interface Set<E>
Overrides:
contains in class AbstractCollection<E>
Parameters:
o - the element whose presence in the set is to be tested
Returns:
true if this set contains the specified element

isEmpty

public boolean isEmpty()
Returns true if this set contains no elements.

Specified by:
isEmpty in interface Collection<E>
Specified by:
isEmpty in interface Set<E>
Overrides:
isEmpty in class AbstractCollection<E>
Returns:
true if this set contains no elements

iterator

public Iterator<E> iterator()
Returns a concurrent, Serializable Iterator over the elements in this set.

Specified by:
iterator in interface Iterable<E>
Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Set<E>
Specified by:
iterator in class AbstractCollection<E>
Returns:
an iterator over the elements in this set

remove

public boolean remove(Object o)
Removes the specified element from this set if it was present.

Specified by:
remove in interface Collection<E>
Specified by:
remove in interface Set<E>
Overrides:
remove in class AbstractCollection<E>
Parameters:
o - the element that should be removed from the set, if present
Returns:
true if the element was initially present in this set

size

public int size()
Returns the number of elements in this set. Note that unlike HashMap, this is not a constant time operation. Determining the size of a set takes O(n*log(n)).

Specified by:
size in interface Collection<E>
Specified by:
size in interface Set<E>
Specified by:
size in class AbstractCollection<E>
Returns:
the number of elements in this set

retainAll

public boolean retainAll(Collection<?> c)
Retains only the elements in this collection that are contained in the specified collection. In other words, removes from this collection all of its elements that are not contained in the specified collection.

This implementation iterates over this collection, checking each element returned by the iterator in turn to see if it's contained in the specified collection. If it's not so contained, it's removed from this collection with the iterator's remove method.

Specified by:
retainAll in interface Collection<E>
Specified by:
retainAll in interface Set<E>
Overrides:
retainAll in class AbstractCollection<E>
Parameters:
c - elements to be retained in this collection.
Returns:
true if this collection changed as a result of the call
Throws:
NullPointerException - if the specified collection is null
See Also:
remove(java.lang.Object), contains(java.lang.Object)

removingObject

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

This implementation removes the underlying ScalableHashMap.

Specified by:
removingObject in interface ManagedObjectRemoval

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

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