|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.set.SeparateChaining<E>
public class SeparateChaining<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 |
---|
public static final double DEFAULT_LOAD
public static final double A
Constructor Detail |
---|
public SeparateChaining(int capacity, double load, Comparator<? super E> equivalenceTester, Hasher<? super E> hasher)
capacity
- the desired capacityload
- the target loadequivalenceTester
- the comparator that defines equivalence of objectshasher
- the user-supplied hash code computation
IllegalArgumentException
- capacity
< 0.public SeparateChaining(int capacity, double load, Comparator<? super E> equivalenceTester)
capacity
- the desired capacityload
- the target loadequivalenceTester
- the comparator that defines equivalence of objects
IllegalArgumentException
- capacity
< 0.public SeparateChaining()
public SeparateChaining(Comparator<? super E> equivalenceTester)
equivalenceTester
- the comparator defining equivalencepublic SeparateChaining(int capacity)
capacity
- the desired capacity for the setpublic SeparateChaining(int capacity, Comparator<? super E> equivalenceTester)
capacity
- the desired capacityequivalenceTester
- the comparator defining equivalencepublic SeparateChaining(int capacity, double load)
capacity
- the desired capacityload
- the desired load factor
IllegalArgumentException
- capacity
< 0Method Detail |
---|
public int getCapacity()
AbstractCollection
Integer.MAX_VALUE
.
getCapacity
in interface Collection<E>
getCapacity
in class AbstractCollection<E>
public boolean contains(E element)
AbstractCollection
contains
takes linear time, so it
is overridden by a more efficient method in most data structure
implementations.
contains
in interface Collection<E>
contains
in class AbstractCollection<E>
element
- the target
public E getEquivalentElement(E target)
Collection
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.
getEquivalentElement
in interface Collection<E>
getEquivalentElement
in class AbstractCollection<E>
target
- the target element
NoSuchElementException
- there is no equivalent element in the
collection.protected void shrinkTableAsNeeded()
ensureCapacity
protected void growTableAsNeeded()
protected void resizeTableAsNeeded()
public void setTargetLoad(double load)
load
- the desired loadpublic void ensureCapacity(int desiredCapacity)
desiredCapacity
elements at the target load factor
ensureCapacity
in interface Collection<E>
ensureCapacity
in class AbstractCollection<E>
desiredCapacity
- the desired capacitypublic void trimToSize()
trimToSize
in interface Collection<E>
trimToSize
in class AbstractCollection<E>
public void add(E element)
Collection
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.
add
in interface Collection<E>
element
- the element to be inserted into this setpublic void clear()
clear
in interface Collection<E>
clear
in class AbstractCollection<E>
public boolean remove(E element)
remove
in interface Collection<E>
element
- the target
public Locator<E> iterator()
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public Locator<E> getLocator(E element)
Collection
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.
getLocator
in interface Collection<E>
element
- the target
NoSuchElementException
- there is no equivalent element in this set.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |