This applet visually demonstrates the use of hashing in programming. View the applet in the Applet section below. The usage of the applet is described in the following Usage section. For those interested, the Display and design of the applet are also described.
Hashtables are useful for rapid insertion and searching for single values. There are three common operations on hashtables, Insert, Delete and Search. All three require an argument. You can perform any of these operations on the visual by clicking the respective buttons. Enter an integer into the textbox when prompted; this will be the key to search for, delete, or insert.
For each operation, you will be able to step through the code that manipulates the hash table using the Step or Autostep buttons.
At any time (except when entering a value) you can also reset the entire display to the original empty state by clicking the Reset button.
The usual demonstration framework and display is used. The buttons are displayed in an InputPanel along the top of the screen, with the Step/Autostep buttons first, and the Reset button last. The box to retrieve user input is also on this bar when it is visible.
Below this and to the left is the pseudocode area. This area is divided in two. The upper area shows the method signatures and variables used in the hashing mechanism. The lower area shows whichever method is currently being stepped through.
To the right of this is the visualization area. This area displays the hashtable as the user steps through the code. It is displayed as an array, with indices above and the values (strings) below. Items not currently of interest are displayed with a black outline and lettering. The currently selected element is outlined in blue. Any tombstone items are outlined in red.
The applet will follow the standard demonstration design. Methods
will be shown in a ProgramPanel with an overview
above and specific methods below. There will have to be separate
method calls to the hashchode functions.
The visualization area will be quite simple. The array will have 11 elements (11 is nicely prime). The array will be simply displayed, with selected items in blue. Both the array display and multiple method setup will be similar to the Heap demonstration.
These Pseudocode methods will be used. For the main function:
class HashTable {
int max = 11
table = new int[max]
boolean search(int key);
boolean remove(int key);
void insert(int key);
int hashHome(int key);
int probeStep(int key);
}
For the search function:
public int search(int key) {
if (key < 1)
throw invalidKeyException
pos = home = hashHome(key)
for (int i = 1; table[pos] != 0 && table[pos] != key; i++)
pos = (home + i * probeStep(key)) % max
if (table[pos] == 0)
return -1
return pos
}
For the insert function:
public void insert(int key) {
if (key < 1)
throw InvalidKeyException
insertpos = -1
pos = home = hashHome(key)
for (int i = 1; table[pos] != 0; i++) {
if (table[pos] == key)
throw NoDuplicatesException
if (insertpos == -1 && pos == -1)
insertpos = pos
pos = (home + i * probe(key)) % max
}
if (insertpos == -1)
table[pos] = key
else
table[insertpos] = key
}
For the remove function:
public int remove(int key) {
if (key < 1)
throw InvalidKeyException
pos = search(key)
if (pos == -1)
return -1
table[pos] = -1
return pos
}
For the hashHome function:
public int hashHome(int key) {
int hash = key % 11
return hash
}
For the probe function:
public int probeStep(int key) {
int doublehash = key % 10 + 1
return doublehash
}