goldman.collection.set
Class SeparateChaining<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.set.SeparateChaining<E>
All Implemented Interfaces:
Collection<E>, Set<E>, Iterable<E>

public class SeparateChaining<E>
extends AbstractCollection<E>
implements Set<E>

This data structure should be considered when only a small fraction of the elements in U will be stored in the collection. It is the right choice in this setting when deletions occur frequently, or if n changes dramatically since it can be resized relatively infrequently. In the provided implementation, it is only resized when n grows 4-fold, which keeps the expected load within a factor of two of the desired value. If the space usage can vary even more, then without much degradation in performance, the implementation can be modified to resize less frequently. However, the space usage required for separate chaining is higher than that for the other data structures.


Nested Class Summary
static class SeparateChaining.DefaultSeparateChainingHasher<E>
          The default separate chaining hasher provides a default hasher for separate chaining that hashes null to slot 0, and uses the element's hash code for all other elements.
protected  class SeparateChaining.Marker
           
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
static double A
           
static double DEFAULT_LOAD
           
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version
 
Constructor Summary
SeparateChaining()
          Creates a new set with a default initial capacity, load, equivalence tester, and hasher.
SeparateChaining(Comparator<? super E> equivalenceTester)
          Creates a new set with a default initial capacity, load, and hasher.
SeparateChaining(int capacity)
          Creates a new set with the given capacity, and the default load, equivalence tester, and hasher.
SeparateChaining(int capacity, Comparator<? super E> equivalenceTester)
          Creates a new set with the provided capacity and equivalence tester, using the default load and hasher
SeparateChaining(int capacity, double load)
          Creates a new set with the provided capacity and load, using the default equivalence tester and hasher.
SeparateChaining(int capacity, double load, Comparator<? super E> equivalenceTester)
          Creates a hash table with the specified capacity (plus one to handle null values), and with the given comparator and default separate chaining hasher
SeparateChaining(int capacity, double load, Comparator<? super E> equivalenceTester, Hasher<? super E> hasher)
          Creates a hash table with the specified capacity (plus one to handle null values), and with the given comparator and hasher
 
Method Summary
 void add(E element)
          Inserts value into the collection in an arbitrary location.
 void clear()
          Removes all elements from the collection.
 boolean contains(E element)
          This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.
 void ensureCapacity(int desiredCapacity)
          Resizes the table (if needed), so this set can hold desiredCapacity elements at the target load factor
 int getCapacity()
          By default this method returns Integer.MAX_VALUE.
 E getEquivalentElement(E target)
          Returns an element in the collection that is equivalent to target.
 Locator<E> getLocator(E element)
          Returns a locator that has been initialized to an element equivalent to target.
protected  void growTableAsNeeded()
          Checks if the hash table is at or above its maximum allowed load, and, if so, resizes the table to accommodate the current size
 Locator<E> iterator()
          Creates a new marker that is initialized to FORE.
 boolean remove(E element)
          Removes an equivalent element (if one exists) from the set
protected  void resizeTableAsNeeded()
           
 void setTargetLoad(double load)
          Resizes the table so that it has the desired load factor
protected  void shrinkTableAsNeeded()
          Checks if the hash table is at or below its minimum allowed load, and, if so, resizes within the limitations of the last call to ensureCapacity
 void trimToSize()
          Adjust the size of the hash table so it is the minimum size needed to maintain the desired load factor.
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, compare, equivalent, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, traverseForVisitor, writeElements
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.Collection
accept, addAll, checkRep, getComparator, getSize, isEmpty, retainAll, toArray, toArray, toString
 

Field Detail

DEFAULT_LOAD

public static final double DEFAULT_LOAD
See Also:
Constant Field Values

A

public static final double A
Constructor Detail

SeparateChaining

public SeparateChaining(int capacity,
                        double load,
                        Comparator<? super E> equivalenceTester,
                        Hasher<? super E> hasher)
Creates a hash table with the specified capacity (plus one to handle null values), and with the given comparator and hasher

Parameters:
capacity - the desired capacity
load - the target load
equivalenceTester - the comparator that defines equivalence of objects
hasher - the user-supplied hash code computation
Throws:
IllegalArgumentException - capacity < 0.

SeparateChaining

public SeparateChaining(int capacity,
                        double load,
                        Comparator<? super E> equivalenceTester)
Creates a hash table with the specified capacity (plus one to handle null values), and with the given comparator and default separate chaining hasher

Parameters:
capacity - the desired capacity
load - the target load
equivalenceTester - the comparator that defines equivalence of objects
Throws:
IllegalArgumentException - capacity < 0.

SeparateChaining

public SeparateChaining()
Creates a new set with a default initial capacity, load, equivalence tester, and hasher.


SeparateChaining

public SeparateChaining(Comparator<? super E> equivalenceTester)
Creates a new set with a default initial capacity, load, and hasher.

Parameters:
equivalenceTester - the comparator defining equivalence

SeparateChaining

public SeparateChaining(int capacity)
Creates a new set with the given capacity, and the default load, equivalence tester, and hasher.

Parameters:
capacity - the desired capacity for the set

SeparateChaining

public SeparateChaining(int capacity,
                        Comparator<? super E> equivalenceTester)
Creates a new set with the provided capacity and equivalence tester, using the default load and hasher

Parameters:
capacity - the desired capacity
equivalenceTester - the comparator defining equivalence

SeparateChaining

public SeparateChaining(int capacity,
                        double load)
Creates a new set with the provided capacity and load, using the default equivalence tester and hasher.

Parameters:
capacity - the desired capacity
load - the desired load factor
Throws:
IllegalArgumentException - capacity < 0
Method Detail

getCapacity

public int getCapacity()
Description copied from class: AbstractCollection
By default this method returns Integer.MAX_VALUE.

Specified by:
getCapacity in interface Collection<E>
Overrides:
getCapacity in class AbstractCollection<E>
Returns:
the capacity of the underlying representation for the current hash table to meet the desired load factor

contains

public boolean contains(E element)
Description copied from class: AbstractCollection
This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.

Specified by:
contains in interface Collection<E>
Overrides:
contains in class AbstractCollection<E>
Parameters:
element - the target
Returns:
true if and only if an equivalent value exists in this set

getEquivalentElement

public E getEquivalentElement(E target)
Description copied from interface: Collection
Returns an element in the collection that is equivalent to target. It throws a NoSuchElementException when there is no equivalent element. The contains method should be used to determine if an element is in the collection.

Specified by:
getEquivalentElement in interface Collection<E>
Overrides:
getEquivalentElement in class AbstractCollection<E>
Parameters:
target - the target element
Returns:
an equivalent element that is in the collection
Throws:
NoSuchElementException - there is no equivalent element in the collection.

shrinkTableAsNeeded

protected void shrinkTableAsNeeded()
Checks if the hash table is at or below its minimum allowed load, and, if so, resizes within the limitations of the last call to ensureCapacity


growTableAsNeeded

protected void growTableAsNeeded()
Checks if the hash table is at or above its maximum allowed load, and, if so, resizes the table to accommodate the current size


resizeTableAsNeeded

protected void resizeTableAsNeeded()

setTargetLoad

public void setTargetLoad(double load)
Resizes the table so that it has the desired load factor

Parameters:
load - the desired load

ensureCapacity

public void ensureCapacity(int desiredCapacity)
Resizes the table (if needed), so this set can hold desiredCapacity elements at the target load factor

Specified by:
ensureCapacity in interface Collection<E>
Overrides:
ensureCapacity in class AbstractCollection<E>
Parameters:
desiredCapacity - the desired capacity

trimToSize

public void trimToSize()
Adjust the size of the hash table so it is the minimum size needed to maintain the desired load factor.

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

add

public void add(E element)
Description copied from interface: Collection
Inserts value into the collection in an arbitrary location. If a tracker is to be returned then the method addTracked which is part of the Tracked interface should be called instead. An AtCapacityException (an unchecked exception) is thrown when a bounded collection is already at capacity.

Specified by:
add in interface Collection<E>
Parameters:
element - the element to be inserted into this set

clear

public void clear()
Removes all elements from the collection.

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

remove

public boolean remove(E element)
Removes an equivalent element (if one exists) from the set

Specified by:
remove in interface Collection<E>
Parameters:
element - the target
Returns:
true if and only if the element was in the set and therefore removed.

iterator

public Locator<E> iterator()
Creates a new marker that is initialized to FORE.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Iterable<E>

getLocator

public Locator<E> getLocator(E element)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to target. Like the iterator method, this method enables navigation, but from a specified starting point. This method throws a NoSuchElementException if there is no equivalent element in the collection.

Specified by:
getLocator in interface Collection<E>
Parameters:
element - the target
Returns:
a marker initialized to the first equivalent element in the iteration order
Throws:
NoSuchElementException - there is no equivalent element in this set.