|
||||||||||
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.DirectAddressing<E>
goldman.collection.set.OpenAddressing<E>
public class OpenAddressing<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 |
---|
public static final double DEFAULT_LOAD
public static double A
Constructor Detail |
---|
public OpenAddressing(int capacity, double load, Comparator<? super E> equivalenceTester, Hasher<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 or load
≥ 1.0public OpenAddressing(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 or load
≥ 1.0public OpenAddressing()
public OpenAddressing(Comparator<? super E> equivalenceTester)
equivalenceTester
- the comparator defining equivalencepublic OpenAddressing(int capacity)
capacity
- the desired capacity for the setpublic OpenAddressing(int capacity, Comparator<? super E> equivalenceTester)
capacity
- the desired capacityequivalenceTester
- the comparator defining equivalencepublic OpenAddressing(int capacity, double load)
capacity
- the desired capacityload
- the desired load factor
IllegalArgumentException
- capacity
< 0 or load
≥ 1.0Method Detail |
---|
public int getCapacity()
AbstractCollection
Integer.MAX_VALUE
.
getCapacity
in interface Collection<E>
getCapacity
in class DirectAddressing<E>
protected int hash(int x)
x
- an arbitrary integer
protected int locate(E target)
target
- the element to search for
public void setTargetLoad(double load)
load
- the desired loadpublic void ensureCapacity(int desiredCapacity)
ensureCapacity
in interface Collection<E>
ensureCapacity
in class DirectAddressing<E>
desiredCapacity
- the desired capacitypublic void trimToSize()
trimToSize
in interface Collection<E>
trimToSize
in class DirectAddressing<E>
public void add(E element)
DirectAddressing
x
is in the set,
then element
replaces x
add
in interface Collection<E>
add
in class DirectAddressing<E>
element
- the element to be inserted into this setpublic boolean remove(E element)
remove
in interface Collection<E>
remove
in class DirectAddressing<E>
element
- the target
public void clear()
clear
in interface Collection<E>
clear
in class DirectAddressing<E>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |