|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object nz.ac.waikato.jdsl.core.ref.AbstractDictionary nz.ac.waikato.jdsl.core.ref.HashtableDictionary
public class HashtableDictionary
An implementation of Dictionary using a chaining hashtable. Elements are inserted at the front of each chain, to ensure a constant time bound (disregarding resizing overhead).
The chains have references to both the next and previous element in the chains to make remove(Locator) guaranteed constant time (again, disregarding resizing overhead).
In the time complexities listed for the methods, O(1) is constant time, O(N) is time proportional to the number of elements in the data structure, and O(C) is time proportional to the capacity of the data structure.
Nested Class Summary |
---|
Nested classes/interfaces inherited from interface nz.ac.waikato.jdsl.core.api.InspectableDictionary |
---|
InspectableDictionary.InvalidLocator |
Field Summary |
---|
Fields inherited from interface nz.ac.waikato.jdsl.core.api.InspectableDictionary |
---|
NO_SUCH_KEY |
Constructor Summary | |
---|---|
HashtableDictionary(HashComparator comp)
This constructor takes a Comparator which can determine if it can compare a key, and if two keys are equal, nothing more. |
|
HashtableDictionary(HashComparator comp,
int initCap)
This constructor takes a Comparator which can determine if it can compare a key, and if two keys are equal, nothing more, and an integer denoting the initial capacity. |
Method Summary | |
---|---|
boolean |
contains(Accessor acc)
O(1) |
ObjectIterator |
elements()
O(1) if structure *AND* elements haven't changed, O(N) otherwise. |
Locator |
find(java.lang.Object key)
O(1) -- expected, O(N) worst case with excessive chaining. |
LocatorIterator |
findAll(java.lang.Object key)
O(#elts with target key), worst case O(N) |
Locator |
insert(java.lang.Object key,
java.lang.Object value)
O(1) expected, O(N) if insertion pushes the size above the rehashing threshhold. |
boolean |
isEmpty()
O(1) |
ObjectIterator |
keys()
O(1) if structure hasn't changed, O(N) otherwise. |
LocatorIterator |
locators()
O(1) if structure hasn't changed, O(N) otherwise. |
Container |
newContainer()
O(1) |
void |
remove(Locator loc)
O(1) expected: strictly O(1) unless removal reduces size below the downhashing threshhold, in which case it is O(N) |
LocatorIterator |
removeAll(java.lang.Object key)
O(#elts with target key) expected, worst case O(N) with excessive chaining, or if removeAll drops the size below the downhashing threshhold. |
Locator |
removeKey(java.lang.Object key)
Removes the first element found with the given key from the hashtable. |
java.lang.Object |
replaceElement(Accessor acc,
java.lang.Object Element)
O(1) |
java.lang.Object |
replaceKey(Locator loc,
java.lang.Object key)
O(1) |
int |
size()
O(1) |
java.lang.String |
toString()
O(N) human readable description of the contents of this dictionary, conforming to the Collections spec for key-element structures. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public HashtableDictionary(HashComparator comp)
public HashtableDictionary(HashComparator comp, int initCap)
Method Detail |
---|
public final int size()
size
in interface InspectableContainer
public boolean isEmpty()
isEmpty
in interface InspectableContainer
true
if and only if the container is empty (holds
no elements)InspectableBinaryTree
public java.lang.Object replaceElement(Accessor acc, java.lang.Object Element)
replaceElement
in interface Container
acc
- Accessor in this containerElement
- to be stored at a
public Container newContainer()
newContainer
in interface Container
public boolean contains(Accessor acc)
contains
in interface InspectableContainer
public void remove(Locator loc) throws InvalidAccessorException
remove
in interface KeyBasedContainer
loc
- a locator in the container to remove
InvalidAccessorException
- if the locator is not valid or
is not contained by this containerpublic java.lang.Object replaceKey(Locator loc, java.lang.Object key)
replaceKey
in interface KeyBasedContainer
loc
- the locator in the container whose key should be replacedkey
- the new key to associate with loc
.
public LocatorIterator locators()
locators
in interface InspectableKeyBasedContainer
public ObjectIterator keys()
keys
in interface InspectableKeyBasedContainer
public ObjectIterator elements()
elements
in interface InspectableContainer
public LocatorIterator findAll(java.lang.Object key) throws InvalidKeyException
findAll
in interface InspectableDictionary
key
- The key to search for.
InvalidKeyException
- if the specified key is not valid in
this containerpublic LocatorIterator removeAll(java.lang.Object key)
removeAll
in interface Dictionary
key
- the key to search for
public Locator removeKey(java.lang.Object key) throws InvalidKeyException
InvalidKeyException
- if the key cannot be comparedpublic Locator insert(java.lang.Object key, java.lang.Object value) throws InvalidKeyException
insert
in interface KeyBasedContainer
key
- the key associated with the specified element.value
- the element to insert into the container.
InvalidKeyException
- if key
cannot be used
by this containerpublic Locator find(java.lang.Object key) throws InvalidKeyException
find
in interface InspectableDictionary
key
- The key mapped to search for.
Locator
referring to the key-element pair
that was found, or NO_SUCH_KEY if it could not be found.
InvalidKeyException
- if the specified key is not a valid
key in this container.InspectableDictionary.NO_SUCH_KEY
public java.lang.String toString()
toString
in class java.lang.Object
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |