|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--com.mhhe.clrs2e.OpenAddressingHashTable
Abstract base class for hash tables that use open addressing, as
described on pages 237-241 of Introduction to Algorithms,
Second edition. Handles returned by the insert
and
search
methods are simply indices into the hash
table.
Field Summary | |
private java.lang.String |
DELETED
Indicator that a slot used to hold an object but that object has been deleted from the hash table. |
protected int |
m
How many slots are in the hash table. |
private java.lang.Comparable[] |
table
The hash table. |
Constructor Summary | |
OpenAddressingHashTable()
Creates a new open-addressed hash table with 16 entries. |
|
OpenAddressingHashTable(int m)
Creates a new open-addressed hash table of a given size. |
Method Summary | |
void |
delete(java.lang.Object handle)
Removes an element. |
protected abstract int |
hash(java.lang.Object o,
int i)
Computes a hash function for an open-addressing hash table, dependent on an object and a probe number. |
private void |
initOpenAddressingHashTable(int m)
Initializes an open-addressed hash table of a given size. |
java.lang.Object |
insert(java.lang.Comparable o)
Inserts an element that implements Comparable . |
java.lang.Object |
search(java.lang.Comparable k)
Searches for an element with a given key. |
java.lang.String |
toString()
Returns the String representation of this
hash table, with one entry per line. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
private final java.lang.String DELETED
private java.lang.Comparable[] table
protected int m
Constructor Detail |
public OpenAddressingHashTable()
public OpenAddressingHashTable(int m)
m
- The size of the open-addressed hash table.Method Detail |
private void initOpenAddressingHashTable(int m)
m
- The size of the open-addressed hash table.protected abstract int hash(java.lang.Object o, int i)
The probe sequence
o
- The object. If the object implements
DynamicSetElement
, the hash value is of its key.i
- The probe number.
public java.lang.Object insert(java.lang.Comparable o)
Comparable
.
insert
in interface Dictionary
o
- The element to insert.
HashTableOverflow
- if the hash table is full.public void delete(java.lang.Object handle)
delete
in interface Dictionary
handle
- A handle to the element to remove. The handle is
just the index of the element to remove.
java.lang.ClassCastException
- if handle
does not
reference an Integer
.
java.lang.ArrayIndexOutOfBoundsException
- if the integer value of
handle
is not in the range 0 to m-1.public java.lang.Object search(java.lang.Comparable k)
search
in interface Dictionary
k
- The key being searched for.
null
if
there is no match.public java.lang.String toString()
String
representation of this
hash table, with one entry per line.
toString
in class java.lang.Object
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |