jdsl.core.ref
Class HashtableDictionary

java.lang.Object
  jdsl.core.ref.AbstractDictionary
      jdsl.core.ref.HashtableDictionary

All Implemented Interfaces:

Container, Dictionary, InspectableContainer, InspectableDictionary, InspectableKeyBasedContainer, KeyBasedContainer, Serializable

public class HashtableDictionary

extends AbstractDictionary

implements Dictionary, Serializable

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.

Version:

JDSL 2.1.1

Author:

Mike Boilen (mgb) , Benoit Hudson (bh) , Ryan Shaun Baker (rsb) , Keith Schmidt (kas)

Nested Class Summary

Nested classes inherited from class jdsl.core.api.InspectableDictionary

InspectableDictionary.InvalidLocator

Field Summary

Fields inherited from interface 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(Object key) O(1) -- expected, O(N) worst case with excessive chaining.
LocatorIterator	findAll(Object key) O(#elts with target key), worst case O(N)
Locator	insert(Object key, 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(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(Object key) Removes the first element found with the given key from the hashtable.
Object	replaceElement(Accessor acc, Object Element) O(1)
Object	replaceKey(Locator loc, Object key) O(1)
int	size() O(1)
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

HashtableDictionary

public 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

public 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 Detail

size

public final int size()

O(1)

Specified by:

size in interface InspectableContainer

Returns:

Number of elements stored by the container.

isEmpty

public boolean isEmpty()

O(1)

Specified by:

isEmpty in interface InspectableContainer

Returns:

true if and only if the container is empty (holds no elements)

See Also:

InspectableBinaryTree

replaceElement

public Object replaceElement(Accessor acc,
                             Object Element)

O(1)

Specified by:

replaceElement in interface Container

Parameters:

acc - Accessor in this container

Element - to be stored at a

Returns:

old element, previously stored at a

newContainer

public Container newContainer()

O(1)

Specified by:

newContainer in interface Container

Returns:

A new, empty Container of the same class as this one.

contains

public boolean contains(Accessor acc)

O(1)

Specified by:

contains in interface InspectableContainer

remove

public void remove(Locator loc)
            throws InvalidAccessorException

O(1) expected: strictly O(1) unless removal reduces size below the downhashing threshhold, in which case it is O(N)

Specified by:

remove in interface KeyBasedContainer

Parameters:

loc - a locator in the container to remove

Throws:

InvalidAccessorException - if the locator is not valid or is not contained by this container

replaceKey

public Object replaceKey(Locator loc,
                         Object key)

O(1)

Specified by:

replaceKey in interface KeyBasedContainer

Parameters:

loc - the locator in the container whose key should be replaced

key - the new key to associate with loc.

Returns:

The old key

locators

public LocatorIterator locators()

O(1) if structure hasn't changed, O(N) otherwise.

Specified by:

locators in interface InspectableKeyBasedContainer

Returns:

a LocatorIterator over all of the locators in the container

keys

public ObjectIterator keys()

O(1) if structure hasn't changed, O(N) otherwise.

Specified by:

keys in interface InspectableKeyBasedContainer

Returns:

an iterator over all the keys stored in this container

elements

public ObjectIterator elements()

O(1) if structure *AND* elements haven't changed, O(N) otherwise.

Specified by:

elements in interface InspectableContainer

Returns:

an iterator over all the elements stored in this container

findAll

public LocatorIterator findAll(Object key)
                        throws InvalidKeyException

O(#elts with target key), worst case O(N)

Specified by:

findAll in interface InspectableDictionary

Parameters:

key - The key to search for.

Returns:

A LocatorIterator over the set of (key, element) pairs whose keys match the parameter key

Throws:

InvalidKeyException - if the specified key is not valid in this container

removeAll

public LocatorIterator removeAll(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.

Specified by:

removeAll in interface Dictionary

Parameters:

key - the key to search for

Returns:

a LocatorIterator over the (key, element) pairs whose keys match the parameter key

removeKey

public Locator removeKey(Object key)
                  throws InvalidKeyException

Removes the first element found with the given key from the hashtable. O(1) -- expected. will be O(N) with excessive chaining or if removal reduces below the downhashing threshhold.

Throws:

InvalidKeyException - if the key cannot be compared

insert

public Locator insert(Object key,
                      Object value)
               throws InvalidKeyException

O(1) expected, O(N) if insertion pushes the size above the rehashing threshhold.

Specified by:

insert in interface KeyBasedContainer

Parameters:

key - the key associated with the specified element.

value - the element to insert into the container.

Returns:

a locator associated with the inserted pair.

Throws:

InvalidKeyException - if key cannot be used by this container

find

public Locator find(Object key)
             throws InvalidKeyException

O(1) -- expected, O(N) worst case with excessive chaining.

Specified by:

find in interface InspectableDictionary

Parameters:

key - The key mapped to search for.

Returns:

The Locator referring to the key-element pair that was found, or NO_SUCH_KEY if it could not be found.

Throws:

InvalidKeyException - if the specified key is not a valid key in this container.

See Also:

InspectableDictionary.NO_SUCH_KEY

toString

public String toString()

O(N) human readable description of the contents of this dictionary, conforming to the Collections spec for key-element structures.