goldman.collection.set
Class OpenAddressing<E>

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

public class OpenAddressing<E>
extends DirectAddressing<E>
implements Set<E>

This data structure should also be considered when only a small fraction of the elements in the universe will be stored in the collection. As compared with separate chaining, for the same space usage, the primary methods generally run faster. However, the computation costs of the primary methods grow as the number of deletions grows. If deletions are frequent, then separate chaining (or if applicable, direct addressing) should be considered. Also, as compared with separate chaining, resizing must be performed more frequently if the capacity provided in the constructor (or via ensureCapacity) is not adequate.


Nested Class Summary
static class OpenAddressing.DefaultOpenAddressingHasher<E>
          The default open addressing hasher provides a default hasher for open addressing that hashes null to slot 0, and uses the element's hash code for all other elements.
 
Nested classes/interfaces inherited from class goldman.collection.set.DirectAddressing
DirectAddressing.DirectAddressingHasher<E>, DirectAddressing.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
OpenAddressing()
          Creates a new set with a default initial capacity, load, equivalence tester, and hasher.
OpenAddressing(Comparator<? super E> equivalenceTester)
          Creates a new set with a default initial capacity, load, and hasher.
OpenAddressing(int capacity)
          Creates a new set with the given capacity, and the default load, equivalence tester, and hasher.
OpenAddressing(int capacity, Comparator<? super E> equivalenceTester)
          Creates a new set with the provided capacity and equivalence tester, using the default load and hasher
OpenAddressing(int capacity, double load)
          Creates a new set with the provided capacity and load, using the default equivalence tester and hasher.
OpenAddressing(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 open addressing hasher
OpenAddressing(int capacity, double load, Comparator<? super E> equivalenceTester, Hasher<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)
          If an equivalent element x is in the set, then element replaces x
 void clear()
          Removes all elements from the collection.
 void ensureCapacity(int desiredCapacity)
          Resizes the table if necessary so that it has the desired capacity
 int getCapacity()
          By default this method returns Integer.MAX_VALUE.
protected  int hash(int x)
           
protected  int locate(E target)
           
 boolean remove(E element)
          Removes an equivalent element (if one exists) from the set
 void setTargetLoad(double load)
          Resizes the table so that it has the desired load factor
 void trimToSize()
          Adjusts the size of the hash table so that the desired load factor is met as long as this does not increase the hash table size.
 
Methods inherited from class goldman.collection.set.DirectAddressing
contains, getEquivalentElement, getLocator, iterator
 
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, contains, getComparator, getEquivalentElement, getLocator, getSize, isEmpty, iterator, retainAll, toArray, toArray, toString
 

Field Detail

DEFAULT_LOAD

public static final double DEFAULT_LOAD
See Also:
Constant Field Values

A

public static double A
Constructor Detail

OpenAddressing

public OpenAddressing(int capacity,
                      double load,
                      Comparator<? super E> equivalenceTester,
                      Hasher<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 or load ≥ 1.0

OpenAddressing

public OpenAddressing(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 open addressing hasher

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

OpenAddressing

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


OpenAddressing

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

Parameters:
equivalenceTester - the comparator defining equivalence

OpenAddressing

public OpenAddressing(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

OpenAddressing

public OpenAddressing(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

OpenAddressing

public OpenAddressing(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 or load ≥ 1.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 DirectAddressing<E>
Returns:
the capacity of the underlying representation for the current hash table to meet the desired load factor

hash

protected int hash(int x)
Parameters:
x - an arbitrary integer
Returns:
an integer between 0 and m-1

locate

protected int locate(E target)
Parameters:
target - the element to search for
Returns:
the slot referencing an equivalent element to target, or the insert position if no equivalent element is in the set.

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 necessary so that it has the desired capacity

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

trimToSize

public void trimToSize()
Adjusts the size of the hash table so that the desired load factor is met as long as this does not increase the hash table size.

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

add

public void add(E element)
Description copied from class: DirectAddressing
If an equivalent element x is in the set, then element replaces x

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

remove

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

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

clear

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

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