|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object finiteAutomata.Hashtable
public class Hashtable
Data structure which allows for insertions, deletions, and finds in
constant average time.
This Hashtable class uses separate chaining to store Associations
(key-value pairs). Any non-null object can be used as the key (which
is used as input to the hashing function). To successfully store and
retrieve values from a hashtable, the objects used as keys must
implement the hashCode method and the equals method. To store an
Association, apply the hash function to its key and store the
Association in the resulting list (first check that an equivalent
Association is not already present). To retrieve an Association,
apply the hash function to its key and search for it in the resulting
list. If the hashtable is appropriately long and if the hash function
does a good job of distributing the keys evenly among the hashing
locations, then all the lists should be short and it will be very
quick to find, insert, and delete based on keys.
Data Fields:
A Hashtable is based on an array "table" of Vectors. The integer field
"tableSize" gives the length of the array, and should be a prime number
(to help insure even distribution for the hashing function).
The integer field "size" tells how many Associations are currently
stored; load factor can thus be calculated by size / tableSize. (Load
factor around 1.0 is ideal for efficient use of time and space in open
chaining.)
Field Summary | |
---|---|
protected int |
size
number of Associations currently stored |
protected java.util.Vector[] |
table
Vector lists for storing Assocations |
protected int |
tableSize
length of the "table" array |
Constructor Summary | |
---|---|
Hashtable()
0-parameter constructor. |
|
Hashtable(int n)
1-parameter constructor. |
Method Summary | |
---|---|
boolean |
contains(java.lang.Object key)
Returns true if an item with this same key exists in the hashtable. |
java.lang.Object |
get(java.lang.Object key)
Returns the value associated with key, or null (if not found). |
protected int |
indexOf(java.lang.Object key,
int hash)
Returns the index, relative to the Vector table[hash], of the Association with the given key. |
void |
insert(java.lang.Object key,
java.lang.Object value)
Inserts an Association. |
boolean |
isEmpty()
True if no Associations are stored. |
double |
loadFactor()
Returns the current load factor, size divided by tableSize. |
protected int |
locate(java.lang.Object key)
Returns the hash location for the provided key. |
static void |
main(java.lang.String[] args)
|
void |
printTable()
Pretty-prints the hash table information. |
java.lang.Object |
remove(java.lang.Object key)
Removes an Association. |
int |
size()
Returns number of Associations currently stored. |
int |
tableSize()
Returns tableSize. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected java.util.Vector[] table
protected int tableSize
protected int size
Constructor Detail |
---|
public Hashtable(int n)
n
- table sizepublic Hashtable()
Method Detail |
---|
public int tableSize()
public int size()
public double loadFactor()
protected int locate(java.lang.Object key)
key
- the key to be hashed on
protected int indexOf(java.lang.Object key, int hash)
key
- the key to be locatedhash
- indexes the Vector to be searched
public java.lang.Object get(java.lang.Object key)
key
- the key to be searched on
public boolean contains(java.lang.Object key)
key
- the key to be searched on
public void insert(java.lang.Object key, java.lang.Object value)
key
- the key to be searched onvalue
- the associated value for keypublic java.lang.Object remove(java.lang.Object key)
key
- the key to be searched on
public boolean isEmpty()
public void printTable()
public static void main(java.lang.String[] args)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |