Class Hashtable<K,D>

java.lang.Object
  Dictionary<K,D>
      Hashtable<K,D>

Type Parameters:

K - The type of the keys. Note that Object.hashCode() and Object.equals(Object) must conform to each other, i.e. whenever o1.equals(o2) == true then o1.hashCode() == o2.hashCode() must hold. Otherwise, this data-structure will have unexpected behaviour.

D - The type of the data.

All Implemented Interfaces:

Map<K,D>

public class Hashtable<K,D>
extends Dictionary<K,D>

A hashtable implementation of the Map-interface. Conflicts are resolved by allowing multiple entries per array element. Automatic reallocation of the table is performed if the table is too empty or too crowded. Standard access methods like insertion, deletion, etc. all have amortized cost O(1) if a good hash-function, i.e. Object.hashCode() is used.

Author:

Rossmanith

Constructor Summary

Hashtable()
Constructs an empty hashtable with default initial tablesize (10).

Hashtable(int s)
Constructs an empty hashtable with initial tablesize s.

Method Summary

void	delete(K k) Removes the entry which stores the data for the key k.
D	find(K k) Looks up the data stored under the key k.
void	insert(K k, D d) Associates the data d to the key k in this map.
boolean	iselement(K k) Checks whether the key k is present in this map.
Iterator<K,D>	iterator() Creates a new iterator over all associations between keys and data.
int	size() Returns the size of this map, i.e. the number of keys, under which data is stored in O(1).

Methods inherited from class Dictionary

array, isempty, print, simpleiterator

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Hashtable

public Hashtable(int s)

Constructs an empty hashtable with initial tablesize s.

Parameters:

s - The initial size of the table.

Hashtable

public Hashtable()

Constructs an empty hashtable with default initial tablesize (10).

Method Detail

iterator

public Iterator<K,D> iterator()

Description copied from interface: Map

Creates a new iterator over all associations between keys and data.

Specified by:

iterator in interface Map<K,D>

Specified by:

iterator in class Dictionary<K,D>

Returns:

The Iterator over all keys with associated data.

insert

public void insert(K k,
                   D d)

Associates the data d to the key k in this map. A possible old entry for k will be deleted. (amortized cost of O(1) when using a good hash-function)

Specified by:

insert in interface Map<K,D>

Specified by:

insert in class Dictionary<K,D>

Parameters:

k - The key to store.

d - The data associated to the key k.

See Also:

Map.insert(Object, Object)

delete

public void delete(K k)

Removes the entry which stores the data for the key k. Idle operations if there is no data stored for k. (amortized cost of O(1) when using a good hash-function)

Specified by:

delete in interface Map<K,D>

Specified by:

delete in class Dictionary<K,D>

Parameters:

k - The key to delete with its associated data.

See Also:

Map.delete(Object)

find

public D find(K k)

Looks up the data stored under the key k. (amortized cost of O(1) when using a good hash-function)

Specified by:

find in interface Map<K,D>

Overrides:

find in class Dictionary<K,D>

Parameters:

k - The key under which the data is stored.

Returns:

The data, which is stored under the key k, or null, if there is no data associated to k.

See Also:

Map.find(Object)

iselement

public boolean iselement(K k)

Checks whether the key k is present in this map. (amortized cost of O(1) when using a good hash-function)

Specified by:

iselement in interface Map<K,D>

Overrides:

iselement in class Dictionary<K,D>

Parameters:

k - The key to look for.

Returns:

true, if k is contained in this map, and false, otherwise.

See Also:

Map.iselement(Object)

size

public int size()

Returns the size of this map, i.e. the number of keys, under which data is stored in O(1).

Specified by:

size in interface Map<K,D>

Overrides:

size in class Dictionary<K,D>